47 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, ...
user avatar
32 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 ...
user avatar
23 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 ...
user avatar
20 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{ ...
user avatar
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}$. ...
user avatar
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 ...
user avatar
19 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 \...
user avatar
  • 22.2k
18 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 $...
user avatar
  • 22.2k
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 ...
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, ...
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} ...
user avatar
  • 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 ...
user avatar
  • 10.2k
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 = ...
user avatar
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-...
user avatar
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^-$ ...
user avatar
  • 22.2k
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 $$
user avatar
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 ...
user avatar
11 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 ...
user avatar
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 + ...
user avatar
  • 22.2k
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 ...
user avatar
  • 22.2k
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 ...
user avatar
  • 2,665
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 ...
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 ...
user avatar
  • 201
10 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,...
user avatar
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 ...
user avatar
  • 1,307
10 votes

Is there a heuristic approach to the MILP problem?

You can solve the LP relaxation and round the resulting solution $x^*$, being careful to preserve the equality constraint. Then take $t=\max_c |\sum_n B_{n,c} x_n - d_c|$. There are lots of choices ...
user avatar
  • 22.2k
10 votes

Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint

Assuming that the $c_i$ and $q$ are all positive you may add one binary variable $y_i$ for every $i=1,\cdots,n$ then you may do \begin{align}c_i x_i &\geq q y_i \quad\forall i\\\sum_i y_i &\...
user avatar
10 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$.
user avatar
  • 29.6k
10 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 $...
user avatar
  • 22.2k
10 votes
Accepted

Which linearisation technique is correct?

They are equivalent except when $x_{i,g}=x_{j,g}=0$, in which case the second linearization incorrectly contributes $-d_{ij}$ to the objective. Assuming $d_{ij} \ge 0$, I recommend a third ...
user avatar
  • 22.2k

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