# Questions tagged [linear-programming]

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

802 questions
Filter by
Sorted by
Tagged with
1 vote
234 views

### Problem of optimal solution generated with Pulp

I'm trying to use Pulp to solve VRP problem. Here is the model: ...
• 129
279 views

### An if-then-else logic to construct constraint

I was hoping to get some help in modelling the following logic, I know that it would use some kind of Big M formulation but I am not sure how. Thank you in advance! $\Omega$ is a set whose values are ...
• 33
377 views

### What happens to the dual and primal feasibility when a constraint is removed after finding an optimal solution?

Assuming I had solved the a problem to optimality, I want to remove a constraint. What happens to primal feasibility? What happens to dual feasibility? How to solve this new problem efficiently? My ...
• 253
101 views

### Converting a quadratic objective function in piecewise linear function

The objective function is of the form: $max$ $x^2/2+y^2/2+z^2/2$ I would like to convert it to piecewise linear function. How do I achieve that?
187 views

### Multiple absolute values with multiple variables in an LP

Assume that we have a LP with the constraint $$\sum_{j} \left(c_j x_j + |c_j x_j - \alpha_j + \beta_j|\right) \leq y$$ and $$\alpha_j + \beta_j \leq \lambda_j$$ for all $j$, where the (positive) ...
• 145
111 views

### Correct way to set a quadratic constraint Xpress

I'm implementing on Xpress a problem with different solution proposed on a paper. The idea is to decompose a matrix $X$ into a convex sum $\sum_{t}\lambda_t M^{(t)}$, where each $M^{(t)}$ has only ...
• 123
332 views

### Existence of extreme points in primal and dual LP

If the nonempty feasible set of a primal LP has extreme points does its dual also have extreme points? I know that a standard form LP (nonempty) always has extreme points. But I am not sure if we can ...
• 77
100 views

### How to linearize or convexify a constraint with a square root of sum of two variables?

Here is the constraint: $$\text{Pa} + \text{Pb}=a + b \sqrt{\text{Ir}^2 +\text{Ii}^2} + c (\text{Ir}^2 +\text{Ii}^2)$$ Here $\text{Pa}, \text{Pb}, \text{Ir},$ and $\text{Ii}$ are variables. $a, b, c$ ...
474 views

### If/then constraint formulation

Let's assume we have event $i=1,2,\cdots,k$, denoted as $\text{event}_i$. We know for a fact that $\text{event}_i$ is smaller then $\text{event}_{i+1}$ i.e., $\text{event}_i \leq \text{event}_{i+1}$. ...
51 views

• 153
1 vote
89 views

### Polynomial time separation and optimization for an LP with exponential columns and rows?

We know the fundamental theorem on the equivalence of separation and optimization: an optimization problem can be solved in a polynomial time if and only if there is a polynomial time separation ...
• 11
1 vote
211 views

### Applying weights to assignment problems for linear MIP solvers

In previous posts, A & B, I posed the Movie Theater Problem. In short, the movie theater problem encompasses assigning viewers to seats such that the distance between viewers is maximized, however,...
• 551
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 ...
• 551
133 views

615 views

### Optimization problem with if condition as constraint

I am trying to solve an optimization problem where the constraint contains absolute values and I am not sure how I can express this in a 'Pyomo-friendly' way. Consider the following optimization ...
• 175
1 vote
105 views

### Are there any performance overheads if we specify Pyomo Constraints in different way?

I am interested to know whether there are any performance overheads for specifying Pyomo Constraints in different ways. For example, which of the two ways is better? I am trying to speed up one of my ...
• 392
109 views

### How to create a transportation model with preferences

I have the following table ...
495 views

### Profit Maximization LP and Incentives Scenarios

I wrote a profit maximization LP with inventory, component usage, production, and machine hours constraints. When I optimize the model, it solves as expected. When applied towards a business case, ...
• 105
148 views

### Big LP program to be submitted to NEOS Server (union-closed sets conjecture)

I have a big LP program with around $91,000$ variables and $2,900,000$ constraints. They are all binary variables, but I want to try also relaxing the problem putting $0 \le x \le 1$ bounds. I am not ...
210 views

### How to formulate "If statement with equality constraints" using big m? [duplicate]

How to convert this one to a linear program: if $x=1$ then $B=1$; otherwise, $B=0$. If I use the Big M method: \begin{align}x&\ge1-M(1-B)\\x&\le1+M(1-B)\end{align} A) with $B=1$: \begin{align}...
115 views

### How to add batch constraint to an optimization problem

