Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
61
questions
25
votes
3answers
5k 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
5k 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$?
7
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.
31
votes
1answer
4k 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$?
24
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 ...
40
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.
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 ...
5
votes
2answers
409 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
974 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
1k 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 ...
14
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
395 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
594 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 (...
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?
8
votes
2answers
663 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
482 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
157 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 $...
3
votes
2answers
309 views
If-then constraint with continuous variables
I was usually using if-then constraints with integer variables but ended up using continuous variables and got confused. I have variables $x_{ij}\in\mathbb{R}_{\geq 0}$, and would like to force the ...
28
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 ...
19
votes
4answers
789 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
928 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
351 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
1k 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
411 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
378 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
2answers
434 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
3k 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
387 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
685 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
2answers
159 views
Asymmetric time-constrained capacitated vehicle routing problem
I am trying to add some more constraints to the flow-based ADVRP model in Almoustafa et al. (2013)1 (pp.4).
The mentioned model caps the travel distance, while I cap the travel time. Let $U$ represent ...
5
votes
1answer
429 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?
2
votes
1answer
153 views
Pulp Python: How to formulate a time-based variable for shipping demurrage
I am working on a shipping optimisation problem that aims to minimise demurrage charges as a result of low/insufficient inventory.
I have daily vessel requirement (sales) data in the format ...
21
votes
5answers
323 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
274 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
287 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
676 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
1k 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
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 ...
8
votes
2answers
135 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$ ...
7
votes
1answer
712 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
2answers
237 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
1answer
171 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
3answers
185 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
2answers
175 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 \...
4
votes
0answers
193 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\...
