Integer Programs

Let's revisit our muffin batter problem:

\[ \begin{aligned} \max \quad & 0.6 x_1 + 0.5 x_2 \\ \text{subject to} \quad & 0.8 x_1 + 0.5 x_2 \leq 1500 \\ & 0.2 x_1 + 0.5 x_2 \leq 900 \\ & x_1 \geq 0 \\ & x_2 \geq 0 \end{aligned} \]

Assuming a muffin always consists of 175g of batter.

Our solution was $x_1 = 1000$ and $x_2 = 1400$.

So, we can produce 5 muffins of Type A and 8 muffins of Type B. There will be 125g of Type A batter left unused.

Is this the best solution?

Not necessarily!

We want to find the best solution assuming that only discrete quantities of muffins are possible.

We reformulate the problem to count the number of muffins per type.

\[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \in \{0, 1, 2, 3, 4, \ldots \} \\ & x_2 \in \{0, 1, 2, 3, 4, \ldots \} \end{aligned} \]

Integer Linear Program (ILP or IP)

When we have continuous and integer variables, we speak of
Mixed Integer Linear Programming (MILP or MIP).

We only allow integer points within the constraints:

We achieve this solution by rounding:

The solution brings revenues of 1225;

How do we know if there is a better solution?

How do we generally find the best solution?

Idea: Divide & Conquer

If we solve the problem as LP, we get

\[ x = \begin{bmatrix} 5.714 \\ 8 \end{bmatrix} \]

In the final solution, $x_1$ has two options: \[ x_1 \leq 5 \quad\text{or}\quad x_1 \geq 6 \]

So we can now solve the two LPs:

\[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \leq 5 \\ & x_1, x_2 \geq 0 \end{aligned} \] \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_1, x_2 \geq 0 \end{aligned} \]

For each LP, we receive a solution again

$x = \begin{bmatrix} 5 \\ 8.286 \end{bmatrix}, \text{obj} = 1250$

$x = \begin{bmatrix} 6 \\ 7.543 \end{bmatrix}, \text{obj} = 1290$

We can continue in a similar manner. For the first branch, we can formulate two variations again:

\[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \leq 5 \\ & x_2 \leq 8 \\ & x_1, x_2 \geq 0 \end{aligned} \] \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \leq 5 \\ & x_2 \geq 9 \\ & x_1, x_2 \geq 0 \end{aligned} \]

Each new branch has a solution:

$x = \begin{bmatrix} 5 \\ 8 \end{bmatrix}, \text{obj} = 1225$

$x = \begin{bmatrix} 3.214 \\ 9 \end{bmatrix}, \text{obj} = 1125$

In the variant $x_1 \leq 5, x_2 \leq 8$ we have now found a feasible, integer solution.

This is also the solution we had earlier by rounding.

In this branch we are done. No other point can be better.

In the other branch, our solution was again fractional:

$x = \begin{bmatrix} 3.214 \\ 9 \end{bmatrix}, \text{obj} = 1125$

Do we now need to try
$x_1 \leq 3$ and $x_1 \geq 4$ here?

The best fractional solution in the branch has an objective function value of 1125.

We have already found an integer solution with an objective function value of 1225.

So, we can prune the entire branch.

In the still open version $x_1 \geq 6$ the fractional solution had an objective function value of 1290.

So we are not finished yet.

Once again, we break down the problem into two parts:

\[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1, x_2 \geq 0 \end{aligned} \] \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \geq 8 \\ & x_1, x_2 \geq 0 \end{aligned} \]

$x = \begin{bmatrix} 6.339 \\ 7 \end{bmatrix}, \text{obj} = 1278.125$

Infeasible

We can directly cut off the unsolvable branch.

In the other branch, we will continue to subdivide.

\[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1 \leq 6 \\ & x_1, x_2 \geq 0 \end{aligned} \] \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1 \geq 7 \\ & x_1, x_2 \geq 0 \end{aligned} \]

$x = \begin{bmatrix} 6 \\ 7 \end{bmatrix}, \text{obj} = 1242.5$

$x = \begin{bmatrix} 7 \\ 5.943 \end{bmatrix}, \text{obj} = 1255$

We have found a new integer solution. Its objective function value of 1242.5 is even better than the old one of 1225.

We can now forget the old solution. We always only need the (so far) best solution.

What can we say at this point about the quality of the (so far best) solution?

  • The current best integer solution has objective 1242.5
  • The best (still open) fractional solution has objective 1255

