# Questions tagged [linear-programming]

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

354 questions
Filter by
Sorted by
Tagged with
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
208 views

### Algorithm for workforce scheduling for call volumes

I am trying to solve a workforce scheduling and optimization problem. Available data: daily level forecasted call volumes, shift schedules, resource utilization at the aggregate level, AHT at ...
285 views

### How to add Binary Variable with condition in LP

Notation $\text{src}_{h,s},\text{dst}_{h,s},\text{ch}_{h,s}$ are constants. $a_{h,s},x_{i,j,s}$ are binary variables. $\text{wt}_{h,s}$ are continuous variables. Problem \begin{align}\min.&\...
880 views

### Linearization of objective function

Notation $\text{src}_{h,s},\text{dst}_{h,s},\text{ch}_{h,s}$ are constants. $a_{h,s},x_{i,j,s}$ are binary variables. $\text{wt}_{h,s}$ are continuous variables. Problem \begin{align}\min.&\...
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?
705 views

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

I have a dataframe like: ...
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 ...
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-...
151 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 ...
573 views

219 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 ...
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 ...
99 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
591 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 (...
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.
126 views

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 \\ & ... 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?... 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. 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 ... 2answers 212 views ### How to decide to write an objective function? I'm working on this problem: In the Njaba river basin, the available water was allocated for the purposes of consumption, irrigation, and electric power supply among three communities. The water ... 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? 1answer 919 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? 3answers 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 ... 1answer 287 views ### Simplest way to eliminate redundant constraints due to a new cut 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 ... 1answer 225 views ### How to get bounds on ILP optimal solution quality Often, ILP formulations are just too complicated to solve optimally in reasonable time. In those cases, you can still run a solver for some fixed time and simply take the best solution that the solver ... 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)
Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?