The Seesaw Algorithm: Function Optimization Using Implicit Hitting Sets
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F21%3A00353758" target="_blank" >RIV/68407700:21730/21:00353758 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.CP.2021.31" target="_blank" >https://doi.org/10.4230/LIPIcs.CP.2021.31</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.CP.2021.31" target="_blank" >10.4230/LIPIcs.CP.2021.31</a>
Alternative languages
Result language
angličtina
Original language name
The Seesaw Algorithm: Function Optimization Using Implicit Hitting Sets
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/LL1902" target="_blank" >LL1902: Powering SMT Solvers by Machine Learning</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
ISBN
978-3-95977-211-2
ISSN
—
e-ISSN
1868-8969
Number of pages
16
Pages from-to
1-16
Publisher name
Dagstuhl Publishing,
Place of publication
Saarbrücken
Event location
Montpellier
Event date
Oct 25, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—