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
32 votes
3 answers
19k 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 ...
LarrySnyder610's user avatar
37 votes
3 answers
16k 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$?
Michiel uit het Broek's user avatar
36 votes
2 answers
11k 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$?
Michiel uit het Broek's user avatar
10 votes
1 answer
3k 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.
Rajasekhar Kadambur's user avatar
24 votes
2 answers
6k 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 ...
EhsanK's user avatar
  • 5,864
15 votes
5 answers
8k 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?
Michiel uit het Broek's user avatar
51 votes
8 answers
3k 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.
Mark L. Stone's user avatar
22 votes
2 answers
7k 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 pipeline ...
Palaniappan Chellappan's user avatar
22 votes
4 answers
3k 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 ...
Albert Schrotenboer's user avatar
15 votes
2 answers
2k 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)....
rasul's user avatar
  • 2,140
34 votes
6 answers
2k 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 ...
Zohar Strinka's user avatar
31 votes
3 answers
2k 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 feasible solutions, and your solver of choice: For what theoretical and/or practical ...
fbahr's user avatar
  • 1,026
18 votes
1 answer
3k 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 ...
Oguz Toragay's user avatar
  • 8,652
17 votes
5 answers
5k 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 ...
Skander H.'s user avatar
  • 2,139
16 votes
1 answer
909 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)$$
Michiel uit het Broek's user avatar
12 votes
3 answers
6k 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 ...
Erel Segal-Halevi's user avatar
5 votes
2 answers
583 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 ...
Hasibul's user avatar
  • 67
24 votes
5 answers
4k 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 ...
Nikos Kazazakis's user avatar
24 votes
5 answers
4k 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?...
David M.'s user avatar
  • 2,077
22 votes
3 answers
2k views

How to minimize an absolute value in the objective of an LP?

I want to solve the following optimization problem $$\begin{array}{ll} \text{minimize} & | c^\top x |\\ \text{subject to} & A x \leq b\end{array}$$ Without the absolute value, this a ...
Discrete lizard's user avatar
19 votes
4 answers
4k 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?
Rajasekhar Kadambur's user avatar
18 votes
3 answers
1k 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 ...
Mark H's user avatar
  • 550
13 votes
2 answers
949 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 ...
Emma's user avatar
  • 382
10 votes
3 answers
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,...
KGM's user avatar
  • 2,265
8 votes
1 answer
1k 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 ...
Nikos Kazazakis's user avatar
8 votes
1 answer
2k 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 ...
KGM's user avatar
  • 2,265
8 votes
2 answers
1k 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 ...
Emma's user avatar
  • 382
6 votes
1 answer
222 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 $...
ooo's user avatar
  • 1,589
3 votes
2 answers
646 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 ...
tcokyasar's user avatar
  • 1,249
3 votes
1 answer
417 views

How to modify master problem and individual sub problems in column generation?

This is a follow-up post regarding this one. I deleted this new post once before, as I was unhappy with the formulation. I have the following basic nurse scheduling MILP, which tries to cover the ...
nflgreaternba's user avatar
2 votes
1 answer
2k views

How to linearize the product of a binary and a continuous variable? [duplicate]

Suppose we have a binary variable $b \in \{0, 1\}$ and a continuous (possibly negative) variable $y \in \mathbb{R}$. How can we linearize the product $b \cdot y$?
joni's user avatar
  • 1,572
2 votes
1 answer
193 views

Google OR Tools: Iterative Assignment Problem

This question is a Google OR-Tools specific implementation of recommendation from a previous question. In short, the movie theater problem encompasses assigning viewers to seats such that the distance ...
jbuddy_13's user avatar
  • 551
1 vote
1 answer
84 views

Will constraints in this LP be satisfied as equalities?

This is a follow up of my previous question. I repeat it below with an additional condition (in italics). Say $\mathbf{X}$ is a $n\times m$ matrix with no negative entries and such that every row and ...
Patricio's user avatar
  • 591
1 vote
1 answer
55 views

When will constraints in an LP be satisfied as equalities?

Say $\mathbf{X}$ is a $n\times m$ matrix with no negative entries. Assume further that every row and every column have at least a non zero element. Denote $\langle\mathbf{X}\rangle$ the cone spanned ...
Patricio's user avatar
  • 591
-2 votes
1 answer
75 views

Mixed Integer programming - Problem modelling coincidence restriction in scheduling match problem

I am trying to model and solve a problem for maximize audience of matches that must be scheduled in different slots (I am using python PulP library). Below I explain the problem and the model process ...
brtin_'s user avatar
  • 19
31 votes
4 answers
3k 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 ...
Rolf van Lieshout's user avatar
21 votes
5 answers
672 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 ...
Mertcan Yetkin's user avatar
20 votes
7 answers
3k views

Is there a Linear Programming Library that natively supports fractions instead of floating point arithmetic?

If one recalls how the Simplex method is taught by hand in most LP classes it takes place entirely in $\mathbb{Q}$. All operations yield exact fractions. For this reason I'm looking for linear ...
Sidharth Ghoshal's user avatar
18 votes
3 answers
2k views

TSP with revenue maximization

How to approach a traveling 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 ...
user23369's user avatar
  • 189
18 votes
2 answers
325 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 ...
JRogers97's user avatar
  • 181
17 votes
1 answer
4k 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?
LarrySnyder610's user avatar
14 votes
4 answers
687 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 ...
worldterminator's user avatar
12 votes
2 answers
1k 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 ...
Florian Pommerening's user avatar
11 votes
2 answers
806 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. ...
user3680510's user avatar
  • 3,655
11 votes
2 answers
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 ...
BarkingCat's user avatar
9 votes
2 answers
1k views

"Partial" Lagrangian Dual in LP

Consider the optimization problem \begin{align}\label{opt-lp}\tag{Primal} \begin{array}{cl} \underset{x \in \mathbb{R}^n}{\text{minimize}} & c^\top x \\ \text{subject to} & Ax = a \\ & Bx =...
independentvariable's user avatar
9 votes
3 answers
681 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 ...
Djames's user avatar
  • 1,143
9 votes
2 answers
543 views

Mixed-Integer Linear Programming With Free Variables

In the classic Mixed-Integer Linear Programming (MILP), the variables are fixed to be either integer or real. I am interested in the following MILP variant, where only one thing different from the ...
Samuel Bismuth's user avatar
9 votes
3 answers
4k 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
Lalitha Sundar Iyer S's user avatar
9 votes
2 answers
5k 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 ...
KGM's user avatar
  • 2,265