TL;DR
This paper introduces CONJURE, a system that automatically generates constraint models from abstract problem specifications written in the ESSENCE language. By employing a refinement-based approach, CONJURE can produce effective constraint models that match those developed by human experts, significantly easing the modeling bottleneck in constraint programming.
What Problem Does This Paper Address?
Constraint programming (CP) is a powerful technique for solving complex decision-making problems. However, the efficiency of a CP solver heavily relies on the quality of the constraint model representing the problem. Developing these models is a highly skilled and time-consuming task, posing a significant barrier for non-experts. This paper addresses the challenge of automating this crucial modeling phase, aiming to make CP more accessible and efficient by automatically generating high-quality constraint models from abstract problem descriptions.
Methods
CONJURE employs a refinement-based approach to transform abstract problem specifications written in the ESSENCE language into concrete constraint models. The core of this process involves applying two types of refinement rules:
- Representation Selection Rules: These rules choose how to represent abstract decision variables and parameters using concrete types (e.g., matrices, integers). This is akin to selecting a "viewpoint" for the problem. CONJURE can apply multiple such rules to the same variable, creating "channelled models" where a single abstract variable is represented in several ways simultaneously.
- Expression Refinement Rules: These rules translate ESSENCE expressions into equivalent ESSENCE PRIME expressions, leveraging the chosen representations of variables. These rules can be "horizontal" (representation-independent) or "vertical" (representation-dependent).
A key aspect of CONJURE is its ability to handle symmetries automatically during the refinement process, eliminating the need for a separate symmetry detection step. The system also incorporates a greedy heuristic called COMPACTEP (a combination of COMPACT and SPARSE heuristics) to guide the refinement process and select more compact or sparse representations where applicable.
Datasets
The paper evaluates CONJURE on 42 benchmark problems from CSPLib. These problems cover a wide range of decision-making scenarios and are used to demonstrate that CONJURE can generate constraint models similar to those developed by human experts. The authors note that they excluded problems that could be naturally represented using only matrices of Booleans or integers, focusing on those that benefit from ESSENCE's richer abstract types.
Key Insights and Ideas
- Automated Symmetry Breaking: CONJURE's ability to break symmetries during the refinement process is a significant advantage, as it avoids a costly post-modeling step.
- Class-Level Refinement: The system refines problem class specifications into class-level constraint models, allowing for efficient solving of multiple instances of the same problem without re-refining.
- Handling Nested Abstract Types: CONJURE can refine complex, arbitrarily nested abstract types (like sets of sets) without needing to enumerate all possible values of the inner types, which is crucial for scalability.
- Diverse Model Generation: By exploring different refinement rule application pathways, CONJURE can generate a diverse space of models for a single problem specification, offering choices for optimization.
- Expert Model Replication: The empirical results suggest that CONJURE can successfully reproduce the "kernels" of constraint models developed by human experts, validating its effectiveness.
Key Results
CONJURE was evaluated on 42 benchmark problems from CSPLib. The empirical results demonstrate that CONJURE can successfully reproduce the kernels of the constraint models for these problems, matching those found in the literature and developed by human experts. This indicates that the system is capable of generating effective and efficient constraint models automatically.
Limitations and Future Work
The paper is an extended abstract, and a full formal proof of the refinement rules' correctness is out of scope. The authors mention that their system is evaluated on a diverse set of problems, but the number of models generated for a problem depends on the number of representation options for its decision variables. Future work could explore more sophisticated model selection heuristics beyond the COMPACTEP heuristic, potentially involving racing methods or machine learning, to further optimize model choice. The paper also hints at the potential for CONJURE to be extended to handle more complex problem specifications and generate models for a wider range of solvers.
Summary updated