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
1 vote
0 answers
234 views

Problem of optimal solution generated with Pulp

I'm trying to use Pulp to solve VRP problem. Here is the model: ...
MAYA's user avatar
  • 129
2 votes
2 answers
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 ...
WaMIMO's user avatar
  • 33
4 votes
2 answers
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 ...
Morpheus's user avatar
  • 253
-2 votes
1 answer
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?
scouse_s's user avatar
2 votes
1 answer
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) ...
endeavor's user avatar
  • 145
2 votes
1 answer
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 ...
Davide Trono's user avatar
4 votes
3 answers
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 ...
Krypt's user avatar
  • 77
4 votes
0 answers
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$ ...
Ghulam Mohy-ud-din's user avatar
2 votes
1 answer
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}$. ...
OpenAtTheClose's user avatar
3 votes
1 answer
51 views

Formulating a non-multitask constraint [duplicate]

Suppose we have $n$ tasks. These tasks can not be executed at the same time i.e. every task should be finished before starting the next task. Every task ($i=0,\cdots,n$) has a day in which it starts $...
OpenAtTheClose's user avatar
6 votes
2 answers
227 views

Breaking symmetry of permutations in LIP

Setup I have a $N \times M$ matrix with integer values and I need to group it into $K$ groups (subject to constraints). Internally I work with a flattened 1D list as I don't see any benefits of using ...
armset's user avatar
  • 73
3 votes
1 answer
65 views

Is not the substitution method supposed to reduce the computation cost?

Is the substitution method expected to reduce the computation cost? We know it will reduce the number of variables and constraints. I mean by substitution method is to eliminate the equality ...
Hussein Sharadga's user avatar
2 votes
1 answer
48 views

Automatic Reformulation Tools For AML Programs

Are there any tools to transform programs written in an algebraic modeling language like GAMS,AMPL,... into a different formulation. E.g. there is a quadratic constraint $\sum_j b_i b_j = N, b \in \...
Lars Hadidi's user avatar
1 vote
0 answers
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 ...
kachi's user avatar
  • 11
1 vote
1 answer
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,...
jbuddy_13's user avatar
  • 551
2 votes
1 answer
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 ...
jbuddy_13's user avatar
  • 551
3 votes
0 answers
133 views

Linearize objective function with non-linear terms

I have a problem with linear constraints but in the objective function I want to have some linear terms along with a $x^2$ term. So it is like the following: $$\min \sum \limits _i \sum \limits _j (a[...
christouandr7's user avatar
2 votes
3 answers
593 views

How to find the index of the item, the first time appears?

How to formulate this problem as MIP: For example, we have the following vector of binary variables: $$ x= [0, 0, 0, 1, 0, 1, 1] $$ How to find out when the first "1" is recorded? For ...
Hussein Sharadga's user avatar
2 votes
2 answers
433 views

Simplex method for multiple objectives

I am a user of Google OR Tools, which can interface with many LP & MIP solvers, plus it's own SAT based constraint programming solver. My question, in the context of OR-Tools, is: how should I ...
jbuddy_13's user avatar
  • 551
1 vote
1 answer
112 views

ILP program to find a centrosymmetric Hadamard matrix

A question in mathoverflow asks if there exists a centrosymmetric Hadamard matrix of order 36. An $n \times n$ matrix $A = (a_{i,j})$ is centrosymmetric if: $$a_{i,j} = a_{n-i+1, n-j+1}, \space i=1,\...
Fabius Wiesner's user avatar
2 votes
1 answer
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 ...
BenBernke's user avatar
  • 175
1 vote
1 answer
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 ...
Pia MiA's user avatar
  • 392
0 votes
2 answers
109 views

How to create a transportation model with preferences

I have the following table ...
Fernando Martinez's user avatar
7 votes
3 answers
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, ...
TroyE219's user avatar
  • 105
3 votes
1 answer
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 ...
Fabius Wiesner's user avatar
0 votes
2 answers
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}...
Hussein Sharadga's user avatar
2 votes
1 answer
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 ...
Fernando Martinez's user avatar
2 votes
1 answer
183 views

Binary variable constraint for condition

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, ...
Bohdana Nevierova's user avatar
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 ...
Bohdana Nevierova's user avatar
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}\...
user avatar
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, ...
Bohdana Nevierova's user avatar
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 ...
Pia MiA's user avatar
  • 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 ...
Bohdana Nevierova's user avatar
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 \...
Fabius Wiesner's user avatar
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 ...
Fabius Wiesner's user avatar
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];$$ $$...
Fabius Wiesner's user avatar
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} \...
user avatar
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 $y$ is zero. For example, I have a model: $$ \...
Laura's user avatar
  • 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 ...
endeavor's user avatar
  • 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 ...
dmbeledo's user avatar
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: ...
TroyE219's user avatar
  • 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.$ ...
M.Badaoui's user avatar
  • 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/...
Fernando Martinez's user avatar
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&...
someone random's user avatar
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 ...
someone random's user avatar
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) ...
Pia MiA's user avatar
  • 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 ...
Miya's user avatar
  • 31
1 vote
3 answers
211 views

How to linearize this if-then constraint?

If $x \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?
Ajinkya Bankar's user avatar
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 ...
Alexander Mills's user avatar
2 votes
1 answer
230 views

Negative values for b-vector (RHS) for LP solvers

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 ...
Alexander Mills's user avatar

1
3 4
5
6 7
17