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
Figure 1: Architecture of the propagator ranking model.
Figure 2: Distribution of instances by median solver runtime over measured randomized propagator orderings.
Figure 3: Impact of propagator ordering on solving time. Bars indicate the percentage of instances for which the ratio between the slowest and fastest randomized ordering exceeds the corresponding threshold.
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%
Table 1: Comparison between Choco’s default propagator ordering and the learned threshold pair-mining model on the hard test set.
Def. runtime
n
Solved def.
Solved model
Runtime def./model
<10 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
Table 2: Model performance by instance difficulty, where difficulty is measured by Choco’s default solver runtime. Runtime values report median solver runtime in each group.
Class
n
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
Table 3: Problem classes with the largest improvements and regressions under the learned threshold pair-mining model. PAR1 diff is the aggregate Choco solver runtime of the default ordering minus that of the learned ordering, with timeouts counted as 1200s. Median values report Choco solver runtime.
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%
Table 4: Comparison between the ungated threshold model and the validation-based gated policy on the test set. The gated policy chooses between the learned threshold model and Choco’s default ordering based on validation PAR1 walltime for each problem class. Positive percentages indicate improvement of the gated policy over the ungated model.
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
Table 5: Comparison of alternative pair-mining strategies. Aggregate times use PAR1, with timeouts counted as 1200s.