$\Rightarrow$ There cannot be an integer solution that improves our current objective by more than 12.5 (1%).

The distance between the current best solution and the best open fractional solution is called
Optimality Gap.

If we were to give up solving now, at least we have this quality guarantee.

If we do not give up, we have to further divide here:

$x = \begin{bmatrix} 7 \\ 5.943 \end{bmatrix}, \text{obj} = 1255$

\[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1 \geq 7 \\ & x_2 \leq 5 \\ & x_1, x_2 \geq 0 \end{aligned} \] \[ \begin{aligned} \max \quad & 105 x_1 + 87.5 x_2 \\ \text{subject to} \quad & 140 x_1 + 87.5 x_2 \leq 1500 \\ & 35 x_1 + 87.5 x_2 \leq 900 \\ & x_1 \geq 6 \\ & x_2 \leq 7 \\ & x_1 \geq 7 \\ & x_2 \geq 6 \\ & x_1, x_2 \geq 0 \end{aligned} \]

$x = \begin{bmatrix} 7.589 \\ 5 \end{bmatrix}, \text{obj} = 1234.375$

Infeasible

In the first branch, we are now too weak, and there is no solution in the other one.

So, we are done and know:
$x = \begin{bmatrix} 6 \\ 7 \end{bmatrix}$ is the globally best solution with an objective function value of 1242.5

    We do not need to further partition a node if:

  • The LP solution is already integral.
  • The sub-problem is infeasible.
  • The fractional solution is worse than the best integral solution found so far.

Branch & Bound

The best integer objective function value we know is called the primal bound.

We know that we do not have to accept a solution with a worse objective.

We call the best objective function value across all current (non-pruned) leaves the dual bound.

We know that no solution can exist that exceeds this DB.

When we split a node, the objective function value of the children can never improve
(and tends to deteriorate).

Each child node has more constraints than the parent node.

The primal bound can never be better than the dual bound.

Integerality is an additional constraint that can only make things worse for us.

In a maximization problem, the primal bound increases over time and the dual bound decreases.

In a minimization problem, it is the opposite.

The optimality gap

\[ \frac{|\text{dual bound} - \text{primal bound}|}{|\text{primal bound}|} \]

indicates how much our current best solution could potentially be improved.

We now have an algorithm that will eventually find the globally optimal solution for our ILP.

How much computational effort does it require?

In the worst case, the number of nodes is exponential in the number of variables (and their possible values).

Our prospect of a well-scalable algorithm is poor.

Integer programming is NP-hard.

This way we can map every NP-hard problem to ILP.

Integer Programming is NP-complete.

Advantage: many problems can be modeled very well as ILP.

    Further advantages of ILPs:

  • Our algorithm ensures that it always makes progress towards the global optimum.
  • We always have a quality guarantee of the current solution (in case we abort).
  • Modern ILP solvers are very fast for many problems.

    There are several tricks to improve Branch & Bound:

  • Start Simplex in child nodes with a "warm start"
  • Use heuristics to find good integer solutions
  • Derive new constraints that must be guaranteed to be met and improve the dual bound.

Example of derived constraints:

\[ x_1 + x_2 \leq 1 \quad x_1 + x_3 \leq 1 \quad x_2 + x_3 \leq 1 \\ \]

\[ \Rightarrow x_1 + x_2 + x_3 \leq 1 \] (Clique Cover)

This is a very active research field.

From 2001 to 2020, solvers have become 22% faster on average each year.

Factor 50 over 20 years.

Hardware improvements (Factor 20) add to this (Factor 1000 in total).

Progress is unevenly distributed: Some problem classes perform better than others.


"Progress in Mathematical Programming Solvers from 2001 to 2020", T. Koch, T. Berthold, J. Pedersen, C. Vanaret.

In the LP models, we had cases where we should have also required integrality.

  • Matching students to exercise groups
  • Shortest path in a graph

Example: Student Matching

\[ \begin{aligned} \max\quad & \sum_{i,j} p_{ij} x_{ij} \\ \text{s.t.}\quad &\sum_j x_{ij} = 1 \quad & \forall i \\ &\sum_i x_{ij} \leq 5 \quad & \forall j \\ &x_{ij} \geq 0 \quad & \forall i,j \end{aligned} \]

It can be proven here that in these cases the vertices of the polyhedron are always integers.

Therefore, we automatically obtain an integer solution.

We can always demand integer values to be on the safe side (if needed). It doesn't cost any performance if the first node is already an integer.

Disadvantages of ILPs compared to LPs:

  • Performance
  • No shadow prices