Summary of Chapter 8

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 ⌊ x_{i}^{*} ⌋

x_{i} \geq ⌈ x_{i}^{*} ⌉ .

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.

🔗

Figure 8.4.1. A demonstration of the Branch and Bound method.

🔗

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

🔗

\sum_{j} (⌊ a_{i j} ⌋ - a_{i j}) x_{j} \leq (⌊ b_{i} ⌋ - b_{i})

which excises the non-integral optimal solution but preserves all integral solutions of the original problem. We repeat until an optimal solution is achieved.

🔗

Figure 8.4.2. A demonstration of the Gomory Cutting Plane method.

🔗

Prev Top Next