On the best search strategy in parallel branch‐and‐bound:Best‐First Search versus Lazy Depth‐First Search

J. Clausen and M. Perregaard

Annals of Operations Research, 1999, vol. 90, issue 0, 17 pages

Abstract: The Best‐First Search strategy (BeFS) and the Depth‐First Search strategy (DFS) areregarded as the prime strategies when solving combinatorial optimization problems by parallelBranch‐and‐Bound (B&B) ‐ BeFS because of efficiency with respect to the number of nodesexplored, and DFS for reasons of space efficiency. We investigate the efficiency of both strategies experimentally, and two versions of eachstrategy are tested: In the first, a B&B iteration for a node consists of bounding followed bybranching on the node if necessary. For the second, the order is reversed ‐ first branchingtakes place, and then each child of the node is bounded and possibly fathomed. The first iscalled lazy, the second eager. The strategies are tested on the Quadratic Assignment Problem and the Job Shop SchedulingProblem. We use parallel codes developed specifically for the solution of the problem inquestion, and hence containing different heuristic rules and tests to speed up computation.In both cases, we start with an initial solution close to but not equal to the optimal solution. Surprisingly, the BeFS‐based strategies turn out to be inferior to the DFS‐based strategies,both in terms of running times and in terms of bound calculations performed. Furthermore,when tested in a sequential setting, DFS turns out to be still superior because pruning andevaluation tests are more effective in DFS due to the presence of better incumbents. Copyright Kluwer Academic Publishers 1999

Date: 1999
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018952429396 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:90:y:1999:i:0:p:1-17:10.1023/a:1018952429396

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018952429396

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().