License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2023.13
URN: urn:nbn:de:0030-drops-190500
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19050/
Go to the corresponding LIPIcs Volume Portal

Coppé, Vianney ; Gillard, Xavier ; Schaus, Pierre

Boosting Decision Diagram-Based Branch-And-Bound by Pre-Solving with Aggregate Dynamic Programming

pdf-format:
LIPIcs-CP-2023-13.pdf (0.9 MB)

Abstract

Discrete optimization problems expressible as dynamic programs can be solved by branch-and-bound with decision diagrams. This approach dynamically compiles bounded-width decision diagrams to derive both lower and upper bounds on unexplored parts of the search space, until they are all enumerated or discarded. Assuming a minimization problem, relaxed decision diagrams provide lower bounds through state merging while restricted decision diagrams obtain upper bounds by excluding states to limit their size. As the selection of states to merge or delete is done locally, it is very myopic to the global problem structure. In this paper, we propose a novel way to proceed that is based on pre-solving a so-called aggregate version of the problem with a limited number of states. The compiled decision diagram of this aggregate problem is tractable and can fit in memory. It can then be exploited by the original branch-and-bound to generate additional pruning and guide the compilation of restricted decision diagrams toward good solutions. The results of the numerical study we conducted on three combinatorial optimization problems show a clear improvement in the performance of DD-based solvers when blended with the proposed techniques. These results also suggest an approach where the aggregate dynamic programming model could be used in replacement of the relaxed decision diagrams altogether.

BibTeX - Entry

@InProceedings{coppe_et_al:LIPIcs.CP.2023.13,
  author =	{Copp\'{e}, Vianney and Gillard, Xavier and Schaus, Pierre},
  title =	{{Boosting Decision Diagram-Based Branch-And-Bound by Pre-Solving with Aggregate Dynamic Programming}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19050},
  URN =		{urn:nbn:de:0030-drops-190500},
  doi =		{10.4230/LIPIcs.CP.2023.13},
  annote =	{Keywords: Discrete Optimization, Decision Diagrams, Aggregate Dynamic Programming}
}

Keywords: Discrete Optimization, Decision Diagrams, Aggregate Dynamic Programming
Collection: 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Issue Date: 2023
Date of publication: 22.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI