I will present this journal article by Tomáš Dlask and me.
It is 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 (well-known from the field of constraint programming) 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 an existing 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.