WB8 - CP Reasoning

The Cumulative constraint is used to solve scheduling problems with resource constraints. This presentation shows how the Overload Check for the Cumulative constraint can be enhanced by reasoning on the integral resource usage. This augmentation is done by solving knapsack sub-problems to evaluate the resource availability at any moment.

We propose a version of DFS designed for Constraint Programming, called bimodal DFS, that scales to both sparse and dense graphs. It runs in $O(n+\Tilde{m})$ time, where $\Tilde{m}$ is the sum, for each vertex $v$, of the minimum between the numbers of successors and non-successors of $v$.
Integrating it into Régin’s GAC algorithm for the AllDifferent constraint results in faster performance as the problem size increases.
In the vast majority of our tests, GAC now performs similarly to BC in terms of speed, but is able to solve more problems.

The general theory of CP-based Lagrangian filtering lacks a uniform framework to explain many known observations, which we provide by studying the Lagrange multiplier space. We build a CP-based Lagrangian filtering algorithm that we test on the multidimensional knapsack problem and the uncapacitated facility location problem. We record a significant speed up compared with traditional CP-based Lagrangian filtering method on both problems.

The additive bounding procedure (Fischetti, Toth 1989) solves a sequence of relaxations to compute a bound on an optimization problem. The bound that is obtained can be better than any one obtained from each individual relaxation. We show that interleaving, rather than sequencing, the computation of the relaxations can result in even tighter bounds.