×

Anomalies in distributed branch-and-cut solving of the CVRP with different search strategies. (English) Zbl 1178.90074

Boljunčić, Valter (ed.) et al., KOI 2006. 11th international conference on operational research, Pula, Croatia, September 27–29, 2006. Proceedings. Zagreb: Croatian Operational Research Society (ISBN 978-953-7498-11-5/pbk). 47-56 (2008).
Summary: We analyze how different search strategies (namely, the breadth-first, the depth-first and the best-first) influence the execution speed of the parallel branch-and-cut algorithm for solving the capacitated vehicle routing problem. We report anomalous behavior observed as a part of the experimental evaluation of the algorithm and relate to it known theoretical results on anomalies in parallel and on efficiency of search strategies in sequential branch-and-bound algorithms.
For the entire collection see [Zbl 1175.90008].

MSC:

90B20 Traffic problems in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite