# Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

352 questions
Filter by
Sorted by
Tagged with
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.
973 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 ...
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$?
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$?
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 ...
590 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 (...
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 ...
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 ...
4k 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. ...
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 ...
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 ...
321 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 ...
296 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 ...
788 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?...
425 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 ...
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?
947 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 ...
277 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 ...
371 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) ...
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 ...
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 ...
473 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 ...
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 ...
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 ...
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 ...
739 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?
240 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.
916 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?
917 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 ...
478 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 ...
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 ...
253 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 ...
576 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 ...
559 views

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 ...
1k 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?
285 views

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 ... 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? 2answers 998 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).... 1answer 393 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)$$3answers 2k 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 ... 5answers 248 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 ... 2answers 408 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 ... 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 ... 2answers 334 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-... 1answer 318 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 ... 2answers 977 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 ... 1answer 94 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 ... 1answer 126 views ### How to reduce recursion when using Gomory cutting planes to solve an integer program? Consider the following simple integer program$$\begin{array}{ll} \text{maximize} & 3 x_1 - x_2\\ \text{subject to} & 3x_1 - x_2 \leqslant 3 \\ & -5x_1 - 4x_2 \leqslant -10 \\ & ...
I have a polyhedral set for constraining $x$: \begin{align} \mathcal{P} = \{x \in \mathbb{R}^n_{+} : \ Dx \leq d \} \end{align} where $D \in \mathbb{R}^{m \times n}, d \in \mathbb{R}^m$. I find the ...