Inductive Synthesis of Constraint Satisfaction Models

28 concepts20 papers1 proposal

When we model complex real-world systems—whether scheduling delivery fleets, optimizing data centers, or training neural networks—we rely on constraints to define the boundaries of what is possible. Historically, capturing these rules has required human experts to manually translate messy domain knowledge into rigid mathematical logic. As Eugene C. Freuder noted in Constraints: The Ties that Bind, while Constraint Satisfaction Problems (CSPs) serve as a powerful lingua franca capable of unifying disparate AI techniques, the process of manually building these models creates a severe "usability gap" (Barry O'Sullivan in Automated Modelling and Solving in Constraint Programming).

Automated constraint acquisition bridges this gap by shifting the burden of formal modeling from humans to machines. Instead of hardcoding rules, this paradigm uses machine learning and inductive reasoning to discover the underlying constraints of a system directly from data, examples, or interactions. As highlighted by Luc De Raedt et al. in their Dagstuhl Seminar Report, intersecting constraint programming with data mining allows optimization models to become self-generating and adaptive.

Inductive Learning from Examples

The most direct way to learn a constraint is to observe what works and what fails. By analyzing a dataset containing examples of valid solutions (positive instances) and invalid configurations (negative instances), inductive learning algorithms can map observed patterns to formal mathematical rules.

[Positive Examples]  ──┐
                       ├─► [Inductive Learning Solver] ─► [Formal Constraints]
[Negative Examples]  ──┘

As Lombardi et al. outline in Boosting Combinatorial Problem Modeling with Machine Learning, this process involves scanning example data and matching observed patterns against existing solver libraries, such as linear inequalities or global constraints. Barry O'Sullivan (Automated Modelling and Solving in Constraint Programming) frames this through the lens of version space learning: the system starts with a broad hypothesis space of all possible constraints and systematically prunes away any rules that contradict the provided examples.

To ensure these learned models can scale up to larger problems, Kumar et al. introduced a "generate-and-aggregate" framework called COUNT-CP in Learning Constraint Programming Models from Data Using Generate-And-Aggregate. Instead of learning rigid, instance-specific rules, their approach uses simple formal grammars to synthesize expressive first-order constraints. Because these constraints focus on high-level aggregations rather than individual variables, a model learned from a small toy example can successfully generalize to massive problem instances.

Even in pure search scenarios, statistical observation can stand in for explicit rule-writing. For instance, Tristan Cazenave demonstrated in Learning a Prior for Monte Carlo Search by Replaying Solutions to Combinatorial Problems that by replaying successful solutions, a search agent can build a data-driven prior that assigns a probability of zero to invalid moves. The agent effectively learns the hard logical rules of a domain purely by observing successful outcomes.

Uncovering Latent Operational Rules

Data in the real world is rarely neatly labeled into clean sets of solutions and non-solutions. Often, the most critical constraints are latent—silently embedded within historical human decisions or structured data files.

Hewitt et al. tackle this challenge in Data-driven optimization model customization by analyzing the discrepancy between theoretical models and actual human behavior. When a textbook optimization algorithm calculates a path as "optimal," but human operators consistently choose a more circuitous route, the discrepancy reveals the presence of an unstated operational constraint. By applying statistical learning to this gap, generic optimization models can automatically customize themselves to reflect real-world business constraints without requiring manual stakeholder interviews.

[Textbook Optimal Solution] ──┐
                              ├─► [Discrepancy Analysis] ─► [Discover Latent Constraint]
[Actual Human Decision]     ──┘

This concept applies equally to structured data environments like spreadsheets. In Predictive spreadsheet autocompletion with constraints, Kolb et al. developed the PSyChe framework, which automatically identifies latent mathematical relationships across spreadsheet rows and columns. By treating these discovered relationships as hard rules during inference, the system drastically reduces the search space for autocompletion, filtering out candidates that violate the underlying logic of the sheet. As noted by Yingqian Zhang et al. in their DSO workshop preface, this ability to extract structural rules from historical data is vital when the governing logic of a system is not explicitly documented or fully understood by human experts.

Bypassing Combinatorial Explosion with Language and Agents

A major hurdle for traditional constraint acquisition is the combinatorial explosion of the search space. Testing every possible combination of variables against a library of constraint templates quickly becomes computationally intractable as the number of variables grows.

To circumvent this, Mechqrane et al. introduced LLMACQ in Using Large Language Models to Improve Query-based Constraint Acquisition. Instead of blindly matching templates, the system leverages Large Language Models (LLMs) to interpret natural language explanations from users detailing why a specific solution is invalid. By converting these explanations into "nogoods" (forbidden combinations of values), the system bypasses template matching entirely and drastically cuts down the number of queries needed to define a problem. This fulfills Eugene C. Freuder's vision of "human-aware constraint reasoning" (Explaining Ourselves: Human-Aware Constraint Reasoning), where interactive dialogues shift the cognitive burden of formalization from the human to the solver.

Taking autonomy a step further, Ni Zhang et al. developed the AFL framework in An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems. Rather than relying on human prompts or pre-translated templates, AFL deploys a multi-agent LLM system that directly parses raw, standardized problem files. The agents autonomously deduce the constraints, inputs, and objectives embedded within the data files, writing and debugging fully functional Python solvers from scratch without human intervention.

Domain-Agnostic Inductive Biases

Automated constraint discovery is not limited to classical combinatorial puzzles; it serves as a powerful mechanism for injecting domain-specific inductive biases into deep learning architectures.

  • Computer Vision: While early deformable models required manual configuration to enforce geometric boundaries (Christian Brechbühler in Imposing Hard Constraints on Soft Snakes), modern semantic segmentation frameworks can discover these rules automatically. As demonstrated in Optimizing against Infeasible Inclusions from Data for Semantic Segmentation through Morphology, systems can automatically extract spatial relationship constraints (e.g., learning that a road segment cannot be entirely enclosed within a sky segment) directly from training data, penalizing unrealistic predictions.
  • Deep Learning Safety: In out-of-distribution (OOD) detection, Kirchheim et al. show in Improving Out-of-Distribution Detection with Markov Logic Networks that a greedy search algorithm can automatically identify logical constraints from datasets. These rules are compiled into a Markov Logic Network to verify if an input makes "semantic sense," providing interpretable explanations for why anomalous data is flagged.
  • Physical Simulations: In the realm of dynamical systems, Thangamuthu et al. demonstrate in Unravelling the Performance of Physics-informed Graph Neural Networks for Dynamical Systems that incorporating explicit constraints into Graph Neural Networks is the key to achieving zero-shot generalization on larger systems. They note that the future of the field relies on developing methods that can automatically extract these physical constraints directly from trajectory data, eliminating the need for manual user specification.

By shifting from manual engineering to data-driven discovery, automated constraint acquisition allows optimization models to remain dynamic, evolving alongside the data they represent (Barry O'Sullivan in Opportunities and Challenges for Constraint Programming). Whether extracting unstated business logic from historical decisions or parsing physical constraints from trajectories, this paradigm provides the essential link between raw data and structured reasoning.

Key Foundational Work

Constraints: The Ties that Bind (2006) — contributed 2 concept elements to this direction.
Imposing Hard Constraints on Soft Snakes (1996) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_automated_constraint_acquisition_e6dc9b47,
  title = {automated constraint acquisition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/automated-constraint-acquisition/rdr_e6dc9b4722be4f608da79bbfde442a8e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_automated_constraint_acquisition_e6dc9b47_v1,
  title = {automated constraint acquisition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/automated-constraint-acquisition/rdr_e6dc9b4722be4f608da79bbfde442a8e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake