Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
4
votes
0answers
188 views

How can I formulate this multi-objective optimization problem?

Now, for each system $X$ $(X=A,B,C,E)$, my objective is $$\max\min\frac{s_{x_u}}{d_{x_u}}$$ here, $x=a$ for system A, $x=b$ for system B and follows... and for the whole system, my objective is $$\max\...
15
votes
3answers
999 views

How does the search space affect the speed of an ILP solver?

Let us suppose we have an optimization problem which we have modeled as an ILP. Suppose we solve this problem using some set of constraints which restricts the search space. Let us suppose we model ...
7
votes
1answer
622 views

Why is the Ellipsoid Method of polynomial complexity?

We know that the ellipsoid method is proven to be of polynomial complexity. However, as far as I can tell we may need to add exponentially many feasibility cuts in order to solve the LP (or prove no ...
22
votes
4answers
2k views

Find feasible point in polynomial time in linear programming

Background A while ago my team was implementing an interior point LP solver and we came across the following conundrum: Is there a polynomial-time algorithm to find a feasible starting point in ...
9
votes
1answer
102 views

Extreme rays in polymake

I am trying to find extreme rays of a polyhedral cone using polymake. My understanding is that in a cone, every feasible solution is also a ray and an extreme ray is a ray that cannot be written as ...
14
votes
2answers
819 views

State-of-the-art algorithms for solving linear programs

Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances)....
8
votes
1answer
118 views

Workforce Scheduling problem - Modelling to minimize resources

I am working on a scheduling program for a service desk. I want to decide the number of people required to come in at each shift. The data I have is: There are 4 overlapping shifts Arrival pattern at ...
5
votes
2answers
379 views

Linear and Integer programming materials

I was wondering if you could refer me to some online video/text resources to learn linear and integer programming. I am intending to work in the field of data science. I greatly appreciate your kind ...
9
votes
2answers
330 views

Generating all extreme rays

