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."
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:
- 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."
- 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.
- 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.
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