The Rules of Constraint Modelling

Alan M. Frisch, Christopher Jefferson, Bernadette Martínez Hernández, Ian MiguelIJCAI 2005

Introduction

In constraint programming, a significant gap exists between the conceptual description of a problem—such as "assigning golfers to groups without repeat pairings"—and the low-level code required by a solver. This gap, known as the modelling bottleneck, typically requires human experts to manually translate abstract concepts into atomic variables like integers or Booleans. This paper introduces CONJURE, a system designed to automate this "black art" by formalizing constraint modelling as a process of systematic, compositional refinement.

ESSENCE: Bridging the Abstraction Gap

The foundation of this automation is ESSENCE, a high-level specification language. Unlike traditional constraint languages that force users to think in terms of solver-supported primitives, ESSENCE allows for the use of natural mathematical constructs. Its primary innovation is support for compositional types, enabling the definition of complex, nested structures like "sets of sets" or "multisets of partitions."

An ESSENCE specification for the SONET communication network design problem, demonstrating the use of nested sets to define communication demands and network rings.

By decoupling the problem logic from the underlying data representation, ESSENCE allows modellers to focus on the "what" of a problem rather than the "how." This abstraction ensures that the problem description remains clean and mathematically sound, independent of the specific solver's requirements.

CONJURE: The Refinement Engine

The CONJURE system acts as a compiler for ESSENCE, applying a library of formal refinement rules to transform abstract specifications into a lower-level language (ESSENCE'). This process involves several key mechanisms:

  1. Compositional Refinement: CONJURE recursively applies rules. If it knows how to refine a "set" and an "integer," it can automatically combine these rules to refine a "set of integers."
  2. Multiple Representations: For any abstract type, the system can explore various concrete representations. For example, a set might be represented as an explicit matrix of elements or as an "occurrence" Boolean array.
  3. Symmetry Tagging: Refinement often introduces new symmetries (e.g., the arbitrary ordering of elements in a matrix representing a set). CONJURE automatically identifies and tags these symmetries so they can be handled by symmetry-breaking constraints later.
Refining a set equality constraint into different concrete representations, including matrix-based and Boolean-based models.

Evaluation and Results

The authors evaluated CONJURE against seven classic combinatorial benchmarks, including Balanced Incomplete Block Design (BIBD) and the SONET problem. The system successfully generated the "kernels"—the fundamental variables and constraints—for all test cases.

A standout result occurred with the SONET problem: CONJURE generated 27 distinct models, which included all four models previously identified by human experts in the literature. This demonstrates that a relatively small set of formal rules can effectively navigate the vast space of potential models to find high-quality solutions that match or exceed human-crafted versions.

Conclusion and Future Work

CONJURE represents a shift in constraint programming from an intuitive craft to an automated science. While the current system focuses on generating correct kernels, future work will address model selection—using heuristics to rank models by performance—and expanding support for more complex types like relations and functions. By automating the refinement process, CONJURE brings us closer to a world where complex combinatorial problems can be solved directly from their natural mathematical descriptions.

Summary updated

BibTeX
@inproceedings{frisch2005rules,
  author = {Alan M. Frisch and Christopher Jefferson and Bernadette Martínez Hernández and Ian Miguel},
  title = {{The Rules of Constraint Modelling}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure