2026-08-10T23:24:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16664 2024-03-06T10:58:00Z ddc:004 open_access

Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams Rudich, Isaac Cappart, Quentin Rousseau, Louis-Martin decision diagrams discrete optimization branch-and-bound sequencing constraint programming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Isaac Rudich and Quentin Cappart and Louis-Martin Rousseau 2022 Is Part Of LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2022.35 urn:nbn:de:0030-drops-166647 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.35 eng https://creativecommons.org/licenses/by/4.0/legalcode