Learning Implied Global Constraints

Christian Bessiere, Remi Coletta, Thierry PetitIJCAI 2007

Abstract

Constraint Programming (CP) is a powerful paradigm for solving combinatorial problems, yet its effectiveness often depends on expert-level modeling. A key technique used by experts is the addition of implied constraints—logically redundant rules that enhance the solver's propagation capabilities. This paper presents a framework for automatically learning these implied global constraints by analyzing variable domains. Our results demonstrate that this automated "expert intuition" can reduce solving times from hours to minutes, significantly lowering the barrier to entry for high-performance constraint modeling.

Introduction

The performance of Constraint Programming (CP) solvers is highly dependent on the quality of the problem model. While a naive model may be logically sound, it often lacks the necessary propagation to prune large portions of the search space, leading to intractability. CP experts address this by manually identifying and adding implied constraints. These constraints do not alter the solution set but provide the solver with additional information to detect dead ends earlier in the search process.

Identifying effective implied constraints is a non-trivial task requiring deep expertise. This paper introduces a general framework to automate this process by learning the parameters of global constraints (such as GCC or NValue) directly from the problem instance and its variable domains.

Methodology

The proposed approach focuses on Parametric Learning, where the system identifies the tightest possible parameters for a given global constraint.

The Learning Framework

The core of the framework is an algorithm that refines the bounds of possible parameter values through:

  1. Inconsistency Checks: Discarding parameter settings that make the problem unsatisfiable.
  2. Solution Analysis: Using found solutions to establish valid parameter ranges.

To maintain computational efficiency, the authors utilize properties such as parameter-partitioning and represent parameters as continuous ranges. A critical innovation is the use of Relaxation: by learning constraints on a simplified version of the problem, the system can derive valid rules for the full problem with significantly less overhead.

Experimental Results

The framework was evaluated on synthetic scheduling tasks and a real-world project assignment problem involving 60 students at the University of Montpellier.

Impact on Search Efficiency

On small-scale scheduling instances, the addition of learned implied constraints led to a dramatic reduction in both the number of search nodes and the total solving time. As illustrated in Figure 1, instances that remained unsolved by a naive model after 60 seconds were resolved in just 0.05 seconds using the learned constraints.

Performance comparison on small scheduling instances.

Scalability and Real-World Application

The scalability of the approach is best demonstrated by the project assignment optimization problem. For an instance with 60 students, the initial model failed to find an optimal solution within a 12-hour limit. By incorporating a learned Global Cardinality Constraint (GCC), the solver reached the optimal solution in approximately 43 minutes, including a brief 2-minute learning phase.

Scalability results for the project assignment problem.

Discussion and Key Insights

  • Data-Driven Discovery: By focusing on variable domains rather than just problem syntax, the framework discovers constraints arising from complex variable interactions that human experts might overlook.
  • Low Overhead, High Reward: The "upfront investment" in the learning phase is minimal compared to the exponential savings in search time, especially for large-scale instances.

Conclusion

This research provides a scalable method for automatically enhancing CP models with implied global constraints. By bridging the gap between naive modeling and expert-level performance, this framework makes Constraint Programming more accessible and efficient for a wider range of applications. Future work will explore the automatic selection of candidate global constraints to further minimize the need for user intervention.

Summary updated

BibTeX
@inproceedings{bessiere2007learning,
  author = {Christian Bessiere and Remi Coletta and Thierry Petit},
  title = {{Learning Implied Global Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}
Figure