Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
59
questions
24
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 ...
32
votes
2answers
4k 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$?
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$?
6
votes
1answer
1k 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.
22
votes
2answers
2k 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
3k 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
399 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
913 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
930 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 ...
15
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?
14
votes
1answer
372 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)$$
22
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
520 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 (...
19
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?
8
votes
2answers
635 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 ...
16
votes
1answer
418 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 ...
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,...
6
votes
1answer
153 views
TSP subtour elimination by assigning distance traveled
Given a set $S$ which we need to travel following TSP rules.
I was wondering if this sub tour elimination method is good enough or not?
Let $b_{i,j}$ denote edge from $i$ to $j$ is taken or not and $...
20
votes
4answers
665 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
713 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
333 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
3answers
996 views
TSP with revenue maximization
How to approach a travelling salesman problem with an aim to maximize revenue at each town visited in a certain number of days (total number of towns is greater than what can be visited in the given ...
13
votes
2answers
362 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
352 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 ...
11
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
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
9
votes
2answers
397 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 ...
8
votes
3answers
383 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 ...
8
votes
1answer
596 views
How to linearize the multiplication of an integer and a binary integer variable?
I have the following constraints
\begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align}
where $x_i\ge 0$ is an integer variable, $t_i\in\{0,1\}$ is a binary variable ...
5
votes
1answer
418 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
311 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
267 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 ...
14
votes
4answers
274 views
Does this $0-1$ integer program have any speciality?
Given matrix $A \in \{0,1\}^{m \times n}$ and vector $b \in (\mathbb{Z^+})^m$, where $\mathbb{Z^+}$ is the set of positive integers,
$$\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject ...
11
votes
2answers
666 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
930 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
132 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
1k 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
681 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 ...
5
votes
3answers
183 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
139 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 &\...
5
votes
2answers
163 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
228 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: $...
4
votes
0answers
191 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\...
3
votes
2answers
96 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
2answers
220 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
39 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 ...
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 ...
