How to Approximate Leximax-optimal Solutions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21730%2F21%3A00354101" target="_blank" >RIV/68407700:21730/21:00354101 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

How to Approximate Leximax-optimal Solutions

Popis výsledku v původním jazyce

Many real-world problems can be modelled as Multi-Objective Combinatorial Opti misation (MOCO) problems. In the multi-objective case, there is not a single optimum value but a set of optima known as Pareto-optima. However, the number of Pareto-optima can be too large to enumerate. Instead, one can compute a minimum Pareto-optimum according to an order. The leximax order selects a Pareto-optimum such that the objec tive functions with the worst values are penalised the least. Unlike other orders, such as the lexicographic order or the weighted sum order, the leximax order does not favour any objective function at the expense of others. Also, the leximax-optimum has a guaranteed small trade-off between the objective functions. In some real-world MOCO problems, the time to find a solution may be limited and computing a leximax-optimal solution may take too long. In such problems, we search for solutions that can be computed in the given admissible amount of time and that are as close to the leximax-optimum as possible. In other words, we approximate the leximax optimum. In this paper, we present and evaluate SAT-based algorithms and heuristics for ap proximating the leximax-optimum of Multi-Objective Boolean Satisfiability problems. The evaluation is performed in the context of the package upgradeability problem, on the set of benchmarks from the Mancoosi International Solver Competition, with combinations of up to five different objective functions.

Název v anglickém jazyce

How to Approximate Leximax-optimal Solutions

Popis výsledku anglicky

Many real-world problems can be modelled as Multi-Objective Combinatorial Opti misation (MOCO) problems. In the multi-objective case, there is not a single optimum value but a set of optima known as Pareto-optima. However, the number of Pareto-optima can be too large to enumerate. Instead, one can compute a minimum Pareto-optimum according to an order. The leximax order selects a Pareto-optimum such that the objec tive functions with the worst values are penalised the least. Unlike other orders, such as the lexicographic order or the weighted sum order, the leximax order does not favour any objective function at the expense of others. Also, the leximax-optimum has a guaranteed small trade-off between the objective functions. In some real-world MOCO problems, the time to find a solution may be limited and computing a leximax-optimal solution may take too long. In such problems, we search for solutions that can be computed in the given admissible amount of time and that are as close to the leximax-optimum as possible. In other words, we approximate the leximax optimum. In this paper, we present and evaluate SAT-based algorithms and heuristics for ap proximating the leximax-optimum of Multi-Objective Boolean Satisfiability problems. The evaluation is performed in the context of the package upgradeability problem, on the set of benchmarks from the Mancoosi International Solver Competition, with combinations of up to five different objective functions.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/LL1902" target="_blank" >LL1902: Obohacování SMT řešičů pomocí strojového učení</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Pragmatics of SAT a workshop of the 24nd International Conference on Theory and Applications of Satisfiability Testing

ISBN

—

ISSN

1574-0617

e-ISSN

1574-0617

Počet stran výsledku

16

Strana od-do

—

Název nakladatele

IOS Press

Místo vydání

Amsterdam

Místo konání akce

Barcelona

Datum konání akce

5. 7. 2021

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—