Research map / Learning theory and algorithms / Combinatorial and search optimization
What Are the Rules? Discovering Constraints from Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Formalizes learning constraints from positive exemplary solutions as MDL model selection and proposes the greedy URPILS algorithm, which discovers noise-robust constraints for constraint programming and AI planning.
Problem
Learning constraints for constraint programming and AI planning from exemplary valid solutions only, without user interaction, invalid examples, or sensitivity to noise.
Approach
Casts constraint discovery as a two-part MDL problem over a custom constraint grammar, approximates model counting with graph-based bounds and a coupon-collector error estimate, and searches greedily in three stages (simple, complex, count constraints).
Key results
- URPILS achieves near-perfect test F1 on most constraint programming datasets with 1000 training examples, outperforming MINEACQ, COUNTOR and COUNTCP.
- URPILS recovers ground-truth constraints on GraphColor up to 60% noise, while COUNTOR and COUNTCP degrade at much lower noise levels.
- On 5-Queens with 10% noise, URPILS reaches 100% F1 with ten training examples, whereas MINEACQ needs 800 examples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use URPILS instead of MINEACQ, COUNTOR, or COUNTCP | Constraint programming constraint discovery · Constraint programming datasets | test F1 score | Helped |
| Add URPILS noise-robust constraint discovery | GraphColor · GraphColor with noisy training data | test F1 score: up to 60% noise | Helped |
| Use URPILS instead of COUNTOR or COUNTCP under noise | GraphColor · GraphColor with noisy training data | test F1 score: 2/3 | Helped |
| Use URPILS instead of MINEACQ | 5-Queens constraint discovery · 5-Queens test (10% training noise) | test F1 score: 100% F1 score with ten training examples; 800 examples | Helped |
| Use URPILS instead of FAMA or PLANMINER | AI planning action-constraint discovery · AI planning benchmark datasets | test F1 score | Helped |
| Use URPILS instead of FAMA or PLANMINER under noise | Hanoi action-constraint discovery · Hanoi with noisy training data | test F1 score | Helped |
| Use URPILS rather than MINEACQ | Constraint programming constraint discovery · Constraint programming datasets | model size (constraint grammar literals): 33 to 90 literals; 1280 literals for 4x4-Sudoku; 106 literals for 8-Teams-DRR | Helped |
| Use URPILS instead of COUNTOR or COUNTCP as training data becomes noisy | Constraint programming constraint discovery · 5-Queens test (10% training noise) | training examples needed for 100% F1 score: ten training examples; 800 examples | Helped |
| Use URPILS instead of FAMA under noise | Hanoi action-constraint discovery · Hanoi with noisy training data | number of discovered constraints | Helped |
| Add numerical-sum capacity constraints to URPILS | MultipleKnapsack · MultipleKnapsack | test F1 score | Helped |
Surprising findings
- Count-based baselines COUNTOR and COUNTCP pick up noise and produce poorly generalizing constraints even at modest noise levels.
- PLANMINER finds constraints with poor F1 under noise, and FAMA finds no constraints when the data contains noise.
Limitations
- Constraint language cannot express bounds on sums of numerical relations, e.g. knapsack capacity constraints, so MultipleKnapsack F1 is not perfect.
- Sample complexity and runtime grow with problem size; only finds all constraints in one of ten runs for 9-Sudoku-hard with 1000 examples.
Experimental setup
Datasets: Random (synthetic) 8-Queens 9-Sudoku-easy 9-Sudoku-hard 8-Teams-DRR GraphColor MultipleKnapsack Rostering (nurse rostering) AI planning benchmarks (Aineto et al. 2019)
Benchmarks: 8-Queens 9-Sudoku-easy 9-Sudoku-hard 8-Teams-DRR GraphColor MultipleKnapsack Rostering DLogDrive FloortileRight GripperPick Hanoi NPuzzle
Metrics: F1 score model size (literals)
Baselines: MINEACQ COUNTOR COUNTCP FAMA PLANMINER
Builds on: MDL principle COUNTOR PlanMiner FAMA
Closest papers by meaning
- Learning to Learn in Interactive Constraint Acquisition (AAAI 2024 · similarity 0.84)
- Learning Valid Dual Bounds in Constraint Programming: Boosted Lagrangian Decomposition with Self-Supervised Learning (AAAI 2025 · similarity 0.83)
- Generalizing Constraint Models in Constraint Acquisition (AAAI 2025 · similarity 0.83)
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.83)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.82)
- Self-Supervised Transformers as Iterative Solution Improvers for Constraint Satisfaction (ICML 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.