2.5 Mixed-Integer Linear Programming

While the simplicity of linear programming (and duality) make it an appealing tool, its modeling power is insufficient in many real-life applications (for example, there is no simple linear programming formulation of the BKP).

Fortunately, allowing the domain set to restrict one or more variables to integer values drastically extends the modeling power. The price we pay is that there is no guarantee that the problems can be solved in polynomial time.

Example: Recall the lemonade and lemon juice problem introduced in the previous section: there is a unique optimal solution at \([x,y]^{\!\top} = [ 1.2 , 1.6]^{\!\top}\) for a profit of \(6.8\).

But this solution requires the preparation of fractional units of lemonade and lemon juice. What if the number of prepared units needs to be integers?

The solution is to add integrality constraints: \[\begin{array}{|rrcrll} \max & 3x & + & 2y & \\ \text{s.t.} & x & + & 3y & \leq & 6 \\ & 2x & +& y & \leq & 4 \\ & x & & & \geq & 0 \\ & & & y & \geq & 0 \\ & x &,& y & \in & \mathbb{Z}. \\ \end{array}\]

This problem is no longer a linear programming problem; rather, it is an integer linear programming problem. Note that we can solve this problem via a case analysis. The second and third inequalities tell us that the possible values for \(x\) are \(0\), \(1\), and \(2\).

  • If \(x = 0\), the first inequality gives \(3y \leq 6\), implying that \(y \leq 2\). Since we are maximizing \(3x+2y\), we want \(y\) to be as large as possible; \([x,y ]^{\!\top} = [ 0,2 ]^{\!\top}\) satisfies all the constraints with an objective function value of \(4\).

  • If \(x = 1\), the first inequality gives \(3y \leq 5\), implying that \(y \leq 1\). Note that \([x, y ]^{\!\top} = [ 1, 1 ]^{\!\top}\) satisfies all the constraints with an objective function value of \(5\).

  • If \(x = 2\), the second inequality gives \(y \leq 0\). Note that \([x, y ]^{\!\top} = [ 2, 0 ]^{\!\top}\) satisfies all the constraints with an objective function value of \(6\).

Thus, \([x^*,y^* ]^{\!\top} = [ 2,0 ]^{\!\top}\) is an optimal solution. How does this compare to the solution of the LP problem of the previous section, both in terms of location of the solution and value of the objective function?

A mixed-integer linear programming problem (MILP) is a problem of minimizing or maximizing a linear function subject to finitely many linear constraints such that the number of variables are finite, with at least one of them required to take on integer values.

If all the variables are required to take on integer values, the problem is called a pure integer linear programming problem or simply an integer linear programming problem. Normally, we assume the problem data to be rational numbers to rule out pathological cases.

Many solution methods for solving MILPs have been devised and some of them first solve the linear programming relaxation of the original problem, which is the problem obtained from the original problem by dropping all the integrality requirements on the variables.

For instance, if (MP) denotes the following mixed-integer linear programming problem: \[\begin{array}{|rrcrcrlll} \min & x_1 & & & + & x_3 \\ \mbox{s.t.} & -x_1 & + & x_2 & + & x_3 & \geq & 1 \\ & -x_1 & - & x_2 & + & 2x_3 & \geq & 0 \\ & -x_1 & + & 5x_2 & - & x_3 & = & 3 \\ & x_1 & , & x_2 & , & x_3 & \geq & 0 \\ & & & & & x_3 & \in & \mathbb{Z}. \end{array}\] then the linear programming relaxation (P1) of (MP) is: \[\begin{array}{|rrcrcrlll} \mbox{min} & x_1 & & & + & x_3 \\ \text{s.t.} & -x_1 & + & x_2 & + & x_3 & \geq & 1 \\ & -x_1 & - & x_2 & + & 2x_3 & \geq & 0 \\ & -x_1 & + & 5x_2 & - & x_3 & = & 3 \\ & x_1 & , & x_2 & , & x_3 & \geq & 0. \end{array}\]

Observe that the optimal value of (P1) is a lower bound for the optimal value of (MP) since the feasible region of (P1) contains all the feasible solutions to (MP), thus making it possible to find a feasible solution to (P1) with objective function value which is better than the optimal value of (MP).

Hence, if an optimal solution to the linear programming relaxation happens to be a feasible solution to the original problem, then it is also an optimal solution to the original problem. Otherwise, there is an integer variable having a nonintegral value \(v\).

What we then do is to create two new sub-problems as follows:

  • one requiring the variable to be at most the greatest integer less than \(v\),

  • the other requiring the variable to be at least the smallest integer greater than \(v\).

