Learning to Rank Propagators in Constraint Programming
Organizations: Faculty of Mathematics, University of Belgrade, Studentski trg 16, Belgrade, 11000, Serbia.
Abstract
The order in which propagators are executed can substantially affect the performance of constraint programming solvers, yet propagator priorities are typically determined by fixed, manually designed heuristics. In this work, we explore learning instance-dependent propagator priorities from static problem features. We formulate the task as a learning-to-rank problem, addressing the challenge that the quality of a priority assignment can be measured through solver runtime, while the desired priorities of individual propagators are not directly observable. A self-attention-based model jointly scores the propagators present in an instance and is trained using pairwise preferences derived from solver runtimes measured under randomized propagator priority assignments, with a Plackett-Luce-based ranking objective. Predicted rankings are mapped to the discrete priority levels of the Choco solver before search begins, without modifying its propagation or search procedures. We evaluate the approach on XCSP3 instances and demonstrate that propagator ordering can have a substantial impact on solving time. On a test set of 698 instances, picked out as most difficult by problem class, the learned priorities increase the number of solved instances from 634 to 654, reduce median solver runtime by 27.93%, and reduce aggregate penalized runtime (PAR1) by 12.65% compared with Choco's default priorities. We further observe that improvements vary across problem classes and show that a simple policy selecting between learned and default priorities further increases the number of solved instances. These results demonstrate the potential of learning instance-dependent propagator priorities to improve constraint programming performance, particularly on difficult instances.
Figures & tables
| Metric | Default | Model | Improvement |
|---|---|---|---|
| Solved instances | 634/698 | 654/698 | +20 |
| Median walltime | 168.37s | 143.14s | 14.98% |
| Median solver runtime | 167.88s | 120.99s | 27.93% |
| Aggregate walltime, PAR1 | 235,653s | 210,410s | 10.71% |
| Aggregate solver runtime, PAR1 | 235,260s | 205,510s | 12.65% |
| Aggregate walltime, PAR2 | 312,453s | 263,210s | 15.76% |
| Def. runtime | Solved def. | Solved model | Runtime def./model | |
|---|---|---|---|---|
| s | 95 | 95 | 95 | 6.11s / 6.63s |
| 10s–60s | 143 | 143 | 141 | 29.95s / 35.32s |
| 1m–5m | 204 | 204 | 201 | 160.21s / 120.02s |
| 5m–20m | 192 | 192 | 179 | 566.09s / 447.09s |
| Timeout | 64 | 0 | 38 | 1200.00s / 1049.68s |
| Class | Solved def./model | PAR1 diff | Median def./model | |
|---|---|---|---|---|
| Largest improvements | ||||
| Crossword | 47 | 38 / 46 | 11,693s | 639.1s / 302.7s |
| Subisomorphism | 96 | 78 / 87 | 9,540s | 297.5s / 215.6s |
| qwh | 5 | 0 / 4 | 3,206s | 1200.0s / 376.9s |
| Wwtpp | 52 | 49 / 48 | 2,467s | 172.5s / 102.9s |
| SocialGolfers | 26 | 23 / 24 | 2,369s | 72.0s / 65.9s |
| Metric | Ungated model | Gated policy | Change |
|---|---|---|---|
| Solved instances | 654/698 | 657/698 | +3 |
| Median walltime | 143.14s | 129.93s | 9.24% |
| Median solver runtime | 120.99s | 127.83s | -5.66% |
| Aggregate walltime, PAR1 | 210,410s | 204,399s | 2.86% |
| Aggregate solver runtime, PAR1 | 205,510s | 203,252s | 1.10% |
| Aggregate walltime, PAR2 | 263,210s | 253,599s | 3.65% |
| Variant | Solved | Agg. walltime | Agg. solver | Med. walltime | Med. solver |
|---|---|---|---|---|---|
| Threshold | 654/698 | 210,410s | 205,510s | 143.14s | 120.99s |
| Weighted | 650/698 | 212,447s | 207,596s | 139.04s | 121.87s |
| Top-K/bottom-K | 647/698 | 210,377s | 205,435s | 137.20s | 119.80s |
| All pairs | 648/698 | 211,887s | 207,083s | 148.61s | 126.40s |
Constraint Programming
Constraint programming models combinatorial problems as variables and constraints, using propagation and search to find feasible or optimal solutions.
See all 40 papers