Bounding Linear Programs by Constraint Propagation: Application to Max-SAT

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00343057" target="_blank" >RIV/68407700:21230/20:00343057 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-030-58475-7_11" target="_blank" >https://doi.org/10.1007/978-3-030-58475-7_11</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-58475-7_11" target="_blank" >10.1007/978-3-030-58475-7_11</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Bounding Linear Programs by Constraint Propagation: Application to Max-SAT

Popis výsledku v původním jazyce

The Virtual Arc Consistency (VAC) algorithm by Cooper et al. is a soft local consistency technique that computes, in linear space, a bound on the basic LP relaxation of the Weighted CSP (WCSP). We generalize this technique by replacing arc consistency with a (problem-dependent) constraint propagation in a system of linear inequalities over the reals. When propagation detects infeasibility, the infeasibility certificate (a solution to the alternative system in Farkas’ lemma) provides a dual improving direction. We illustrate this approach on the LP relaxation of Weighted Max-SAT. We show in experiments that the obtained bounds are often not far from global LP optima and we prove that they are exact for known tractable subclasses of Weighted Max-SAT.

Název v anglickém jazyce

Bounding Linear Programs by Constraint Propagation: Application to Max-SAT

Popis výsledku anglicky

The Virtual Arc Consistency (VAC) algorithm by Cooper et al. is a soft local consistency technique that computes, in linear space, a bound on the basic LP relaxation of the Weighted CSP (WCSP). We generalize this technique by replacing arc consistency with a (problem-dependent) constraint propagation in a system of linear inequalities over the reals. When propagation detects infeasibility, the infeasibility certificate (a solution to the alternative system in Farkas’ lemma) provides a dual improving direction. We illustrate this approach on the LP relaxation of Weighted Max-SAT. We show in experiments that the obtained bounds are often not far from global LP optima and we prove that they are exact for known tractable subclasses of Weighted Max-SAT.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10100 - Mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2020

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

Principles and Practice of Constraint Programming

ISBN

978-3-030-58474-0

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

17

Strana od-do

177-193

Název nakladatele

Springer Nature Switzerland AG

Místo vydání

Basel

Místo konání akce

Louvain-la-Neuve

Datum konání akce

7. 9. 2020

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

WRD - Celosvětová akce

Kód UT WoS článku

—