Some linearization techniques in linear programming

Linear programming (LP) is the minimization of a linear form on a polyhedron¹. The standard form of an LP is

where \(c \in \mathbb{R}^n\), \(b \in \mathbb{R}^m\), and \(A\) is the \(m{\times}n\)-matrix of coefficients. LP has been shown² to be fell into the computational complexity class P. It is hard sometimes to cast the problem as an LP. It such situation we may need to add some integer or binary variables. This leads us to an MILP (mixed integer LP) problem, which includes ILP (integer variables only), BLP (binary variables only), or LP as a special case. MILP is another fundamental problem in mathematical programming, and has been shown to be NP-hard².

Some linearization techniques

Following are some linearization techniques which transform nonlinear terms to linear forms, which may involve additional (usually integer or binary) variables.

1. Max-min functions

The term \(X = \max\{x_{1}, x_{2}\}\) can be linearized by introducing an additional binary decision variable \(y\) and using the so-called big-\(M\) method.

The following constraints³ enforce the definition of \(X\) and \(y\):

Similarly, the term \(X = \min\{x_{1}, x_{2}\}\) can be linearized as follows⁴

The value of \(M\) has to be carefully chosen. See more here.

2. Rounding functions: Ceil and Floor

A floor function \(y = \lfloor x \rfloor\) can be linearized as⁵

Similarly, a ceiling function \(y = \lceil x \rceil\) can be linearized as

3. Product of two binary variables

A product term \(x_{1}x_{2}\), where \(x_{1}, x_{2} \in \{0,1\}\) occuring in a linear program can be replaced by an auxiliary continuous variable \(y \in [0,1]\) and the following so-called Fortet’ constraints⁶:

4. Product of multiple binary variables

The above technique could also be extended to the product of multiple variables: \(y_\mathcal{I} = \prod_{i \in \mathcal{I}} x_i\), where \(x_i \in \{0,1\}\), \(\forall i \in \mathcal{I}\). The linearization constraints are²

5. Product of a binary and a non-negative continuous variable

Suppose we have a binary variable \(x \in \{0,1\}\) and a non-negative continuous variable \(y \in \mathbb{R_+}\). The product \(z = xy\) is thus

\(z\) can be linearized by using the big-\(M\) method⁷,

where \(z \in \mathbb{R_+}\), \(M\) is a sufficiently large value so that it would not be part of any feasible solution.

6. Activate or deactivate a specific constraint

The Big-\(M\) method can also be used to activate or deactivate a specific constraint as follows⁸

• LEQ (less-than-or-equal-to) constraint (i.e., \(Ax \leq b\)): It could be activated/deactivated by using an additional variable \(y \in \{0,1\}\) as

  \[Ax \leq b + M(1 − y).\]

  Here if \(y = 0\) the constraint \(Ax \leq b\) is deactivated, and otherwise if \(y = 1\).

• GEQ (greater-than-or-equal-to) constraint (i.e., \(Ax \geq b\)): Then we need the following

  \[Ax \geq b − M(1−y).\]

  If all coefficients in \(A\) are nonnegative, we can instead write

  \[Ax \geq b(1−y),\]

  which is tighter than the previous constraint.

• Equality constraint (i.e., \(Ax = b\)): Then the following constraints are used

  \[\begin{align*} Ax & \leq b + M(1 − y), \\ Ax & \geq b − M(1 − y) \end{align*}\]

7. Preventing loops in linear directed graph

Let \(x_{ij}\) be a binary variable indicating that the arc \((i,j)\) is present, the constraint

will prevent creating loops in a linear directed graph⁹.

See more:

• How to specify an IF-THEN constraint with an Integer Linear Programming (ILP) solver: 1, 2
• How to specify an unequal constraint with an Integer Linear Programming (ILP) solver
• In an integer program, how I can force a binary variable to equal 1 if some condition holds?

References