Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.35
URN: urn:nbn:de:0030-drops-166647
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16664/
Rudich, Isaac ; Cappart, Quentin ; Rousseau, Louis-Martin
Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams
| pdf-format: |
|
Abstract
Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. However, the field of decision diagrams is relatively new, and is still incorporating the library of techniques that conventional solvers have had decades to build. We drew inspiration from the warm-start technique used in conventional solvers to address one of the major challenges faced by decision diagram based methods. Decision diagrams become more useful the wider they are allowed to be, but also become more costly to generate, especially with large numbers of variables. We present a method of peeling off a sub-graph of previously constructed diagrams and using it as the initial diagram for subsequent iterations that we call peel-and-bound. We test the method on the sequence ordering problem, and our results indicate that our peel-and-bound scheme generates stronger bounds than a branch-and-bound scheme using the same propagators, and at significantly less computational cost.
BibTeX - Entry
@InProceedings{rudich_et_al:LIPIcs.CP.2022.35,
author = {Rudich, Isaac and Cappart, Quentin and Rousseau, Louis-Martin},
title = {{Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams}},
booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
pages = {35:1--35:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-240-2},
ISSN = {1868-8969},
year = {2022},
volume = {235},
editor = {Solnon, Christine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16664},
URN = {urn:nbn:de:0030-drops-166647},
doi = {10.4230/LIPIcs.CP.2022.35},
annote = {Keywords: decision diagrams, discrete optimization, branch-and-bound, sequencing, constraint programming}
}
| Keywords: | decision diagrams, discrete optimization, branch-and-bound, sequencing, constraint programming | |
| Seminar: | 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 23.07.2022 | |
| Supplementary Material: | Other (Source Code for Experiments): https://github.com/IsaacRudich/PnB_SOP |
