On Relation Between Constraint Propagation and Block-Coordinate Descent in Linear Programs

Kód výsledku v IS VaVaI

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

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

On Relation Between Constraint Propagation and Block-Coordinate Descent in Linear Programs

Popis výsledku v původním jazyce

Block-coordinate descent (BCD) is a popular method in large-scale optimization. Unfortunately, its fixed points are not global optima even for convex problems. A succinct characterization of convex problems optimally solvable by BCD is unknown. Focusing on linear programs, we show that BCD fixed points are identical to fixed points of another method, which uses constraint propagation to detect infeasibility of a system of linear inequalities in a primal-dual loop (a special case of this method is the Virtual Arc Consistency algorithm by Cooper et al.). This implies that BCD fixed points are global optima iff a certain propagation rule decides feasibility of a certain class of systems of linear inequalities.

Název v anglickém jazyce

On Relation Between Constraint Propagation and Block-Coordinate Descent in Linear Programs

Popis výsledku anglicky

Block-coordinate descent (BCD) is a popular method in large-scale optimization. Unfortunately, its fixed points are not global optima even for convex problems. A succinct characterization of convex problems optimally solvable by BCD is unknown. Focusing on linear programs, we show that BCD fixed points are identical to fixed points of another method, which uses constraint propagation to detect infeasibility of a system of linear inequalities in a primal-dual loop (a special case of this method is the Virtual Arc Consistency algorithm by Cooper et al.). This implies that BCD fixed points are global optima iff a certain propagation rule decides feasibility of a certain class of systems of linear inequalities.

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

194-210

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

—