Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F10%3A00170728" target="_blank" >RIV/68407700:21230/10:00170728 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction

Popis výsledku v původním jazyce

We present a number of contributions to the LP relaxation approach to weighted constraint satisfaction (Gibbs energy minimization). We generalize it to n-ary constraints in a simple and natural way. This includes a simple algorithm to minimize the LP-based upper bound, n-ary max-sum diffusion, we consider using other bound-optimizing algorithms as well. The diffusion iteration is tractable for a certain class of high-arity constraints represented as a black-box, which is analogical to propagators for global constraints CSP. Diffusion exactly solves permuted n-ary supermodular problems. A hierarchy of gradually tighter LP relaxations is obtained simply by adding various zero constraints and coupling them in various ways to existing constraints. Zero constraints can be added incrementally, which leads to a cutting plane algorithm. The separation problem is formulated as finding an unsatisfiable subproblem of a CSP.

Název v anglickém jazyce

Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction

Popis výsledku anglicky

We present a number of contributions to the LP relaxation approach to weighted constraint satisfaction (Gibbs energy minimization). We generalize it to n-ary constraints in a simple and natural way. This includes a simple algorithm to minimize the LP-based upper bound, n-ary max-sum diffusion, we consider using other bound-optimizing algorithms as well. The diffusion iteration is tractable for a certain class of high-arity constraints represented as a black-box, which is analogical to propagators for global constraints CSP. Diffusion exactly solves permuted n-ary supermodular problems. A hierarchy of gradually tighter LP relaxations is obtained simply by adding various zero constraints and coupling them in various ways to existing constraints. Zero constraints can be added incrementally, which leads to a cutting plane algorithm. The separation problem is formulated as finding an unsatisfiable subproblem of a CSP.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

JD - Využití počítačů, robotika a její aplikace

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)<br>R - Projekt Ramcoveho programu EK

Rok uplatnění

2010

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 periodika

IEEE Transactions on Pattern Analysis and Machine Intelligence

ISSN

0162-8828

e-ISSN

—

Svazek periodika

32

Číslo periodika v rámci svazku

8

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

15

Strana od-do

—

Kód UT WoS článku

000278858600009

EID výsledku v databázi Scopus

—