Overcoming Over-Fitting in Constraint Acquisition via Query-Driven Interactive Refinement

Manual modeling in Constraint Programming is a bottleneck, which Constraint Acquisition (CA) aims to alleviate. However, passive CA methods are prone to over-fitting when trained on limited data, often learning models that include spurious global constraints, while active methods can be query-intensive. We introduce HCAR, a hybrid CA framework designed to address the challenge of over-fitting in CA. HCAR integrates three phases: (1) passive learning for initial candidate generation from examples, (2) a novel query-driven interactive refinement phase that utilizes probabilistic confidence scores — initialized by machine learning priors and updated via Bayesian reasoning — to identify and correct over-fitted constraints, and (3) an active learning phase to ensure model completeness. Extensive experiments demonstrate that HCAR achieves 100% solution-space precision and 100% recall across all problems when learning from only five positive examples, compared to 33%–82% recall for hybrid baselines without our refinement phase. Starting from initial biases containing 27–118 candidate global constraints, HCAR successfully refines these down to accurate final models, correctly learning all target constraints. Our framework advances CA by providing robust learning in data-limited scenarios, in which over-fitting is the primary challenge.