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.2021.31
URN: urn:nbn:de:0030-drops-153220
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15322/
Go to the corresponding LIPIcs Volume Portal

Janota, Mikoláš ; Morgado, António ; Fragoso Santos, José ; Manquinho, Vasco

The Seesaw Algorithm: Function Optimization Using Implicit Hitting Sets

pdf-format:
LIPIcs-CP-2021-31.pdf (3 MB)

Abstract

The paper introduces the Seesaw algorithm, which explores the Pareto frontier of two given functions. The algorithm is complete and generalizes the well-known implicit hitting set paradigm. The first given function determines a cost of a hitting set and is optimized by an exact solver. The second, called the oracle function, is treated as a black-box. This approach is particularly useful in the optimization of functions that are impossible to encode into an exact solver. We show the effectiveness of the algorithm in the context of static solver portfolio selection.
The existing implicit hitting set paradigm is applied to cost function and an oracle predicate. Hence, the Seesaw algorithm generalizes this by enabling the oracle to be a function. The paper identifies two independent preconditions that guarantee the correctness of the algorithm. This opens a number of avenues for future research into the possible instantiations of the algorithm, depending on the cost and oracle functions used.

BibTeX - Entry

@InProceedings{janota_et_al:LIPIcs.CP.2021.31,
  author =	{Janota, Mikol\'{a}\v{s} and Morgado, Ant\'{o}nio and Fragoso Santos, Jos\'{e} and Manquinho, Vasco},
  title =	{{The Seesaw Algorithm: Function Optimization Using Implicit Hitting Sets}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15322},
  URN =		{urn:nbn:de:0030-drops-153220},
  doi =		{10.4230/LIPIcs.CP.2021.31},
  annote =	{Keywords: implicit hitting sets, minimal hitting set, MaxSAT, optimization}
}

Keywords: implicit hitting sets, minimal hitting set, MaxSAT, optimization
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021

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