56 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, ...
Michiel uit het Broek's user avatar
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 ...
Michiel uit het Broek's user avatar
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 ...
LarrySnyder610's user avatar
25 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 \...
RobPratt's user avatar
  • 31.5k
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{ ...
Siong Thye Goh's user avatar
21 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}$. ...
Mark L. Stone's user avatar
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 $...
RobPratt's user avatar
  • 31.5k
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 ...
Discrete lizard's user avatar
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 ...
Mark L. Stone's user avatar
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, ...
Mark L. Stone's user avatar
15 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 ...
Kuifje's user avatar
  • 13.2k
14 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,...
LarrySnyder610's user avatar
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} ...
phil's user avatar
  • 141
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 = ...
Rolf van Lieshout's user avatar
13 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 \...
Kuifje's user avatar
  • 13.2k
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-...
Michael Trick's user avatar
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 ...
LarrySnyder610's user avatar
12 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 + ...
RobPratt's user avatar
  • 31.5k
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^-$ ...
RobPratt's user avatar
  • 31.5k
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 $$
Markus Seizinger's user avatar
12 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}^...
Kuifje's user avatar
  • 13.2k
11 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 ...
Marcus Ritt's user avatar
  • 2,715
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 ...
SecretAgentMan's user avatar
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$.
prubin's user avatar
  • 38.8k
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 $...
RobPratt's user avatar
  • 31.5k
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 ...
RobPratt's user avatar
  • 31.5k
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 ...
Discrete lizard's user avatar
10 votes
Accepted

How to linearize the product of two continuous variables?

As far as I know, there is no true way to linearize such constraints, as also stated in the answer given by Michael Trick. Let us therefore consider a piecewise linear approximation of the constraint $...
Michiel uit het Broek's user avatar
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 ...
Baykal's user avatar
  • 201
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 ...
prubin's user avatar
  • 38.8k

Only top scored, non community-wiki answers of a minimum length are eligible