This is the basic idea behind the branch-and-bound method. We now illustrate these ideas on (MP). Solving the linear programming relaxation (P1), we find that \(\mathbf{x}' = \frac{1}{3}[0,2,1]^{\!\top}\) is an optimal solution to (P1). Note that \(\mathbf{x}'\) is not a feasible solution to (MP) because \(x'_3\) is not an integer. We now create two sub-problems (P2) and (P3).

(P2) is obtained from (P1) by adding the constraint \[x_3 \leq \lfloor x'_3\rfloor\] and (P3) is obtained from (P1) by adding the constraint \[x_3 \geq \lceil x'_3\rceil.\footnote{\(\lfloor a \rfloor\) denotes the \textbf{floor of} \(a\) and \(\lceil a \rceil\) denotes the \textbf{ceiling of} \(a\).}\] Hence, (P2) is the problem \[\begin{array}{|rrcrcrlll} \min & x_1 & & & + & x_3 \\ \text{s.t.} & -x_1 & + & x_2 & + & x_3 & \geq & 1 \\ & -x_1 & - & x_2 & + & 2x_3 & \geq & 0 \\ & -x_1 & + & 5x_2 & - & x_3 & = & 3 \\ & & & & & x_3 & \leq & 0 \\ & x_1 & , & x_2 & , & x_3 & \geq & 0, \end{array}\] and (P3) is the problem \[\begin{array}{|rrcrcrlll} \min & x_1 & & & + & x_3 \\ \text{s.t.} & -x_1 & + & x_2 & + & x_3 & \geq & 1 \\ & -x_1 & - & x_2 & + & 2x_3 & \geq & 0 \\ & -x_1 & + & 5x_2 & - & x_3 & = & 3 \\ & & & & & x_3 & \geq & 1 \\ & x_1 & , & x_2 & , & x_3 & \geq & 0. \end{array}\]

Note that any feasible solution to (MP) must be a feasible solution to either (P2) or (P3). Using the help of a solver, one can see that (P2) is infeasible. The problem (P3), however, has an optimal solution at \(\mathbf{x}^* = \frac{1}{5}[0,4,5]^{\!\top}\), which is also feasible for (MP). Hence, \(\mathbf{x}^*\) is an optimal solution of (MP).

In many instances, there are multiple choices for the variable on which to branch, and for which sub-problem to solve next. These choices can have an impact on the total computation time. Unfortunately, there are no hard-and-fast rules at the moment to determine the best branching path. This in area of ongoing research.

2.5.1 Cutting Planes

Difficult MILP problems often cannot be solved by branch-and-bound methods alone. A technique that is typically employed in solvers is to add valid inequalities to strengthen the linear programming relaxation.

Such inequalities, known as cutting planes, are known to be satisfied by all the feasible solutions to the original problem but not by all the feasible solutions to the initial linear programming relaxation.

Example: consider the following PILP problem: \[\begin{array}{|rrcrlll} \min & 3x & + & 2y \\ \text{s.t.} & 2x & + & y & \geq & 1 \\ & x & + & 2y & \geq & 4 \\ & x & , & y & \in & \mathbb{Z}. \end{array}\]

An optimal solution to the linear programming relaxation is given by \[[x^+, y^+ ]^{\!\top} = \frac{1}{3}[ -2,7 ]^{\!\top}.\] Note that adding the inequalities \(2x + y \geq 1\) and \(x + 2y \geq 4\) yields \(3x + 3y \geq 5\), or equivalently, \[x + y \geq \frac{5}{3}.\] Since \(x+y\) is an integer for every feasible solution \([x,y ]^{\!\top}\), \(x + y \geq 2\) is a valid inequality for the original problem, but is violated by \([x^+, y^+ ]^{\!\top}\). Hence, \(x + y \geq 2\) is a cutting plane.

Adding this to the linear programming relaxation, we have \[\begin{array}{|rrcrlll} \min & 3x & + & 2y \\ \text{s.t.} & 2x & + & y & \geq & 1 \\ & x & + & 2y & \geq & 4 \\ & x & + & y & \geq & 2. \end{array}\] which, upon solving, yields \([x^*,y^* ]^{\!\top} = [ -1,3 ]^{\!\top}\) as an optimal solution.

Since all the entries are integers, this is also an optimal solution to the original problem. In this example, adding a single cutting plane solved the problem. In practice, one often needs to add numerous cutting planes and then continue with branch-and-bound to solve nontrivial MILP problems.

Many methods for generating cutting planes exist – the problem of generating effective cutting planes efficiently is still an active area of research [22].

References

[22]
G. Cornuéjols, Valid inequalities for mixed integer linear programs,” Math. Program., vol. 112, no. 1, pp. 3–44, Mar. 2008.