Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning to Learn in Interactive 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.
Uses probabilistic classifiers (mainly Random Forests) trained on relation- and scope-based features to predict whether candidate constraints are in the target network, and uses these predictions to guide query generation in all layers of GrowAcq/MQuAcq-2 interactive constraint acquisition.
Problem
Interactive constraint acquisition needs a large number of queries to learn a constraint model, because the search is largely uninformed about patterns in the constraints learned so far.
Approach
Train classifiers incrementally on the constraints learned and removed from the bias to estimate P(c in target), and use these probabilities in the objective functions of top-level query generation, FindScope, and FindC, instead of counting-based estimates based only on relation.
Key results
- Guiding query generation with Random Forest decreases the number of queries by up to 70% vs. the GrowAcq baseline and up to 56% vs. counting; the abstract reports up to 72%.
- Average query reduction across structured benchmarks is 52% vs. baseline and 32% vs. counting for the RF-guided method.
- Guiding all layers (FindScope and FindC) with RF yields an additional reduction of up to 22% (Exam TT) and about 10% on average over guiding only top-level query generation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Random Forest probabilities to guide top-level query generation | GrowAcq with MQuAcq-2 · Structured benchmarks | number of queries: 52% average decrease | Helped |
| Use Random Forest probabilities to guide top-level query generation | GrowAcq with MQuAcq-2 · All benchmarks | number of queries: up to 70% | Helped |
| Guide FindScope and FindC in addition to top-level query generation (ablation) | GrowAcq + RF guidance · Exam TT | number of queries: up to 22% | Helped |
| Guide FindScope and FindC in addition to top-level query generation (ablation) | GrowAcq + RF guidance · Benchmarks | number of queries: 10% | Helped |
| Use SVM probabilities to guide query generation | GrowAcq with MQuAcq-2 · Benchmarks | number of queries | No clear effect |
| Use GNB probabilities to guide query generation | GrowAcq with MQuAcq-2 · Random | number of queries | Hurt |
| Use Random Forest probabilities to guide query generation | GrowAcq with MQuAcq-2 · Benchmarks | maximum user waiting time: less than 2s | Mixed |
| Guide FindScope and FindC in addition to top-level query generation (ablation) | GrowAcq + RF guidance · Benchmarks | maximum user waiting time | Helped |
Surprising findings
- SVM-guided variants perform similarly to the unguided baseline because their early-stage accuracy is too low to give useful guidance.
- GNB overfits and does not give consistent guidance, including on the Random benchmark where no patterns should be found.
Limitations
- Assumes all user answers are correct; handling wrong answers is left to future work.
- Only fixed-arity binary constraints from a simple language are considered; global constraints and linear inequalities are not supported.
- Classifiers are retrained from scratch before each top-level query, which adds waiting time for SVM and MLP.
Experimental setup
Datasets: Random CSP (100 variables) 9x9 Sudoku Jigsaw Sudoku Exam Timetabling Nurse rostering
Benchmarks: Random 9x9 Sudoku Jigsaw Sudoku Exam Timetabling Nurse rostering
Metrics: number of queries maximum user waiting time accuracy balanced accuracy F1-score
Baselines: GrowAcq base (no guiding) count-based guidance (Tsouros et al.) GNB SVM
Builds on: GrowAcq MQuAcq-2 PQ-Gen counting-based query guidance
Closest papers by meaning
- Generalizing Constraint Models in Constraint Acquisition (AAAI 2025 · similarity 0.89)
- Parallel Constraint Acquisition (AAAI 2021 · similarity 0.86)
- GEQCA: Generic Qualitative Constraint Acquisition (AAAI 2022 · similarity 0.86)
- What Are the Rules? Discovering Constraints from Data (AAAI 2024 · similarity 0.84)
- ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation (ICML 2024 · 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.