Virtual Arc Consistency for Linear Constraints in Cost Function Networks
This work addresses an incremental improvement for constraint programming practitioners by enhancing the efficiency of solving problems with linear constraints in cost function networks.
The paper tackled the problem of solving discrete minimization problems with linear constraints in cost function networks by adapting an existing soft arc consistency algorithm to handle linear constraints, resulting in significantly improved lower bounds and reduced solving time on several benchmarks.
In Constraint Programming, solving discrete minimization problems with hard and soft constraints can be done either using (i) soft global constraints, (ii) a reformulation into a linear program, or (iii) a reformulation into local cost functions. Approach (i) benefits from a vast catalog of constraints. Each soft constraint propagator communicates with other soft constraints only through the variable domains, resulting in weak lower bounds. Conversely, the approach (ii) provides a global view with strong bounds, but the size of the reformulation can be problematic. We focus on approach (iii) in which soft arc consistency (SAC) algorithms produce bounds of intermediate quality. Recently, the introduction of linear constraints as local cost functions increases their modeling expressiveness. We adapt an existing SAC algorithm to handle linear constraints. We show that our algorithm significantly improves the lower bounds compared to the original algorithm on several benchmarks, reducing solving time in some cases.