Section 8.4 Summary of Chapter 8
An integer optimization problem is an optimization problem where all solutions must only have integer values. We generally begin by solving the relaxation of an integer problem, where there is no such restriction. If the optimal solution is integral, then no additional work is needed. Otherwise, there are techniques which allow us to find the integral solutions.
The Branch and Bound method Definition 8.1.5 works by recursively adding additional constraints to the problem. If for some optimal solution \(x_i = x_i^*\) is non-integral, then we may force it to be integral with the additional constraint that \(x_i\leq \lfloor x_i^*\rfloor\) or \(x_i\geq \lceil x_i^*\rceil\text{.}\) Each choice results in a new branch of a search tree. If the additional constraint results in an integral optimal solution or an infeasible solution, no additional constraints are needed and we may return to the parent node. We terminate when all branches are explored in this way. Then amongst the integer solutions, we select the optimal choice.
The other more tableau centric approach is the Gomory Cutting Plane method Definition 8.2.4. We pivot to the optimal relaxed solution, and if this is non-integral, we select a non-integral \(b_i\) and for that row, add the additional constraint
\begin{equation*}
\sum_j (\lfloor a_{ij} \rfloor - a_{ij})x_j \leq (\lfloor b_i \rfloor - b_i)
\end{equation*}
which excises the non-integral optimal solution but preserves all integral solutions of the original problem. We repeat until an optimal solution is achieved.
