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
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
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
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
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
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
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
24 votes
4 answers
5k 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. ...
Gehhilfe's user avatar
  • 453
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
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
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
23 votes
1 answer
346 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 ...
Rolf van Lieshout's user avatar
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
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
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
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
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
19 votes
2 answers
8k views

Is Linear Programming as Useful as it was 50 Years Ago?

Based on the plethora of advancements in optimization algorithms and computer technology that has occurred in the past 50 years - is Linear Programming today as "Powerful" and "...
stats_noob's user avatar
  • 1,831
19 votes
4 answers
1k views

PhD-level textbooks on linear programming

My graduate Linear Programming class uses Bertsimas & Tsitsiklis's Introduction to Linear Optimization. Are there any alternative texts that I could use to supplement this textbook (mainly the ...
tiger123's user avatar
  • 191
19 votes
2 answers
429 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 ...
abc's user avatar
  • 293
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
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
490 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) ...
SecretAgentMan's user avatar
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
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
3 answers
3k views

How Close Is Linear Programming Class to What Solvers Actually Implement for Pivot Algorithms

As part of a final project for my linear programming course, I have been asked to discuss implementations of pivot algorithms, including which combinations of the ideas we have talked about in class ...
Sean Kelley's user avatar
17 votes
5 answers
744 views

Presolve is cutting down a lot of binary variables. Should I rethink my formulation?

I built my model on Python and am passing it to Gurobi to solve the problem. The presolve phase of Gurobi cuts down ~80% of the integer/binary variables and I am wondering if I should rethink my ...
Abhishiekh Ramesh's user avatar
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
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
17 votes
1 answer
3k views

Duality in mixed integer linear programs

I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
rasul's user avatar
  • 2,140
17 votes
2 answers
5k views

Tool to get dual problem from any linear optimization problem (.lp)

Is there a tool that reads any linear optimization problem (for example an .lp or .mps file), converts it to the dual problem and prints the dual problem?
JaBe's user avatar
  • 491
16 votes
2 answers
1k 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.
Richard's user avatar
  • 3,459
16 votes
1 answer
1k 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 ...
Mats Granvik's user avatar
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
15 votes
2 answers
2k 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?
A.Omidi's user avatar
  • 8,882
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
15 votes
3 answers
1k 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 ...
ephemeral's user avatar
  • 897
15 votes
2 answers
346 views

Search approach to solve optimization problem with only a minimum where time series get scaled

Currently, I am working on a relatively simple optimization problem: There is a set of time series (red) that get summed up to a cumulated time series (blue). The red time series have different forms ...
Emma's user avatar
  • 382
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
15 votes
1 answer
936 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 ...
Orlando Rivera Letelier'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
14 votes
1 answer
251 views

Is the optimal objective of a linear program continuous in its right-hand-side?

Consider a linear program $$f(b)=\min_{x}\{c^\top x: A x = b, x\geq 0\}$$ (assume it is feasible and bounded for all $b$). My understanding is that $f(b)$ is a convex piecewise linear function of $b$ ...
k88074's user avatar
  • 1,661
13 votes
3 answers
599 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 ...
Yinan's user avatar
  • 379
13 votes
5 answers
516 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 ...
Mertcan Yetkin's user avatar
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
13 votes
2 answers
550 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-...
Colin M's user avatar
  • 133
13 votes
1 answer
823 views

LP how to sum up positive free variables and negative free variables separately?

For an LP problem where $x_1,\dots,x_n$ are free variables (which may take positive or negative values), I want to bound the sums of $a_i\cdot x_i$ where $x_i>0$, and where $x_i<0$. I suspect ...
Henry's user avatar
  • 542
13 votes
2 answers
2k 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 ...
Borelian's user avatar
  • 803
12 votes
5 answers
2k views

Dividing machines into groups of equal sizes so that each group has approximately same productivity

I have set of machines with varying productivity. I want put the machines in different groups so that the groups have approximately equal productivity. Lets say, we have $M$ machines. and we want to ...
KGM's user avatar
  • 2,265

1
2 3 4 5
17