# Questions tagged [linear-programming]

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

849 questions
Filter by
Sorted by
Tagged with
726 views

### Running a linear programming model to maximize binned predictions

I have a dataframe like: ...
• 203
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 ...
• 1,859
563 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-...
• 133
181 views

### Structural Optimization

Currently, I am working on a problem in which I need to use MILP to model equilibrium equations in a lightweight structure. Although this is an application based question, I wondered if there is a ...
• 8,677
2k views

• 83
657 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 ...
• 379
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 ...
• 550
169 views

### Computational complexity to compute an IIS

How hard is it to compute an irreducible infeasible subset (IIS) for a linear program? What about an integer program (e.g., removing the integrality constraint on a single variable may be enough to ...
• 2,117
533 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 ...
691 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 ...
967 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 ...
441 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 ...
• 293
750 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 ...
• 453
505 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) ...
• 1,895
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 ...
• 1,026
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.
• 3,469
251 views

12k 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$?
17k 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$?
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 ...
• 13.1k
773 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 ...