I am trying to understand a problem and would like to generate all extreme rays for a given set of linear constraints. With the Python interface of CPLEX, I was able to generate a single ray (not sure ...
17
votes
2answers
2k views

How does a warm start work in LP/MIP?

Can someone explain how warm starts/ MIP starts work? How do solvers like CPLEX/GUROBI use warm start with the Simplex algorithm? I am interested in understanding how the entire warm start ...
12
votes
1answer
316 views

Mixed-Integer Linear Programming (Capacity Planning)

I'm currently developing a small capacity planning problem and right now I am struggling with the "activation" of a subset. Needless to say I am not an expert in this kind of things. I have a set of $...
9
votes
3answers
2k views

Google - OR tools for workforce scheduling problems

Has anyone used the google OR tools in python to solve the workforce scheduling problem. Can you please let me know Advantages and Disadvantages Any issues faced during usage and implementation
10
votes
1answer
179 views

Algorithm for workforce scheduling for call volumes

I am trying to solve a workforce scheduling and optimization problem. Available data: daily level forecasted call volumes, shift schedules, resource utilization at the aggregate level, AHT at ...
6
votes
2answers
247 views

How to add Binary Variable with condition in LP

Notation $\text{src}_{h,s},\text{dst}_{h,s},\text{ch}_{h,s}$ are constants. $a_{h,s},x_{i,j,s}$ are binary variables. $\text{wt}_{h,s}$ are continuous variables. Problem \begin{align}\min.&\...
6
votes
2answers
690 views

Linearization of objective function

Notation $\text{src}_{h,s},\text{dst}_{h,s},\text{ch}_{h,s}$ are constants. $a_{h,s},x_{i,j,s}$ are binary variables. $\text{wt}_{h,s}$ are continuous variables. Problem \begin{align}\min.&\...
14
votes
2answers
1k views

Polyhedra, Polyhedron, Polytopes and Polygon

About Polyhedra, Polyhedron, Polytopes and Polygon, what do they mean in the context of linear programming and what is the difference between them?
10
votes
2answers
697 views

Running a linear programming model to maximize binned predictions

I have a dataframe like: ...
20
votes
4answers
2k views

Linearize or approximate a square root constraint

I encounter a nonlinear constraint that contains the square root of a sum of integer variables. Of course one could use nonlinear solvers and techniques; but I like linear programming. Are there any ...
13
votes
2answers
274 views

Querying attributes of LP relaxation at MIP-optimality in Gurobi

Is there a way to configure Gurobi to allow the LP relaxation associated with the optimal solution leaf of a MIP branch-and-bound tree to be queried for shadow prices & other general LP properties-...
9
votes
1answer
147 views

Structural Optimization

Currently, I am working on a problem in which I need to use MILP to model equilibrium equations in a lightweight structure. Although this is an application based question, I wondered if there is a ...
4
votes
1answer
371 views

Having negative value for non basic variable gives a infeasible solution in simplex method?

I try to solve the following linear program with the simplex method: $$ \begin{alignedat}{4} \max & \quad & x_1 & {}-{} & 2x_2\\ \text{subject to} & & &...
7
votes
1answer
99 views

References for “metric” network flow problems

Network flow problems are very well studied in the literature (e.g., see the Network Flows book), and the first DIMACS challenge was dedicated to these problems. Very efficient implementation of ...
5
votes
2answers
214 views

Formulation of a constraint in a MIP for an element in different Sets

I have an element e $\in E$ with $E$ the set containing all elements e and $e \in Y_i$ with $Y_i \subseteq E$. Each set $Y_i$ has different attributes. $G_j$ is a set of sets and the following holds: $...
18
votes
4answers
3k views

How to evaluate the performance of open source solver?

I am looking for a reliable open source solver to solve LP and MILP (with a few thousand variables). How can I evaluate the performance of a given solver for a particular use case?
12
votes
2answers
107 views

Pricing of blends/mixtures across multiple timesteps

I have a simple blending problem, where each final product is a blend or mixture of several raw materials, and want to calculate the price per unit of weight for each of the products. So for a given ...
5
votes
0answers
92 views

Construct a direction of recession of the dual that is from growth to dual function

Consider the primal problem $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & Ax = b\\ & x \geq 0\end{array}$$ where $ A \in \mathbb {R}^{ m × n}$ has rank $m$. Suppose ...
21
votes
1answer
287 views

Polynomially solvable problems with exponential extension complexity

The maximum matching problem is solvable in polynomial time using Edmonds' blossom algorithm. However, unlike for example the spanning tree polytope, it has been proven fairly recently that the ...
8
votes
1answer
138 views

What is the Bound Flipping Ratio test?

The bound flipping ratio test (BFRT) appears to be an important feature of modern Simplex implementations. What is it, and how does it work?
4
votes
1answer
794 views

What are good reference books for introduction to operations research?

The reference books should cover the wide range of problem-solving techniques and methods.
-3
votes
1answer
85 views

Geometric interpretation of a Linear problem with bounded variables

I have a question of how to make a geometric interpretation of this problem \begin{eqnarray} \mbox{max} & z = 3x_1+x_3 \\ s.a: & \\ & \begin{array}{cc} x_1+2x_2+x_3+x_4& =...
22
votes
4answers
4k views

What instances can be solved today by modern solvers (pure LP)?

I have found a PowerPoint presentation in which the presentor Hall claims instances could be of the size of 108 in variables and constraints to be solved today. I assume that he meant sparse problems. ...
26
votes
4answers
2k views

“Best practices” for formulating MIPs

Often there are many alternatives ways for formulating a MIP. For example: The model contains inequality constraints that must hold with equality in an optimal solution. The model contains ...
18
votes
2answers
263 views

Mathematically creating the 'perfect' permutation for reservations in a hostel

I am working at a hostel which uses a reservation system for each room and the beds in the room (e.g. $14$ beds in one room, bed numbers $1-14$.) When we get bookings for multiple people, we assign ...
16
votes
1answer
867 views

Prove that these linear programming problems are bounded by $O(k^{1/2})$

Prove that these linear programming problems are bounded by $O(k^{1/2})$ Conjecturally the expanded partial sums of the Möbius transform of the Harmonic numbers have two out of three properties in ...
12
votes
2answers
760 views

Correct way to get a dual extreme ray for an infeasible LP in CPLEX / C++

We are coding a Benders decomposition using CPLEX/Concert (C++) and we are having some troubles to generate a feasibility cut because we are not sure how to get an extreme ray of the dual for a primal ...
11
votes
3answers
201 views

Applicability of Lagrange Multipliers in the analysis of large-scale MILPs?

Qualitatively, in my experience in the solving of large scale MILPs, it is common that binary variables corresponding to "edge possibility" components are frequently chosen. Intuitively, these seem ...
7
votes
1answer
222 views

Assignment problem using Hungarian method

There are five jobs to be assigned to five machines and associated cost matrix is as follows $$ \begin{matrix} \text{Machine} & 1 & 2 & 3 & 4 & 5 \\ \text{Job A} & [11, &...
11
votes
3answers
192 views

Efficiency of solving LP relaxation

I'm building a mixed-integer programming model, and the solver is experiencing a very long run time. So I tried to solve the LP relaxation to the MIP, and I get a similarly long solve time, which ...
13
votes
2answers
294 views

Application of complex numbers in Linear Programming?

The theory surrounding Linear Programming is based on variables, bounds and coefficients that take on values in $\mathbb R$, the set of real numbers. I have long wondered whether there might be ...
11
votes
1answer
84 views

Computational complexity to compute an IIS

How hard is it to compute an irreducible infeasible subset (IIS) for a linear program? What about an integer program (e.g., removing the integrality constraint on a single variable may be enough to ...
13
votes
5answers
212 views

Connectivity of two nodes in an arbitrary undirected graph

Is there an efficient way to model the connectivity of two nodes in an arbitrary undirected graph? I would like to have a binary variable representing this connectivity: 1 if there exists a path ...
21
votes
5answers
287 views

Tightness of an LP relaxation without using objective function

How can we measure the tightness of a linear programming relaxation for a mixed integer linear program without using the objective value? I would like to get a measure in terms of the feasible set and ...
15
votes
1answer
392 views

How to get the best bound of large LP problems in CPLEX?

When using the C callable library to solve a large LP, how can I get the best bound after calling the method CPXXlpopt? Does it depend on the algorithm used to ...
17
votes
2answers
228 views

Automating the column generation decomposition process

When trying a decomposition technique such as column generation, most of the times my approach is to look at the problem and then: Decide what a column should represent Write the Master Problem Write ...
8
votes
2answers
295 views

Simplex-Implementations in professional Solvers

Which non-textbook variants (primal/dual, revised) and techniques (e.g. steepest-edge) do professional solvers like Xpress, CPLEX, CLP use, to get the best out of the simplex algorithm? This ...
17
votes
2answers
330 views

Guidelines for Linear Optimization approaches?

When solving a Linear Optimization model (or Linear Program), there are a lot of solution approaches. Just to name a few: Primal Simplex Dual Simplex Ellipsoid Method (as if) ...
25
votes
3answers
391 views

Feeding known lower bounds to solvers

Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all optimal solutions, and your solver of choice: For what theoretical and/or practical (...
16
votes
2answers
178 views

Is the Irreducible Infeasible Subset (IIS) of an LP unique?

The IIS is a standard part of most modern solvers, but is it unique for an LP? My intuition tells me that it should be, but I could find any proof.
12
votes
1answer
110 views

How to reduce recursion when using Gomory cutting planes to solve an integer program?

Consider the following simple integer program $$\begin{array}{ll} \text{maximize} & 3 x_1 - x_2\\ \text{subject to} & 3x_1 - x_2 \leqslant 3 \\ & -5x_1 - 4x_2 \leqslant -10 \\ & ...
20
votes
4answers
559 views

How can I remember the rules for taking the dual of a linear program (LP)?

When taking the dual of a linear program (LP), is there a trick/easy way to remember the rules for the directions of the inequalities, signs of the variables, etc.? A trick with a catchy name, perhaps?...