Introduction to integer linear programming

Recall the problem on lemonade and lemon juice from Week 1 restated below:

Problem. Say you are a vendor of lemonade and lemon juice. Each unit of lemonade requires 1 lemon and 2 litres of water. Each unit of lemon juice requires 3 lemons and 1 litre of water. Each unit of lemonade gives a profit of \(\$ 3\). Each unit of lemon juice gives a profit of \(\$ 2\). You have 6 lemons and 4 litres of water available. How many units of lemonade and lemon juice should you make to maximize profit?

We saw how letting \(x\) denote the number of units of lemonade to be made and letting \(y\) denote the number of units of lemon juice to be made, the problem could be formulated as the following linear programming problem:

\[\begin{array}{rrcrll} \max & 3x & + & 2y & \\ \text{s.t.} & x & + & 3y & \leq & 6 \\ & 2x & +& y & \leq & 4 \\ & x & & & \geq & 0 \\ & & & y & \geq & 0. \\ \end{array}\]

The problem has a unique optimal solution at \(\begin{bmatrix} x \\ y\end{bmatrix} = \begin{bmatrix} 1.2 \\ 1.6\end{bmatrix}\) for a profit of \(6.8\). But this solution requires us to make fractional units of lemonade and lemon juice. What if we require the number of units to be integers? In other words, we want to solve \[\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. But rather, it is an integer linear programming problem.

Mixed-integer linear programming

A mixed-integer linear programming problem is a problem of minimizing or maximizing a linear function subject to finitely many linear constraints such that the number of variables are finite and at least one of which is 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 some pathological cases.

Mixed integer linear programming problems are in general difficult to solve. Yet they are too important to ignore because they have a wide range of applications (e.g. transportation planning, crew scheduling, circuit design, resource management etc.) Many solution methods for these problems 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 integer requirements on the variables.

Example

Let \((MP)\) denote the following mixed-integer linear programming problem: \[\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 \\ & & & & & x_3 & \in & \mathbb{Z}. \end{array}\]

The linear programming relaxation 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}\] Call this problem \((P_1)\).

Observe that the optimal value of \((P_1)\) is a lower bound for the optimal value of \((MP)\) since the feasible region of \((P_1)\) contains all the feasible solutions to \((MP)\), thus making it possible to find a feasible solution to \((P_1)\) with objective function value 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 subproblems 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 first illustrate the ideas on \((MP)\).

