Research map / Label-efficient and robust learning / Recognition and long-tail
Generalizing Constraint Models in Constraint Acquisition
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.
Proposes GenCon, which learns parameterized constraint specifications from ground constraints of several problem instances by training a constraint-level classifier, extracting decision rules (DT, CN2) or using generate-and-test with any classifier.
Problem
Constraint acquisition methods learn ground constraints for a single instance and cannot generalize them to parameterized constraint specifications that apply across instances of the same problem.
Approach
Cast generalization as constraint-level binary classification over a parameterized feature representation (relation, partition and sequence features with numeric values mapped to parameter names); decision rules for positive classes are converted into constraint specifications, or a generate-and-test loop uses any classifier to filter candidate constraints for new instances.
Key results
- Decision-tree and generate-and-test variants with RF/MLP/KNN achieve near-100% precision and recall across the four benchmarks, while Count-CP reaches only partial recall on Nurse Rostering and Sudoku.
- Naive Bayes gets lower recall in Exam Timetabling and Nurse Rostering and significantly lower precision in Sudoku.
- CN2 and NB are the most sensitive to false-positive noise, while Count-CP fails to generalize even at 5% false-negative noise.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Naive Bayes instead of other evaluated classifiers | GenCon · Exam Timetabling and Nurse Rostering | recall | Hurt |
| Use Naive Bayes instead of other evaluated classifiers | GenCon · Sudoku | precision | Hurt |
| Use Count-CP generalization | constraint model generalization · Nurse Rostering and Sudoku | recall | Hurt |
| Manually provide custom partitions | Count-CP · Sudoku | recall: increased to 100% | Helped |
| Include special features for custom partitions | GenCon · Sudoku | recall: increase to 100% | Helped |
| Add false-positive noise to the input constraints | GenCon with CN2 or Naive Bayes · All benchmarks | precision | Hurt |
| Add false-positive noise to the input constraints | GenCon with Random Forest, MLP, or KNN · All benchmarks | precision | No clear effect |
| Add false-positive noise to the input constraints | Count-CP · All benchmarks | precision and recall | No clear effect |
| Add false-negative noise to the input constraints | GenCon with KNN · All benchmarks | recall | Hurt |
| Add false-negative noise to the input constraints | GenCon with CN2 · All benchmarks | precision and recall: above 80% | Hurt |
| Add false-negative noise to the input constraints | GenCon with classifiers other than CN2 and KNN · All benchmarks | precision and recall: up to 20% | No clear effect |
| Add false-negative noise to the input constraints | Count-CP · All benchmarks | constraint generalization: only 5% | Hurt |
Surprising findings
- Count-CP fails to generalize at all under only 5% false-negative noise, finding no constraints in target instances.
- All methods struggle most on Exam Timetabling, where instances with many parameters sharing the same value cause extra constraints to be generated.
Limitations
- Arbitrary constants cannot be captured by the parameterized features; constants are assumed related to parameters.
- Naive Bayes and CN2 are sensitive to noise, and the exam timetabling benchmark causes ambiguity between parameters with equal values.
- The proof-of-concept feature representation relies on matrix structure and does not include problem-specific variable attributes.
Experimental setup
Datasets: Sudoku instances (generated) Golomb ruler instances (generated) Exam timetabling instances (generated) Nurse rostering instances (generated)
Benchmarks: Sudoku Golomb Exam Timetabling Nurse Rostering
Metrics: precision recall
Baselines: Count-CP generalization
Builds on: Count-CP CPMpy ModelSeeker
Closest papers by meaning
- Learning to Learn in Interactive Constraint Acquisition (AAAI 2024 · similarity 0.89)
- What Are the Rules? Discovering Constraints from Data (AAAI 2024 · similarity 0.83)
- ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation (ICML 2024 · similarity 0.83)
- DeepSaDe: Learning Neural Networks That Guarantee Domain Constraint Satisfaction (AAAI 2024 · similarity 0.82)
- Feasibility-Aware Decision-Focused Learning for Predicting Parameters in the Constraints (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.