55
votes
Accepted
How to linearize the product of two binary variables?
This scenario can be linearized by introducing a new binary variable $z$ which represents the value of $x y$. Notice that the product of $x$ and $y$ can only be non-zero if both of them equal one, ...
- 2,461
38
votes
Accepted
How to linearize the product of a binary and a non-negative continuous variable?
Suppose we can give a finite upper bound for $y$ called $M$. Then this constraint can easily be linearized by using the so-called big $M$ method. We introduce a new variable $z$ that should take the ...
- 2,461
26
votes
Accepted
How to formulate (linearize) a maximum function in a constraint?
(I'm going to change $c$ to $x$ in my answer, since $c$ is usually used for cost coefficients, not decision variables.)
We want a set of constraints that enforces $X = \max\{x_1,x_2\}$. Define a new ...
- 13k
24
votes
How to linearize the product of two binary variables?
It is worth noting that this formulation can be derived somewhat automatically by writing the logical proposition in conjunctive normal form:
\begin{align*}
& z \iff x \wedge y \\
& \left(z \...
- 29.8k
23
votes
Accepted
How to minimize an absolute value in the objective of an LP?
Alternatively, by observing that $|c \cdot x|= \max \{c^T x, -c^T x\}$,
$$\min_x |c\cdot x| \text{ subject to } Ax \le b$$
can be rewritten as
$$\min_x \max \{c^T x, -c^T x\} \text{ ...
- 912
20
votes
Accepted
Linearize or approximate a square root constraint
This can be handled as an MISOCP, Mixed-Integer Second Order Cone problem. The leading commercial MILP solvers can also handle MISOCP.
Specifically, due to $x_{ij}$ being binary, $x_{ij}^2 = x_{ij}$. ...
- 12.8k
20
votes
Accepted
How to linearize membership in a finite set
First, some special cases:
If $S=\{c\}$, fix $x=c$.
If $S=\{0,1\}$, declare $x$ to be binary.
If $S=\{a,b\}\not=\{0,1\}$, introduce binary variable $y$ and impose linear constraint $x=a(1-y)+by$.
If $...
- 29.8k
19
votes
Accepted
Modeling floor function exactly
It is not possible to model the floor function as a constraint without modeling strict inequality. To prove this, I will show how the floor function can be used to model strict inequalities.
Thanks ...
- 1,482
17
votes
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
Here is a nice, succinct,and easy to understand reference for how to do all this and more. Answers to many future questions can be handled by referencing the appropriate section number in this ...
- 12.8k
16
votes
Nonlinear integer (0/1) programming solver
Option 1: Submit as is to a solver which can globally optimize MIQPs having non-convex objective, and which might reformulate to a linearized MILP model under the hood. Such solvers include CPLEX, ...
- 12.8k
14
votes
Nonlinear integer (0/1) programming solver
Maybe I am missing something but it looks like there is no need for a library:
\begin{align}
\sum_i \sum_j \sum_k x_{ji} y_{kj} cost(i,k)&=\sum_i \sum_j x_{ji} \sum_k y_{kj} cost(i,k)
\end{align}
...
- 141
14
votes
Accepted
MILP Penalty Function Only for Negative Values
If $x$ denotes your free variable, you can penalize the term $f(x)=\max\{-x,0\}$ in your objective function, which you can linearize by replacing it with a variable $y$, and constraints $y\ge -x, y\ge ...
- 12.8k
13
votes
How to linearize min function as a constraint?
Here is an answer that uses the same approach as in this answer, but converted from $\max\{\cdot,\cdot\}$ to $\min\{\cdot,\cdot\}$. I'll write the constraint in a more general form:
$$X = \min\{x_1,...
- 13k
13
votes
Accepted
Why does a Max constraint work, but this non-negativity constraint does not?
A rigorous way to look at this problem is to consider the polyhedra corresponding to your constraints (I linearized the 'max' for the second one):
$$P_1 = \left\{(x_t,x_{t-1},y_{t-1},z_{t-1}): x_t = ...
- 2,295
12
votes
How to linearize the product of two continuous variables?
Unlike cases where one or both of the $x$ and $y$ are binary, you won't be able to truly (i.e. exactly) linearize this. https://stackoverflow.com/questions/49021401/how-to-linearize-the-product-of-...
- 2,362
12
votes
Accepted
How to linearize a constraint with a maximum or minimum in the right-hand-side?
Basically the condition is saying, $z$ must be between $x$ and $y$, regardless of whether $x \le y$ or $y \le x$.
Here's a method that involves a new binary variable and a big-$M$.
Let $w$ a binary ...
- 13k
12
votes
MILP Penalty Function Only for Negative Values
You do not need to introduce an indicator variable. Suppose $x$ is your free variable. Introduce nonnegative variables $x^+$ and $x^-$, replace $x$ with $x^+-x^-$ throughout, and penalize $x^-$ ...
- 29.8k
12
votes
Accepted
Linearizing this absolute difference objective function $\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$
As you are minimizing $y_{ij}$, it is sufficient to use
$$
y_{ij} \geq x_i - x_j \quad \forall i, j \\
y_{ij} \geq x_j - x_i \quad \forall i, j
$$
- 136
12
votes
Accepted
Rewriting if-then constraints of binary summations
In conjunctive normal form, you want to enforce:
\begin{align}
&\quad \quad \quad\bigvee_b x_{i,j}^{a,b} \implies \bigwedge_{u,v}\neg y_{u,v}^{a} \quad&\forall a,i,j\\
&\equiv \quad\neg \...
- 12.8k
11
votes
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
I recommend Formulating Integer Linear Programs: A Rogues' Gallery:
The article[1] is very accessible, clear, and has multiple examples of using binary variables to achieve logical constraints. Full ...
- 1,885
11
votes
Accepted
Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint
You can do this with no new variables. Let $S=\{k:c_k \ge q\}$ and add the constraint $\sum_{k\in S}x_k \ge 1$.
- 37.5k
11
votes
Linear programming: objective function with "buckets"
1. Your suggested approach : quadratic program
Here are the details of your suggested approach. It results in a quadratic objective.
Let binary variable $y_{i,b}$ indicate whether $A_i$ is in bucket $...
- 29.8k
11
votes
Accepted
Linearize x different of y in ILP
I recommend a third approach, similar to yours but linear:
\begin{align}
x + 1 - y &\le M_1 z \tag1 \\
y + 1 - x &\le M_2 (1-z) \tag2 \\
\end{align}
Constraint $(1)$ enforces $z=0 \implies x + ...
- 29.8k
11
votes
Accepted
How to linearize a constraint with a maximum of a linear function
You can model the logical implication $$Cx < d \implies \bigvee_{i=1}^m \left(a_i^T x \ge b_i\right)$$
by introducing $m+1$ binary variables $y_i$, where $i\in\{0,\dots,m\}$, and linear constraints
...
- 29.8k
11
votes
Accepted
Is there a better way of defining a constraint on positive integer variables such that no two variables are the same and are uniquely assigned a value
Introduce binary variables $y_{ij}\in \{0,1\}$ that take value $1$ if and only if $x_i$ is assigned to value $j\in \{1,...,N\}$, and use the following constraints:
\begin{align}
x_i &= \sum_{j=1}^...
- 12.8k
10
votes
The effect of choosing big M properly
The bigger the big-M is, more likely the numerical issues will happen with solvers.
If you have right hand sides around $10^{10}$ and objective function coefficients in the range of $10^{-2}$, then ...
- 201
10
votes
How to minimize an absolute value in the objective of an LP?
This is possible by introducing 2 new variables, $t_1,t_2$, and adding a few constraints:
$\begin{align}
\min t_1+t_2 \quad \text{s.t.} \quad t_1-t_2 &= c\cdot x\\
t_1&\geq 0 \\
t_2&\geq ...
- 1,482
10
votes
McCormick envelopes and nonlinear constraints
For real $x\in[l,u]$ and binary $b\in\{0,1\}$ the McCormick envelope gives you bounds on $w=xy$
$$\begin{align}
lb & \leq w \leq ub,\\
ub+x-u& \leq w\leq x+lb-l.
\end{align}$$
By case ...
- 2,705
10
votes
QA techniques for optimization problem coding
The following suggestion is conjecture (I don't do it myself) and certainly not guaranteed to prevent all possible errors. Develop your initial model, run it against multiple scenarios, and store the ...
- 37.5k
10
votes
Accepted
How to linearize a constraint with max
Welcome to OR.SE! If you're looking to enforce $$\max\limits_{pcj}X_{pwcj} \leq L_{wk}, \ \forall w,k$$ then simply using the constraint $$X_{pwcj} \leq L_{wk}, \ \forall p,w,c,j,k$$ will do the ...
- 1,317
Only top scored, non community-wiki answers of a minimum length are eligible