On Relation Between Constraint Propagation and Block-Coordinate Descent in Linear Programs
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On Relation Between Constraint Propagation and Block-Coordinate Descent in Linear Programs
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10100 - Mathematics
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
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
Principles and Practice of Constraint Programming
ISBN
978-3-030-58474-0
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
17
Pages from-to
194-210
Publisher name
Springer Nature Switzerland AG
Place of publication
Basel
Event location
Louvain-la-Neuve
Event date
Sep 7, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—