Democratizing Constraint Satisfaction Problems through Machine Learning

Mohit Kumar, Samuel Kolb, Clément Gautrais, Luc De Raedt

Abstract

Modeling complex scheduling and planning problems typically requires specialized expertise in Operations Research. This paper introduces SYNTHCSP, an interactive Excel plugin designed to bridge this gap. By leveraging machine learning to automatically "learn" underlying constraints from existing data, SYNTHCSP enables users to solve complex Constraint Satisfaction Problems (CSPs) directly within a spreadsheet environment. The system integrates multiple learning algorithms and a high-performance solver to turn raw data into automated problem-solving engines.

Introduction: The Modeling Bottleneck

Constraint Satisfaction Problems (CSPs) are ubiquitous in industries ranging from healthcare (nurse rostering) to aviation (flight scheduling). Despite their prevalence, solving these problems presents a significant "modeling bottleneck." Translating real-world requirements into formal mathematical constraints is a labor-intensive, error-prone process requiring deep domain knowledge.

While the field of constraint learning has emerged to automate rule extraction, existing tools are often fragmented and inaccessible to non-experts. SYNTHCSP addresses this by providing a unified, user-friendly platform that combines multiple learning techniques, making CSP modeling accessible to anyone proficient in spreadsheet software.

Methodology: The SYNTHCSP Pipeline

SYNTHCSP functions as a bridge between raw spreadsheet data and mathematical solvers. The system operates through a four-step pipeline:

  1. Data Extraction: The tool monitors spreadsheet activity and identifies data structures (e.g., binary shift tables) to select the most appropriate learning algorithm.
  2. Constraint Learning: It employs an ensemble of learners simultaneously. For instance, TACLE identifies spreadsheet formulas and relations, while COUNT-OR specializes in rostering-specific constraints.
  3. Model Initialization: SYNTHCSP translates diverse learner outputs into a common language, initializing a model in the Gurobi solver by mapping spreadsheet cells to variables.
  4. Inference and Solving: The engine fills in missing values or generates new valid schedules based on the learned rules.

Furthermore, the authors provide an API that allows researchers to integrate new constraint-learning algorithms into the ecosystem with minimal implementation effort.

Case Study: Nurse Scheduling Dataset

The capabilities of SYNTHCSP are demonstrated using a nurse scheduling scenario. The dataset consists of a weekly schedule and a corresponding summary table.

Nurse scheduling dataset showing a weekly shift schedule (left) and a summary of total shifts per nurse (right).

In this example, the system learns two distinct types of rules:

  • Rostering constraints: Using COUNT-OR, it identifies that "every shift requires a nurse."
  • Relational constraints: Using TACLE, it recognizes that the summary table represents the sum of rows in the primary schedule.

Discussion and Key Insights

The development of SYNTHCSP highlights several critical advancements in the field:

  • Ensemble Learning: No single algorithm can capture all types of constraints. By combining learners like TACLE and COUNT-OR, the system uncovers multi-layered rules that individual algorithms might miss.
  • Spreadsheets as Interfaces: By integrating with Excel, the authors leverage a familiar environment that provides natural "visual hints" for interactive modeling.
  • Unified Formalism: The system acts as a "universal translator," converting various mathematical formalisms into a format compatible with high-performance solvers like Gurobi.

Conclusion and Future Directions

SYNTHCSP successfully demonstrates interoperability between different learning algorithms and provides a self-sufficient lifecycle for constraint modeling without requiring user-written code. While currently limited by the types of constraints Gurobi can handle and a focus on "hard" constraints rather than optimization criteria, future work aims to integrate more advanced learners like ARNOLD and INCAL. This move toward a collaborative, open-source framework represents a significant step in democratizing access to powerful optimization tools.

Summary updated

Abstract

Constraint satisfaction problems (CSPs) are used widely, especially in the field of operations research, to model various real world problems like scheduling or planning. However,modelling a problem as a CSP is not trivial, it is labour intensive and requires both modelling and domain expertise. The emerging field of constraint learning deals with this problem by automatically learning constraints from a given dataset. While there are several interesting approaches for constraint learning, these works are hard to access for a non-expert user. Furthermore, different approaches have different underlying formalism and require different setups before they can be used. This demo paper combines these researches and brings it to non-expert users in the form of an interactive Excel plugin. To do this, we translate different formalism for specifying CSPs into a common language, which allows multiple constraint learners to coexist, making this plugin more powerful than individual constraint learners. Moreover, we integrate learning of CSPs from data with solving them, making it a self sufficient plugin. For the developers of different constraint learners, we provide an API that can be used to integrate their work with this plugin by implementing a handful of functions.
BibTeX
@inproceedings{kumar2021democratizing,
  author = {Mohit Kumar and Samuel Kolb and Clément Gautrais and Luc De Raedt},
  title = {{Democratizing Constraint Satisfaction Problems through Machine Learning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i18.18011},
}
Figure