Experimental Results on Hillier's Search Imbedded in a Branch-and-Bound Algorithm.
Abstract
The paper reports an empirical discovery in integer programming. A version of the branch-and-bound approach is used as a control, and tested against the same algorithm augmented by the use of Hillier's linear search performed at every node of the search tree. It is shown that the imbedded linear search locates solutions within 1%, and solutions within 5%, of the theoretical optimum, which in fact can be seen to have this proximity to the theoretical optimum at the time of termination of computation, over (10) times faster than the control. Evidence is presented, in terms of the number of variables which have to be fixed to locate the 1% and 5% optima, which strongly supports the view that this order-of-magnitude speed-up will be independent of the precise branch-and-bound algorithm that is used. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1973
- Accession Number
- AD0771094
Entities
People
- H. C. Smith
- Robert G. Jeroslow
Organizations
- Carnegie Mellon University