Publications - Propagation

The minimum-distance constraint links a set of selected points to the smallest distance between any selected pair. A direct constraint-programming encoding is clear, but introduces a quadratic family of auxiliary distance variables and propagators.

This paper studies direct Gecode implementations ranging from pairwise propagators to global pair-support scans, advisor-backed support maintenance, and a conflict-matching upper bound. Preliminary experiments on p-dispersion instances show that direct propagation can avoid decomposition overhead, while also making clear that stronger propagation is not automatically faster. The simple pairwise forward-bound propagator remains a useful baseline; advisors and matching-based bounds are promising additions.

This paper revisits Helmut Simonis’s 2005 study of Sudoku as a constraint problem and extends it from the standard 9x9 grid to sizes 6x6, 9x9, 16x16, 25x25, and 36x36. The generated corpus contains 32,000 unique-solution base puzzles and more than 400,000 easier variants produced by adding clues back.

The complete 434,201-instance corpus is available separately, with the base puzzles, saved hardness-walk variants, JSON metadata, and corpus utilities.

The familiar propagation-based hardness categories remain useful, but their distribution changes sharply with size. All generated 6x6 and 9x9 starting puzzles, and 84.9% of the 16x16 puzzles, are solved without search by the tested propagation family. None of the 25x25 or 36x36 starting puzzles are. Hardness walks connect these larger puzzles to easier categories, but require increasingly many added clues to do so.

Propagators are central to the success of constraint programming, that is contracting functions removing values proven not to be in any solution of a given constraint. The literature contains numerous propagation algorithms, for many different constraints, and common to all these propagation algorithms is the notion of correctness: only values that appear in no solution to the respective constraint may be removed.

In this paper half-checking propagators are introduced, for which the only requirements are that identified solutions (by the propagators) are actual solutions (to the corresponding constraints), and that the propagators are contracting. In particular, a half-checking propagator may remove solutions resulting in an incomplete solving process, but with the upside that (good) solutions may be found faster. Overall completeness can be obtained by running half-checking propagators as one component in a portfolio solving process. Half-checking propagators opens up a wider variety of techniques to be used when designing propagation algorithms, compared to what is currently available.

A formal model for half-checking propagators is introduced, together with a detailed description of how to support such propagators in a constraint programming system. Three general directions for creating half-checking propagation algorithms are introduced, and used for designing new half-checking propagators for the cost-circuit constraint as examples. The new propagators are implemented in the Gecode system.

This paper introduces propagator groups as an abstraction for controlling the execution of propagators as implementations of constraints. Propagator groups enable users of a constraint programming system to program how propagators within a group are executed.

The paper exemplifies propagator groups for controlling both propagation order and propagator interaction. Controlling propagation order is applied to debugging constraint propagation and optimal constraint propagation for Berge-acyclic propagator graphs. Controlling propagator interaction by encapsulating failure and entailment is applied to general reification and constructive disjunction. The paper describes an implementation of propagator groups (based on Gecode) that is applicable to any propagator-centered constraint programming system. Experiments show that groups incur little to no overhead and that the applications of groups are practically usable and efficient.

This thesis explores three new techniques for increasing the efficiency of constraint propagation: support for incremental propagation, improved representation of constraints, and abstractions to simplify propagation.

Support for incremental propagation is added to a propagator-centered propagation system by adding a new intermediate layer of abstraction, advisors, that capture the essential aspects of a variable-centered system. Advisors are used to give propagators a detailed view of the dynamic changes between propagator runs. Advisors enable the implementation of optimal algorithms for important constraints such as extensional constraints and Boolean linear in-equations, which is not possible in a propagator-centered system lacking advisors.

Using Multivalued Decision Diagrams (MDD) as the representation for extensional constraints is shown to be useful for several reasons. Classical operations on MDDs can be used to optimize the representation, and thus speeding up the propagation. In particular, the reduction operation is stronger than the use of DFA minimization for the regular constraint. The use of MDDs is contrasted and compared to a recent proposal where tables are compressed.

Abstractions for constraint programs try to capture small and essential features of a model. These features may be much cheaper to propagate than the unabstracted program. The potential for abstraction is explored using several examples.

These three techniques work on different levels. Support for incremental propagation is essential for the efficient implementation of some constraints, so that the algorithms have the right complexity. On a higher level, the question of representation looks at what a propagator should use for propagation. Finally, the question of abstraction can potentially look at several propagators, to find cases where abstractions might be fruitful.

An essential feature of this thesis is an novel model for general placement constraints that uses regular expressions. The model is very versatile and can be used for several different kinds of placement problems. The model applied to the classic pentominoes puzzle will be used through-out the thesis as an example and for experiments.

While incremental propagation for global constraints is recognized to be important, little research has been devoted to how propagator-centered constraint programming systems should support incremental propagation. This paper introduces advisors as a simple and efficient, yet widely applicable method for supporting incremental propagation in a propagator-centered setting. The paper presents how advisors can be used for achieving different forms of incrementality and evaluates cost and benefit for several global constraints.