The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


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.24
URN: urn:nbn:de:0030-drops-190610
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19061/
Go to the corresponding LIPIcs Volume Portal

Malalel, Steve ; Malapert, Arnaud ; Pelleau, Marie ; Régin, Jean-Charles

MDD Archive for Boosting the Pareto Constraint

pdf-format:
LIPIcs-CP-2023-24.pdf (0.8 MB)

Abstract

Multi-objective problems are frequent in the real world. In general they involve several incomparable objectives and the goal is to find a set of Pareto optimal solutions, i.e. solutions that are incomparable two by two. In order to better deal with these problems in CP the global constraint Pareto was developed by Schaus and Hartert to handle the relations between the objective variables and the current set of Pareto optimal solutions, called the archive. This constraint handles three operations: adding a new solution to the archive, removing solutions from the archive that are dominated by a new solution, and reducing the bounds of the objective variables. The complexity of these operations depends on the size of the archive. In this paper, we propose to use a multi-valued Decision Diagram (MDD) to represent the archive of Pareto optimal solutions. MDDs are a compressed representation of solution sets, which allows us to obtain a compressed and therefore smaller archive. We introduce several algorithms to implement the above operations on compressed archives with a complexity depending on the size of the archive. We show experimentally on bin packing and multi-knapsack problems the validity of our approach.

BibTeX - Entry

@InProceedings{malalel_et_al:LIPIcs.CP.2023.24,
  author =	{Malalel, Steve and Malapert, Arnaud and Pelleau, Marie and R\'{e}gin, Jean-Charles},
  title =	{{MDD Archive for Boosting the Pareto Constraint}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{24:1--24:15},
  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/19061},
  URN =		{urn:nbn:de:0030-drops-190610},
  doi =		{10.4230/LIPIcs.CP.2023.24},
  annote =	{Keywords: Constraint Programming, Global Constraint, MDD, Multi-Objective Problem, Pareto Constraint}
}

Keywords: Constraint Programming, Global Constraint, MDD, Multi-Objective Problem, Pareto Constraint
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