Search

This paper presents a novel domain-consistency algorithm which does not maintain supports dynamically during propagation, but rather maintains forbidden values. It introduces the optimal NAC4 (negative AC4) algorithm based on this idea, as an instance of the generic algorithm AC5. The paper then shows how forbidden values and supports can be used jointly to achieve domain consistency on logical combinations of constraints and to compute validity as well as entailment of constraints. The combination of NAC4 and AC4, denoted byPNAC4, allows to achieve domain consistency in time O(ed) for classes of constraints in which the number of supports is O(d 2) but the number of forbidden values is O(d), or conversely. The paper also presents a simple variant of AC3, denoted PNAC3. Both PNAC4 and PNAC3 are especially efficient on classes of constraints offering a O(1) getSupports or getForbidden function. Experimental results show that, on these particular classes of constraints, the joint exploitation of supports and forbidden values outperforms the standard AC algorithms, and that the use of a specialized getSupports or getForbidden function enhances the efficiency of the algorithms, especially for PNAC3 which is very close to the efficiency of totally dedicated consistency algorithms.

Constrained optimum tree (COT) and constrained optimum path (COP) problems arise in many real-life applications and are ubiquitous in communication networks. They have been traditionally approached by dedicated algorithms, which are often hard to extend with side constraints and to apply widely. This paper pro- poses a constraint-based local search framework for COT/COP applications, bring- ing the compositionality, reuse, and extensibility at the core of constraint-based local search and constraint programming systems. The modeling contribution is the abil- ity to express compositional models for various COT/COP applications at a high level of abstraction, while cleanly separating the model and the search procedure. The main technical contribution is a connected neighborhood based on rooted span- ning trees to find high-quality solutions to COP problems. This framework is applied to some COT/COP problems, e.g., the quorumcast routing problem, the edge-disjoint paths problem, and the routing and wavelength assignment with delay side constraints problem. Computational results show the potential importance of the approach.

The Steel Mill Slab Problem is an optimization benchmark that has been studied for a long time in the constraint-programming community but was only solved efficiently in the two last years. Gargani and Refalo solved the problem using Large Neighborhood Search and Van Hentenryck and Michel made use of constraint programming with an improved symmetry breaking scheme. In the first part of this paper, we build on those approaches, present improvements of those two techniques, and study how the problem can be tackled by Constraint-Based Local Search. As a result, the classical instances of CSPLib can now be solved in less than 50 ms. To improve our understanding of this problem, we also introduce a new set of harder instances, which highlight the strengths and the weaknesses of the various approaches. In a second part of the paper, we present a variation of the Steel Mill Slab Problem whose aim is to minimize the number of slabs. We show how this problem can be tackled with slight modifications of our proposed algorithms. In particular, the constraint-programming solution is enhanced by a global symmetric cardinality constraint, which, to our knowledge, has never been implemented and used before. All the proposed approaches to solve this problem have been modeled and evaluated using Comet.

This paper takes a fresh look at the application of interval analysis to ordinary differential equations and studies how consistency techniques can help address the accuracy problems typically exhibited by these methods, while trying to preserve their efficiency. It proposes to generalize interval techniques into a two-step process: a forward process that computes an enclosure and a backward process that reduces this enclosure. Consistency techniques apply naturally to the backward (pruning) step but can also be applied to the forward phase. The paper describes the framework, studies the various steps in detail, proposes a number of novel techniques, and gives some preliminary experimental results to indicate the potential of this new research avenue.