DROPS

Document

DOI: 10.4230/LIPIcs.CP.2023.24

MDD Archive for Boosting the Pareto Constraint

Authors: Steve Malalel, Arnaud Malapert, Marie Pelleau, and Jean-Charles Régin

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

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.

Cite as

Steve Malalel, Arnaud Malapert, Marie Pelleau, and Jean-Charles Régin. MDD Archive for Boosting the Pareto Constraint. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.CP.2023.24},
  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}
}

Search Results

Documents authored by Malapert, Arnaud

MDD Archive for Boosting the Pareto Constraint

Abstract

Cite as

Thanks for your feedback!

Could not send message