Example 5.11 Alternative Search of the Branch-and-Bound Tree

In this example, the HALDI10 problem from Example 5.10 is solved. However, here the default strategy for searching the branch-and-bound tree is modified. By default, the search strategy has VARSELECT=FAR. This means that when searching for an integer variable on which to branch, the procedure uses the one that has a value farthest from an integer value. An alternative strategy has VARSELECT=PENALTY. This strategy causes PROC LP to look at the cost, in terms of the objective function, of branching on an integer variable. The procedure looks at PENALTYDEPTH= integer variables before choosing the one with the largest cost. This is a much more expensive strategy (in terms of execution time) than the VARSELECT=FAR strategy, but it can be beneficial if fewer integer iterations must be done to find an optimal solution.

proc lp data=haldi10 varselect=penalty;
run;

Compare the number of integer iterations needed to solve the problem using this heuristic with the default strategy used in Example 5.10. In this example, the difference is profound; in general, solution times can vary significantly with the search technique. See Output 5.11.1.