Using Constraint Propagation to Bound Linear Programs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00375629" target="_blank" >RIV/68407700:21230/24:00375629 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1613/jair.1.15604" target="_blank" >https://doi.org/10.1613/jair.1.15604</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1613/jair.1.15604" target="_blank" >10.1613/jair.1.15604</a>

Result language

angličtina

Original language name

Using Constraint Propagation to Bound Linear Programs

Original language description

We present an approach to compute bounds on the optimal value of linear programs based on constraint propagation. Given a feasible dual solution, we apply constraint propagation to the complementary slackness conditions and, if propagation succeeds to prove these conditions infeasible, the infeasibility certificate (in the sense of Farkas’ lemma) is reconstructed from the propagation history. This certificate is a dual-improving direction, which allows us to improve the bound. As constraint propagation need not always detect infeasibility of a linear inequality system, the method is not guaranteed to converge to a global solution of the linear program but only to an upper bound, whose tightness depends on the structure of the program and the used propagation method. The approach is suited for large sparse linear programs (such as LP relaxations of combinatorial optimization problems), for which the classical LP algorithms may be infeasible, if only for their super-linear space complexity. The approach can be seen as a generalization of the Virtual Arc Consistency (VAC) algorithm to bound the LP relaxation of the Weighted CSP (WCSP). We newly apply it to the LP relaxation of the Weighted Max-SAT problem, experimentally showing that the obtained bounds are often not far from optima of the relaxation and proving that they are exact for known tractable subclasses of Weighted Max-SAT.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

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

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)

Publication year

2024

Confidentiality

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

Name of the periodical

Journal of Artificial Intelligence Research

ISSN

1076-9757

e-ISSN

1943-5037

Volume of the periodical

80

Issue of the periodical within the volume

June

Country of publishing house

US - UNITED STATES

Number of pages

54

Pages from-to

665-718

UT code for WoS article

001457267900001

EID of the result in the Scopus database

2-s2.0-85197346347