Solving the linear programming relaxation \((P_1)\), we find that \(\mathbf{x}^* = \begin{bmatrix}0\\ \frac{2}{3}\\ \frac{1}{3}\end{bmatrix}\) is an optimal solution to \((P_1)\). Note that \(\mathbf{x}^*\) is not a feasible solution to \((MP)\) because \(x^*_3\) is not an integer. We now create two subproblems \((P_2)\) and \((P_3)\) such that \((P_2)\) is obtained from \((P_1)\) by adding the constraint \(x_3 \leq \lfloor x^*_3\rfloor\) and \((P_3)\) is obtained from \((P_1)\) by adding the constraint \(x_3 \geq \lceil x^*_3\rceil\). (For a number \(a\), \(\lfloor a \rfloor\) denotes the greatest integer at most \(a\) and \(\lceil a \rceil\) denotes the smallest integer at least \(a\).) Hence, \((P_2)\) is the problem \[\begin{array}{rrcrcrlll} \min & x_1 & & & + & x_3 \\ (P_2)~~~~~~ \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 \((P_3)\) is the problem \[\begin{array}{rrcrcrlll} \min & x_1 & & & + & x_3 \\ (P_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 \((P_2)\) or \((P_3)\). One easily checks that \((P_2)\) is infeasible. The problem \((P_3)\) has an optimal solution at \(\mathbf{x}^* = \begin{bmatrix}0\\ \frac{4}{5}\\ 1\end{bmatrix}\), which is also feasible to \((MP)\). Hence, \(\mathbf{x}^* = \begin{bmatrix}0\\ \frac{4}{5}\\ 1\end{bmatrix}\) is an optimal solution to \((MP)\).

We now give a description of the method for a general mixed-integer linear programming problem \((MIP).\) Suppose that \((MIP)\) is a minimization problem and has \(n\) variables \(x_1,\ldots,x_n\). Let \({\cal I} \subseteq \{1,\ldots,n\}\) denote the set of indices \(i\) such that \(x_i\) is required to be an integer in \((MIP).\)

Branch-and-bound method

Input: The problem \((MIP)\).
Steps:

1. Set bestbound \(:= \infty\), \(\mathbf{x}^*_{\text{best}}:= \) N/A, activeproblems \(:= \{ (LP) \}\) where \((LP)\) denotes the linear programming relaxation of \((MIP).\)

2. If there is no problem in activeproblems, then stop; if \(\mathbf{x}^*_{\text{best}} \neq \) N/A, then \(\mathbf{x}^*_{\text{best}}\) is an optimal solution; otherwise, \((MIP)\) has no optimal solution.

3. Select a problem \(P\) from activeproblems and remove it from activeproblems.

4. Solve \(P\).

   • If \(P\) is unbounded, then stop and conclude that \((MIP)\) does not have an optimal solution.

   • If \(P\) is infeasible, go to step 2.

   • If \(P\) has an optimal solution \(\mathbf{x}^*\), then let \(z\) denote the objective function value of \(\mathbf{x}^*\).

5. If \(z \geq \) bestbound, go to step 2.

6. If \(x^*_i\) is not an integer for some \(i \in {\cal I}\), then create two subproblems \(P_1\) and \(P_2\) such that \(P_1\) is the problem obtained from \(P\) by adding the constraint \(x_i \leq \lfloor x^*_i \rfloor\) and \(P_2\) is the problem obtained from \(P\) by adding the constraint \(x_i \geq \lceil x^*_i \rceil\). Add the problems \(P_1\) and \(P_2\) to activeproblems and go to step 2.

7. Set \(\mathbf{x}^*_{\text{best}} = \mathbf{x}^*\), bestbound \(=z\) and go to step 2.

Remarks.

• Throughout the algorithm, activeproblems is a set of subproblems remained to be solved. Note that for each problem \(P\) in activeproblems, \(P\) is a linear programming problem and that any feasible solution to \(P\) satisfying the integrality requirements is a feasible solution to \((MIP)\).

• \(x^*_{\text{best}}\) is the feasible solution to \((MIP)\) that has the best objective function value found so far and bestbound is its objective function value. It is often called an incumbent.

• In practice, how a problem from activeproblems is selected in step 3 has an impact on the overall performance. However, there is no general rule for selection that guarantees good performance all the time.

• In step 5, the problem \(P\) is discarded since it cannot contain any feasible solution to \((MIP)\) having a better objective function value than \(x^*_{\text{best}}\).

• If step 7 is reached, then \(x^*\) is a feasible solution to \((MIP)\) having objective function value better than bestbound. So it becomes the current best solution.

• It is possible for the algorithm to never terminate. Below is an example for which the algorithm will never stop: \[\begin{array}{rl} \min & x_1 \\ \text{s.t.} & x_1 + 2x_2 - 2x_3 = 1 \\ & x_1, x_2, x_3 \geq 0 \\ & x_1, x_2, x_3 \in \mathbb{Z} \end{array} \] However, it is easy to see that \(\mathbf{x}^* = \begin{bmatrix} 1 \\ 0 \\ 0\end{bmatrix}\) is an optimal solution because there is no feasible solution with \(x_1=0\).

One way to keep track of the progress of the computations is to set up a progress chart with the following headings:

In a given iteration, the entry in the solved column denotes the subproblem that has been solved with the result in the status column. The branching column indicates the subproblems created from the solved subproblem with an optimal solution not feasible to \((MIP)\). The entries in the remaining columns contain the latest information in the given iteration. For the example \((MP)\) above, the chart could look like the following:

Another way is to represent the computations using a tree called a branch-and-bound tree:

Each node denotes a subproblem that needs to be solved. Inside each node, the solution status of the associated linear programming problem is shown. Each edge shows the branching inequality added to form the subproblem.

If the mixed-integer linear programming problem is of the form: \[\begin{array}{rl} \min & \mathbf{c}^\mathsf{T}\mathbf{x} \\ \mbox{s.t.} & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \\ & x_i \in \mathbb{Z}~\forall~i \in {\cal I} \end{array}\] where \(\mathbf{A}\) is an \(m \times n\) matrix having rank \(m\), \(\mathbf{b} \in \mathbb{R}^m\), \(\mathbf{c} \in \mathbb{R}^n\), \(\mathbf{x} = \begin{bmatrix} x_1\\ \vdots \\ x_n\end{bmatrix}\) is a vector of \(n\) variables and \({\cal I}\) is a subset of \(\{1,\ldots, n\}\), then in step 6, the newly created problems \(P_1\) and \(P_2\) can be solved using the dual simplex method provided we have an optimal basis for \(P\). Hence, the dual simplex method can be used throughout.

Worked examples

1. Suppose that \((MP)\) in the example above has \(x_2\) required to be an integer as well. Continue with the computations and determine an optimal solution to the modified problem. Present your computations in a branch-and-bound tree.

   An optimal solution to the modified problem is given by \(x^* = \begin{bmatrix} 1\\1\\1 \end{bmatrix}\). Below is the branch-and-bound tree:

2. Determine the optimal value of \[\begin{array}{rrcrll} \max & 3x & + & 2y & \\ \text{s.t.} & x & + & 3y & \leq & 6 \\ & 2x & +& y & \leq & 4 \\ & x & ,& y & \geq & 0 \\ & x &,& y & \in & \mathbb{Z}. \\ \end{array}\]

   An optimal solution is \(\begin{bmatrix} x\\y \end{bmatrix} = \begin{bmatrix} 2 \\ 0\end{bmatrix}\). Thus, the optimal value is \(6\).

3. Find an optimal solution to \[\begin{array}{rrcrcrll} \min & 3x & + & 2y & + & z \\ \text{s.t.} & -x & + & y & + & 4z & = & 1 \\ & x & +& 2y & + & 2z & = & 5 \\ & x & ,& y & , & z & \geq & 0 \\ & x &,& y & , & z & \in & \mathbb{Z}. \\ \end{array}\]

   It might be tempting to solve this using branch-and-bound. However, when it comes to integer linear programming problems, we should search for shortcuts. We will show two ways to solve this problem.

   Solution 1. Consider the second equality constraint: \(x + 2y + 2z = 5\). Since \(x,y,z\) are required to be nonnegative integers, the left-hand side is the sum of a nonnegative integer and two nonnegative even numbers that has to equal 5. Enumerating all possibilities, we see that \((x,y,z)\) can be \((5,0,0)\), \((3,1,0)\), \((3,0,1)\), \((1,2,0)\), \((1,0,2)\). Among these candidates, only \((3,0,1)\) and \((1,2,0)\) satisfy the first equality constraint. Comparing the objective function values of \((3,0,1)\) and \((1,2,0)\), we see that \((x,y,z)=(1,2,0)\) is the unique optimal solution.

   Solution 2. Row-reducing the system of equalities, we obtain the equivalent problem \[\begin{array}{rrcrcrll} \min & 3x & + & 2y & + & z \\ \text{s.t.} & x & & & - & 2z & = & 1 \\ & & & y & + & 2z & = & 2 \\ & x & ,& y & , & z & \geq & 0 \\ & x &,& y & , & z & \in & \mathbb{Z}. \\ \end{array}\] Hence, \(x = 1+2z\) and \(y = 2 - 2z\). Replacing each occurrence of \(x\) with \(1+2z\) and replacing each occurrence of \(y\) with \(2-2z\), we obtain \[\begin{array}{rrll} \min & 5+3z \\ \text{s.t.} & 1+2z & \geq & 0 \\ & 2-2z & \geq & 0 \\ & z & \geq & 0 \\ & 1+2z & \in & \mathbb{Z} \\ & 2-2z & \in & \mathbb{Z} \\ &z & \in & \mathbb{Z}. \end{array}\] The inequalities together give \(0 \leq z \leq 1\). Since we are minimizing \(5+3z\), we choose \(z = 0\), which also satisfies all the constraints. With \(z = 0\), we obtain \(x = 1\) and \(y = 2.\) Thus, an optimal solution is \((x,y,z) = (1,2,0)\).

4. Use software to find an optimal solution to \[\begin{array}{rrcrcrcrll} \min & x_1 & + & 4x_2 & + & 3 x_3 & - & x_4 \\ \text{s.t.} & x_1 & + & 2x_2 & - & 2x_3 & & & = & 1 \\ & x_1 & + & x_2 & + & 3x_3 & - & x_4 & = & 5 \\ & & & 3x_2 & + & x_3 & + & 2x_4 & = & 4 \\ & x_1 & , & x_2 & , & x_3 & , & x_4 & \geq & 0 \\ & x_1 &, & x_2 & , & x_3 & , & x_4 & \in & \mathbb{Z}. \\ \end{array}\]

   Below is the Julia code for solving this problem:

   
   using JuMP, GLPK
   model = Model();
   set_optimizer(model, GLPK.Optimizer)
   
   @variable(model, x₁ >= 0, Int)
   @variable(model, x₂ >= 0, Int)
   @variable(model, x₃ >= 0, Int)
   @variable(model, x₄ >= 0, Int)
   
   @constraint(model, c1, x₁ + 2x₂ - 2x₃       == 1) 
   @constraint(model, c2, x₁ +  x₂ + 3x₃ -  x₄ == 5) 
   @constraint(model, c3,      3x₂ +  x₃ + 2x₄ == 4) 
   
   @objective(model, Min, x₁ + 4x₂ + 3x₃ - x₄) 
   
   optimize!(model) 
   if termination_status(model) == MOI.OPTIMAL
     println("optval = ", objective_value(model))
     println("x₁ = ", value(x₁))
     println("x₂ = ", value(x₂)) 
     println("x₃ = ", value(x₃))
     println("x₄ = ", value(x₄))
   else
     println("Unable to find an optimal solution.")
   end
   

   We could also define an array of variables to avoid naming each variable directly:

   
   using JuMP, GLPK
   model = Model();
   set_optimizer(model, GLPK.Optimizer)
   
   @variable(model, x[1:4] >= 0, Int)
   
   @constraint(model, c1, x[1] + 2x[2] - 2x[3]         == 1) 
   @constraint(model, c2, x[1] +  x[2] + 3x[3] -  x[4] == 5) 
   @constraint(model, c3,        3x[2] +  x[3] + 2x[4] == 4) 
   
   @objective(model, Min, x[1] + 4x[2] + 3x[3] - x[4]) 
   
   optimize!(model) 
   status = termination_status(model)
   if status == MOI.OPTIMAL
     println("optval = ", objective_value(model))
     println("x₁ = ", value(x[1]))
     println("x₂ = ", value(x[2])) 
     println("x₃ = ", value(x[3]))
     println("x₄ = ", value(x[4]))
   elseif status == MOI.INFEASIBLE
     println("Problem is infeasible.")
   else
     println("Failed to solve problem.")
   end
   

   Running the code gives \(\begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \end{bmatrix}\) as an optimal solution.

   Modifying the above code by removing Int in the declaration of variables, we obtain \(\begin{bmatrix} \frac{35}{11} \\ 0 \\ \frac{12}{11} \\ \frac{16}{11} \end{bmatrix}\) (after converting the float values into fractions) as an optimal solution to the linear programming relaxation.