DROPS

Document

DOI: 10.4230/LIPIcs.CP.2024.8

Slide&Drill, a New Approach for Multi-Objective Combinatorial Optimization

Authors: João Cortes, Inês Lynce, and Vasco Manquinho

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract

Following the successful use of Propositional Satisfiability (SAT) algorithms in Boolean optimization (e.g., Maximum Satisfiability), several SAT-based algorithms have been proposed for Multi-Objective Combinatorial Optimization (MOCO). However, these new algorithms either provide a small subset of the Pareto front or follow a more exploratory search procedure and the solutions found are usually distant from the Pareto front. We extend the state of the art with a new SAT-based MOCO solver, Slide and Drill (Slide&Drill), that hones an upper bound set of the exact solution. Moreover, we show that Slide&Drill neatly complements proposed UNSAT-SAT algorithms for MOCO. These algorithms can work in tandem over the same shared "blackboard" formula, in order to enable a faster convergence. Experimental results in several sets of benchmark instances show that Slide&Drill can outperform other SAT-based algorithms for MOCO, in particular when paired with previously proposed UNSAT-SAT algorithms.

Cite as

João Cortes, Inês Lynce, and Vasco Manquinho. Slide&Drill, a New Approach for Multi-Objective Combinatorial Optimization. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cortes_et_al:LIPIcs.CP.2024.8,
  author =	{Cortes, Jo\~{a}o and Lynce, In\^{e}s and Manquinho, Vasco},
  title =	{{Slide\&Drill, a New Approach for Multi-Objective Combinatorial Optimization}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.8},
  URN =		{urn:nbn:de:0030-drops-206932},
  doi =		{10.4230/LIPIcs.CP.2024.8},
  annote =	{Keywords: Multi-Objective Combinatorial Optimization, Satisfiability Algorithms}
}

Search Results

Documents authored by Cortes, João

Slide&Drill, a New Approach for Multi-Objective Combinatorial Optimization

Abstract

Cite as

Thanks for your feedback!

Could not send message