I have one variable called OS which is the number of orders. And I have a variable nt which is the number of trucks. And 20 orders can fit into one truck. I am not ...
I am trying to solve the following task: If $x=1$ or $y=0$ then $z=0$ My approach: If $z=0$ then $x+y \le 2 + Mz \implies x+y \le 2+2z \quad$ where $M = 2$ If $z=1$ then $x+y=1 \\ \implies x+y \le 1, ... 0 votes 1 answer 84 views ### Conditional constraint for binary variables I would appreciate any help to solve the following task: If$y=1$then$x_i=1$for at least$k$of the possible indices$i\in\{1,\cdots,n\}$where$k$and$n$are parameters,$x$is a binary variable ... 2 votes 2 answers 73 views ### How to model this?$i$is a set$1$to$n$.$j$is a set$1$to$m$.$j$and$k$are from the same set such that$j\neq k$.$c_{ij}$is a parameter.$x_{ij}$and$y_{j}$are binary variables. How to model: If $$c_{ij}\... 5 votes 2 answers 410 views ### Binary variable constraint The task is to ensure that if x_i = 1 for at least k of the possible indices i in \{1,...,n\} then y = 1, where k and n are parameters, x is a binary variable vector with n elements, ... 0 votes 1 answer 163 views ### Rolling Horizon approach for solving a job scheduling problem I am trying solve a scheduling problem adopting a rolling horizon approach. I have developed an Integer programming model and seek to speed up execution. I am seeking advice on beginner level ... • 392 3 votes 1 answer 297 views ### Binary variables constraint What constraints would you write to ensure that if x = 1 then y = 0 where x, y are binary variables? Until now I only learnt how to build the constraint with 3 binary variables, therefore the ... 4 votes 1 answer 76 views ### Another difficult constraint for an ILP How can I add to this ILP with all binary variables (again related to this question):$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}\sum_{i=1}^{n-1-h} a_{k,i} \ge \lfloor (n-1)/2\rfloor \qquad \... 5 votes 3 answers 710 views ### Constraint for two binary vectors to be different If I have a matrix$A$of binary variables$a_{i,j}$,$1 \le i \le n$,$1 \le j \le m$, how can I enforce in an Integer Linear Program with binary variables, the condition that every two columns must ... 4 votes 1 answer 191 views ### Difficult linearization of a constraint My previous question was about this ILP with all binary variables: $$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$ $$\sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];$$ $$... 3 votes 2 answers 103 views ### How to model if-then? i is a set 1 to n. j is a set 1 to m. j and k are from the same set such that j\neq k. c_{ij} is a parameter. x_{ij} is a binary variable. How to model: If$$c_{ij}\cdot x_{ij} \... 2 votes 2 answers 279 views ### How can I include a penalty to my (linear) model? Is it possible in a linear model to include a penalty if both variables$x$and$y$are greater than zero? I would like to have no penalty, if$x$OR$yis zero. For example, I have a model: $$\... • 79 2 votes 1 answer 99 views ### Modify the network model to accommodate multiple vehicles Given a directed network (or graph) G = (V,E) with each edge e_{ij} having a non-negative cost as the travel time from i to j. Each node has an associated demand d_i. If the demand is ... • 145 3 votes 1 answer 294 views ### Linearize objective function in MILP I have an objective function that I want to linearize but want to confirm that I'm doing it correctly. There are some constraints that are linear in x but they're unimportant for the problem. The ... • 45 1 vote 0 answers 46 views ### Blending Problem Without Percents and Varying Units of Measure I'm attempting to write a blending/production planning type linear program but am struggling due to the complexity of the manufacturing process. I am formulating the problem as such: Objective: ... • 105 3 votes 3 answers 611 views ### Gurobi - Python: is there a way to express "OR" in a constraint? I'm new to Gurobi in Python and I am wondering if there is way to express/code "or" in the following constraint, where x_i are binary variables: x_i-x_i*x_{i-1} =0 OR x_i*x_{i+1} =1. ... • 185 0 votes 1 answer 85 views ### How to build a deterministic optimization model for the following fc I am not sure how to model this. I have like this table that has dates and orders  dates order 1/16/2021 12 units 1/21/201 13 unit 1/27/2021 21 1/29/2021 14 2/23/... 2 votes 2 answers 198 views ### Proof on Degenerate LP program do all degenerate LP have have an equivalent non degenerate LP? for example the following is a degenerate LP$$A=\begin{bmatrix}1&0&0&0&1&1&0\\0&1&0&1&0&1&... 3 votes 3 answers 342 views ### Question regarding primal Simplex method Given the following degenerate optimization problem \begin{align}\min&\quad c^Tx\\\text{s.t.}&\quad Ax=b,\\&\quad x\ge 0\end{align} Using primal simplex algorithm (either revised or ... 1 vote 0 answers 327 views ### Resetting Pyomo model after computation I am aware that the types provided by pyomo are immutable and often cause issues when we feed the same data twice in consecutive computations (e.g. when trying to solve an instance a couple of times) ... • 392 3 votes 2 answers 176 views ### Find all pivots that the simplex algorithm visited, i.e., the intermediate solutions, using Python For my research, I am interested in finding the trajectory outlined by the pivots along the way of optimizing an LP problem, but I only know how to use Python PuLP to obtain the optimal solution. Is ... • 31 1 vote 3 answers 211 views ### How to linearize this if-then constraint? Ifx \ge 1$then$y = y + x$. And, if$x \le 0$then$y = y$, where$x$and$y$are non-negative integer decision variables. I am using GLPK solver. How do I linearize this if-then constraint? 1 vote 1 answer 124 views ### Avoiding degeneracy in an LP formulation I assume that "less than or equal to"$\left( \leq \right)$and "greater than or equal to"$\left( \geq \right)\$ constraints avoid degeneracy because each of those has at least one ...
Say we have a constraint: $$x-2y+z \ge 3 \tag{1}$$ Typically to actually solve it, we would need to introduce a surplus variable and an artificial variable: $$x-2y+z-s+a=3 \tag{2}$$ However, is it ...