Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
51
questions
23
votes
3answers
4k views
In an integer program, how I can force a binary variable to equal 1 if some condition holds?
Suppose we have a binary or continuous variable $x$, a binary variable $y$, and a constant $b$, and we want to enforce a relationship like
If $x \gtreqless b$, then $y = 1$.
How can we write this ...
4
votes
1answer
832 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.
27
votes
1answer
3k views
How to linearize the product of a binary and a non-negative continuous variable?
Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
29
votes
2answers
3k views
How to linearize the product of two binary variables?
Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?
22
votes
2answers
1k views
Why is it important to choose big-M carefully and what are the consequences of doing it badly?
The question here discusses the two different use of "big-M method", where one of them is the big-M in logical constraints and linearization in (mixed-)integer programming problems (that's what I'm ...
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 ...
38
votes
8answers
1k views
Optimization Problem Libraries
Can someone please make a list of optimization problem libraries so that the community can add to and refine it?
I know a few off the top of my head.
5
votes
2answers
385 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 ...
33
votes
6answers
847 views
Where can I find open source LP solvers?
I'm familiar with COIN-OR and have also used a couple packages in R to solve LPs. Today I found out Google has their own open source optimization software, and it got me wondering what other open ...
14
votes
2answers
871 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)....
17
votes
5answers
3k views
Linear Programming with additional “if-then”/“Default to zero” constraints?
What approaches can I use for a Linear Programming problem with the additional constraint that if a decision variable falls below a certain threshold, then it should just be forced to 0.
I'm ...
16
votes
5answers
2k views
How to linearize the product of two continuous variables?
Suppose we have two variables $x, y \in \mathbb R$. How can we linearize the product $xy$?
If this cannot be done exactly, is there a way to get an approximate result?
21
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 ...
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 ...
27
votes
3answers
453 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 (...
8
votes
2answers
621 views
Linear optimization problem with user-defined cost function
I have a linear optimization problem for which I am looking for a suitable optimization solution that can fulfill my requirements. Here is an explanation of the optimization problem:
There are a ...
10
votes
3answers
1k views
Is there a heuristic approach to the MILP problem?
I have the following optimization problem which is a MILP. I can solve it with a MILP solver.
\begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,...
20
votes
4answers
612 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?...
16
votes
1answer
573 views
What is the “big-M” method? And are there two of them?
I’ve seen the "big-$M$ method" referred to in different ways. What is the "big-$M$ method" and why does it seem to mean two different things?
8
votes
2answers
305 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 ...
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?
14
votes
1answer
329 views
How to linearize a constraint with a maximum or minimum in the right-hand-side?
Suppose we have three variables, $x, y, z \in \mathbb R$. How can we linearize constraints with the following structure?
$$z \geq \min(x, y)$$
$$z \leq \max(x, y)$$
13
votes
2answers
315 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 ...
13
votes
2answers
330 views
Black-box optimization with linear programming?
In my research, I do a black-box optimization based on a simulation model with nonlinear properties. The simulation model gets an operation plan for a time period and then returns a time series, which ...
12
votes
2answers
1k views
Linear programming: objective function with “buckets”
I had a linear programming problem with the following objective function
$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$
Where $q, p, C, c$ are known.
This problem was ...
9
votes
2answers
363 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 ...
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
8
votes
3answers
377 views
LP dependent on the ordering of the data
This is a rather simple question. Can a solution to a linear programming problem be dependent on the order in which the data is read/presented/stored?
I know, that the time it takes to solve the ...
5
votes
1answer
397 views
Where can I find resources to learn mathematical modelling for real life operation research problems like combinatorial optimization?
I find it hard to form math models for real life operations research problems, how can I learn this? Any books, tutorials available?
21
votes
5answers
293 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 ...
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
373 views
Working with absolute values in constraint in a LP or MILP
Having all the approaches explained in the blog called "OR in an OB World" (this address) in my mind, I would like to ask the following question:
What is the best practice to make a constraint linear ...
11
votes
2answers
649 views
Can presolve reductions change the value of the linear programming relaxation?
For integer programs solvers (like Gurobi, Cplex, ...) report the value of the linear programming relaxation for integer programs, i.e.
...
9
votes
3answers
717 views
How to find all vertices of a polyhedron
I have a convex polyhedron given by a set of linear inequalities, for example:
$$
x_1 \geq 0,~~ x_2 \geq 0, ~~x_3\geq 0
\\
x_1+x_2\leq 1,~~ x_2+x_3\leq 1,~~ x_3+x_1\leq 1
$$
I want to list all the ...
8
votes
2answers
129 views
Bounding arrival time at a node in a resource-constrained shortest path problem
Given a city map (a graph) $G$,
$b_{i,j}$ is a Boolean variable for whether or not edge $i$,$j$ is allocated, $d_{i,j}$ denotes the distance between $i$,$j$.
The objective is to move from $s$ to $e$ ...
8
votes
2answers
921 views
Complexity of LP and MILP Problems?
My original problem is an MILP. I make it an LP by relaxing the integer variables.
Can someone please comment on the complexity, solvability and optimality of MILP and LP problems, in general?
Is ...
7
votes
1answer
647 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 ...
6
votes
2answers
157 views
Polynomial algorithm for a special ILP problem
Given the following problem:
\begin{align}
& z=\min \sum_{ij} x_{ij}\\
\text{s.t.} & \quad \sum_i d_{ij} x_{ij} \ge s_j, \quad \forall j \tag1 \\
& \quad \sum_j x_{ij} \le 1, \quad \...
5
votes
2answers
218 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: $...
5
votes
3answers
181 views
Reducing number of suppliers for product portfolio
I have the following matrix of suppliers who are able to make a certain product, against all products in my portfolio.
What is the best way of finding the solution to "the least suppliers necessary ...
5
votes
1answer
125 views
Linearizing a constraint with square root of a variable
I am trying to linearize the constraint set (2) in the following simplified program. The parameters: $A,C,D,T\in\mathbb{R}^+$. The set $\mathcal{J}$ is polynomially-sized.
\begin{alignat}2\min &\...
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\...
4
votes
2answers
93 views
Modelling a data-sensitivity scenario as an ILP problem
I am new to linear programming, and I recently came across the following exercise, which I do not know how to solve:
When publishing data, it is sometimes important to "suppress" sensitive ...
3
votes
1answer
38 views
Finding bounds on a data sensitivity scenario ILP problem
This is a follow up to a problem I posted here: Modelling a data-sensitivity scenario as an ILP problem
As a recap, I was interested in finding the minimum number of cells that need to be suppressed ...
3
votes
1answer
123 views
Representing Date Variables in Pulp
I am working on an optimisation problem that involves minimising shipping demurrage. I am struggling to model how to represent the difference, (x-y) between dates where the ship is ready to be loaded ...
3
votes
2answers
190 views
Find all Combinations of a Matrix
I have a $16\times11$ matrix and want to find all eligible* combinations of this matrix including always entities from all 11 columns.
A simple example from a $2\times3$ matrix would be the following:...
2
votes
1answer
116 views
Is my formulation correct and how to formulate this IF-THEN constraint?
I have system with $N_U$ users and $N_T$ transmitters. Multiple transmitters can transmit to a single users and one transmitter can transmit to many users, i.e., two sets of transmitters serving two ...
2
votes
0answers
58 views
Linear programming: extending problems yields non linearity
I had a linear programming problem with the following objective function
$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$
Where $q, p, C, c$ are known. Let the term ...
2
votes
1answer
141 views
Controlling the constraint execution sequence in docplex
I have tried to implement my question asked here with the help of Github code link.
Below is the linearized version of the MTZ like constraint as per the answer given here. Constraints below assign ...
0
votes
1answer
197 views
Is optimal solution to dual not unique if optimal solution to the primal is degenerate?
If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption?
Spin-off from here.
In my ...
