
Linear programming on a GPU: a case study 225
Example
Figure 10.1 illustrates the use of the B&B algorithm for solving an ILP.
The ILP problem is the following:
Maximize z = x
1
+ 4x
2
Subject to 5x
1
+ 8x
2
≤ 40
−2x
1
+ 3x
2
≤ 9
x
1
, x
2
≥ 0 integer-valued
The nodes are solved with the simplex method in the order written on the
figure. At the 3rd step of the B&B, the first feasible solution is encountered
(light grey leaf). The optimal solution is encountered at the 7th step (dark
grey leaf). However, this is assessed only after solving the last two nodes (8th
and 9th) whose objective value z is inferior to the best one yet found.
FIGURE 10.1. Solving an ILP problem