Publications - Gecode

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.

Table Talk Tuning is a table-assignment problem drawn from a real wedding seating case. Alongside capacities, grouping and separation requests, table slack, and balance constraints, the model asks that every guest have at least one topic with enough support at their table to sustain a conversation.

The paper presents a MiniZinc model, three synthetic instance families from 10 to 150 guests, a reproducible benchmark pipeline, and a native Gecode model for comparing objective-aware search. The experiments show that the conversation terms still change the returned seatings in the paired ablation cases. The native experiments show that scalar, lexicographic, and sequential handling of the same objective hierarchy changes search behaviour.

Modeling and Programming with Gecode provides comprehensive documentation of how to model and program with Gecode.

The first part of the document explains modeling and solving constraint problems with Gecode. It explains how to program, compile, link, and execute these models. It provides an overview of integer, Boolean, and set variables and constraints, modeling support, search, and Gist. This is complemented by a collection of interesting case studies of how to model with Gecode.

The remaining, more advanced, parts are about programming with Gecode. They explain in great detail and with numerous examples the concepts and techniques for programming constraints, branchings, search engines, and new variable types with Gecode. The parts’ coverage puts users on par with Gecode’s developers.

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.