Incumbent solutions in branch-and-bound algorithms: Setting the record straight

Incumbent solutions in branch-and-bound algorithms: Setting the record straight

0.00 Avg rating0 Votes
Article ID: iaor19962230
Country: United Kingdom
Volume: 23
Issue: 5
Start Page Number: 419
End Page Number: 424
Publication Date: May 1996
Journal: Computers and Operations Research
Authors: ,
Abstract:

The folklore of integer linear-programming holds that the computational efficiency of branch-and-bound (B&B) algorithms can be greatly improved by specifying a ‘good’ initial bound on the objective function value for the problem being solved. This belief is reiterated in user’s manuals for many of the well-known commercial integer-programming software packages and in various research papers. Although this belief is certaintly not wrong, it is not entirely reliable. In fact, the use of ‘better’ initial incumbent solution values can sometimes actually lead to longer B&B searches. This note provides an explanation for this anomaly and attempts to set the record straight about the heuristic nature of using initial incumbent solutions in B&B algorithms.

Reviews

Required fields are marked *. Your email address will not be published.