INCUMBENT SOLUTIONS IN BRANCH-AND-BOUND ALGORITHMS - SETTING THE RECORD STRAIGHT

The folklore of integer linear-programming holds that the computationa l efficiency of branch-and-bound (B&B) algorithms can be greatly impro ved by specifying a ''good'' initial bound on the objective function v alue for the problem being solved. This belief is reiterated in user's manuals for many of the well-known commercial integer-programming sof tware packages and in various research papers. Although this belief is certainly not wrong, it is not entirely reliable. In fact, the use of ''better'' initial incumbent solution values can sometimes actually l ead to longer B&B searches. This note provides an explanation for this anomaly and attempts to set the record straight about the heuristic n ature of using initial incumbent solutions in B&B algorithms. (C) 1996 Elsevier Science Ltd