Branch-and-check with explanations for the Vehicle Routing Problem with Time Windows

Edward Lam, Pascal Van Hentenryck

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

This paper proposes the framework of branch-and-check with explanations (BCE), a branch-and-check method where combinatorial cuts are found by general-purpose conflict analysis, rather than by specialized separation algorithms. Specifically, the method features a master problem that ignores combinatorial constraints, and a feasibility subproblem that uses propagation to check the feasibility of these constraints and performs conflict analysis to derive nogood cuts. The BCE method also leverages conflict-based branching rules and strengthens cuts in a post-processing step. Experimental results on the Vehicle Routing Problem with Time Windows show that BCE is a potential alternative to branch-and-cut. In particular, BCE dominates branch-and-cut, both in proving optimality and in finding high-quality solutions quickly.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication23rd International Conference, CP 2017 Melbourne, VIC, Australia, August 28 – September 1, 2017 Proceedings
EditorsJ.Christopher Beck
Place of PublicationCham Switzerland
PublisherSpringer
Pages579-595
Number of pages17
ISBN (Electronic)9783319661582
ISBN (Print)9783319661575
DOIs
Publication statusPublished - 2017
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2017 - Melbourne, Australia
Duration: 28 Aug 20171 Sep 2017
Conference number: 23rd
http://cp2017.a4cp.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10416
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2017
Abbreviated titleCP 2017
CountryAustralia
CityMelbourne
Period28/08/171/09/17
OtherThe International Conference on Principles and Practice of Constraint Programming will take place in Melbourne, Australia alongside SAT 2017 and ICLP 2017 from August 28th to September 1st, 2017 which is the week immediately following IJCAI 2017.
Internet address

Cite this

Lam, E., & Van Hentenryck, P. (2017). Branch-and-check with explanations for the Vehicle Routing Problem with Time Windows. In J. C. Beck (Ed.), Principles and Practice of Constraint Programming : 23rd International Conference, CP 2017 Melbourne, VIC, Australia, August 28 – September 1, 2017 Proceedings (pp. 579-595). (Lecture Notes in Computer Science ; Vol. 10416). Springer. https://doi.org/10.1007/978-3-319-66158-2_37