Consider a knapsack packing problem in which the objective is to maximize cx subject to ax ≤ 26 and each xj ∈ {0, 1}, where the data appear in Table 2.15.
Generate part of a local-search-and-relax-tree similar to that of Figure 2.20.
At each step of the greedy phase, fix to 1 the variable xi that has not already been fixed and that has the largest ratio ci/ai.
A leaf node is reached when no more variables can be fixed to 1.
Thus every leaf node will correspond to a feasible solution.
After evaluating a leaf node, backtrack to a random node in the current tree, and randomly select the next variable to instantiate before resuming the greedy approach.
As a relaxation, maximize cx subject to ax ≤ 26, xj ∈ [0, 1], and the currently fixed values (this is trivial to solve). For instance, after finding the first feasible solution (which has value 53), one might randomly backtrack to the
root node, which causes the other nodes created so far to be deleted. If one randomly selects x5 = 1, the optimal value of the relaxation is 50. This is worse than the incumbent value 53, thus allowing the tree to be pruned. The search backtracks to the root node (the only other node in the tree) and randomly selects another variable to instantiate to 1.
