Introduction
Constraint Programming (CP) offers a robust framework for solving complex combinatorial problems such as scheduling and resource allocation. However, the "modeling bottleneck"—the difficulty of translating real-world requirements into formal constraint networks—remains a significant barrier to widespread adoption. Constraint Acquisition (CA) systems like QUACQ attempt to automate this process by interacting with users through queries. While effective, these systems often require an exhaustive number of queries, leading to user fatigue. This paper introduces P-QUACQ, a hybrid system that leverages recommendation queries and link-prediction techniques to streamline the acquisition process.
The P-QUACQ Framework
The core innovation of P-QUACQ is the introduction of Recommendation Queries. Unlike standard classification queries that ask if a complete or partial assignment is valid, a recommendation query asks the user to confirm whether a specific constraint belongs to the target problem.
To identify high-probability constraints for recommendation, the authors developed the PREDICT&ASK algorithm. This approach treats the evolving constraint network as a social graph where variables are nodes and constraints are edges. By applying link-prediction algorithms, the system can "predict" missing edges based on the existing topology.
Structural Signal and Link Prediction
Real-world constraint problems are rarely random; they typically exhibit strong topological patterns such as cliques or bicliques. P-QUACQ exploits this "structural signal" using two primary link-prediction indices:
- Adamic-Adar (AA): A neighborhood-based index effective at identifying cliques, which are common in logic puzzles where groups of variables are all mutually constrained.
- Leicht-Holme-Newman (LHN): A path-ensemble index superior at detecting biclique structures, often found in resource assignment problems like the Radio Link Frequency Assignment Problem (RLFAP).
Experimental Results
The authors evaluated P-QUACQ against the baseline QUACQ on several benchmarks. The results demonstrate a significant reduction in the total number of queries required to converge on the correct model:
- RLFAP: Using the LHN predictor, queries were reduced from 1,653 to 851 (a ~48% improvement).
- Murder Puzzle: The AA predictor reduced queries from 585 to 367.
- Zebra Problem: Queries dropped from 694 to 498 using the AA predictor.
Importantly, the computational cost of generating these recommendations is negligible (milliseconds), ensuring a smooth real-time experience for the user. Even when a recommendation is rejected, the "no" answer provides valuable information that helps prune the search space of possible constraints.
Conclusion
P-QUACQ significantly mitigates the modeling bottleneck by making CA systems more "intelligent" through structural prediction. By treating constraint acquisition as a link-prediction task, the system asks fewer, more informative questions. Future research may involve using reinforcement learning to dynamically select the most appropriate prediction strategy based on the observed problem structure during the acquisition process.
Summary updated