Совместный семинар HDI Lab & TFAIM Lab «Bounding Linear Programs via Constraint Propagation: From Max-SAT to WCSP Super-Reparametrizations»

Abstract: We present a general framework for computing bounds on the optimal value of large, sparse linear programs (LPs) using constraint propagation. The approach applies propagation to complementary slackness conditions; if infeasibility is detected, a dual-improving direction is reconstructed from the propagation history. While not guaranteed to reach optima due to the limits of constraint propagation, this method offers a low-memory alternative for LPs where classical algorithms fail due to super-linear space complexity. We demonstrate the versatility of this scheme across two domains. First, we apply it to the LP relaxation of the Weighted Max-SAT Problem, showing that it yields tight bounds that are exact for known tractable subclasses. Second, we show how this framework manifests in the Weighted Constraint Satisfaction Problem (WCSP) through the lens of super-reparametrization transformations that preserve or increase the objective value. For arc consistency, this recovers the Virtual Arc Consistency (VAC) algorithm, while scaling to stronger consistencies like singleton arc consistency (SAC) provides superior bounds on benchmark instances.

Доклад будет основан на работах:

- Tomáš Dlask, Tomáš Werner (2024): Using Constraint Propagation to Bound Linear Programs. Journal of Artificial Intelligence Research, 80, pp. 665–718. (https://doi.org/10.1613/jair.1.15604)

- Tomáš Dlask, Tomáš Werner, Simon de Givry (2023): Super-reparametrizations of weighted CSPs: properties and optimization perspective. Constraints, 28(2), pp. 277–319. (https://doi.org/10.1007/s10601-023-09343-6)