1 Search Results for "Rudich, Isaac"

Document
DOI: 10.4230/LIPIcs.CP.2022.35
Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams

Authors: Isaac Rudich, Quentin Cappart, and Louis-Martin Rousseau

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

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.
Cite as

Isaac Rudich, Quentin Cappart, and Louis-Martin Rousseau. Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.35},
  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}
}
  • Refine by Author
  • 1 Cappart, Quentin
  • 1 Rousseau, Louis-Martin
  • 1 Rudich, Isaac

  • Refine by Classification
  • 1 Applied computing → Operations research

  • Refine by Keyword
  • 1 branch-and-bound
  • 1 constraint programming
  • 1 decision diagrams
  • 1 discrete optimization
  • 1 sequencing

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact