Algorithm Selection is essential for efficient Constraint Programming. Over the years, many algorithm selectors based on machine learning methods have been successfully applied, yet traditional feature extraction methods often rely on manually decided instance-level statistics that fail to capture the underlying problem structure. In this paper we aim to bridge this gap by introducing a novel, automated feature extraction methodology that integrates graph conversion and Weisfeiler-Lehman graph kernels to generate robust structural representations of problem instances. The 1-WL test bounds the graph-distinguishing power of standard message-passing Graph Neural Networks (GNNs), and suitable GNN architectures match this bound \citep{Xuetal2018}. WL-based features offer an alternative that does not require training a GNN. Our primary contribution is a cut-based representation (\texttt{WLc}) designed to model structural partitions and provide a more nuanced predictive signal. We evaluate our approach on instances from the 2023--2025 MiniZinc Challenges across two tasks: maximizing Borda count scores and maximizing predictive accuracy. Experimental results across Support Vector Machines, Random Forests, and Multi-Layer Perceptrons demonstrate that cut-based features outperform \texttt{fzn2feat} with SVMs, while results with RFs and MLPs are closer.
Figures & tables
Figure 1 : Conversion of a constraint model (left) to a graph (right). Variables in yellow, Parameters in blue, Operators in red, Constraints in purple, and Solve in green. The area in gray represents the constraint 3*x <= y . Lead edges are labelled as L, Trailing as T and Global as G.
Figure 2 : Feature extraction process using the WL algorithm on a simple, undirected graph. The colour refinement is executed only once. At first, all nodes get the same colour, then node A aggregates its colour (blue) with its 3 neighbours’ colours (blue), getting, as a result, (blue, blue,blue,blue). This produces a new colour, red. C and D, having only two neighbours, get, as aggregation (blue, blue,blue), resulting in the new colour yellow and, finally, node B, having only one neighbour, aggregates to (blue, blue), getting as new colour orange. In the final steps, we count the number of occurrences of each colour, and we get 4 blues from the original initialisation and 1 red, 1 orange and 2 yellow after the first aggregation step.
Figure 4 : Performance results for SVM models trained on WL -based and fzn2feat features for the Borda count maximization task. Scores (top) are normalized as Snorm=Svbs−SsbsS−Ssbs , where S is the model score, sbs is the Single Best Solver, and vbs is the Virtual Best Solver.
Figure 5 : Comparative performance of cut-based features ( WLc-n/WLc-ne ) against the fzn2feat baseline for the Borda count maximization task. Scores are normalised relative to the Single Best Solver and Virtual Best Solver. Results on the left are obtained by training RF models, while those on the right are obtained by training MLPs.
Mean
Median
fzn2feat
0.45
0.47
Wlc-n-1
0.48
0.51
Wlc-n-2
0.47
0.50
Wlc-ne-1
0.46
0.51
Wlc-ne-2
0.48
0.48
Table 1 : Mean and median results of cut features and fzn2feat . Results show the best performing scores obtained using SVM for cut features and RF for fzn2feat .
Figure 6 : Predictive accuracy for SVM models trained on WL -based and fzn2feat features.
Figure 7 : Comparative performance of cut-based features ( WLc-n/WLc-ne ) against fzn2feat and the majority classifier (MC) baseline. Results on the left are obtained by training RF models, while those on the right are obtained by training MLPs.
Mean
Median
fzn2feat
0.66
0.67
Wlc-n-1
0.69
0.68
Wlc-n-2
0.69
0.69
Wlc-ne-1
0.69
0.69
Wlc-ne-2
0.69
0.69
Table 2 : Mean and median results of cut features and fzn2feat . Results show the best performing scores obtained using SVM for cut features and RF for fzn2feat .
Figure 8 : Feature extraction cost comparison between WLc-n / WLc-ne and fzn2feat . The distribution of extraction times (left) is supplemented by pairwise performance comparisons (centre, right). The blue line corresponds to x = y.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Name
Type
Subtype
Is Cut
Is Global
Description
Variable
variable
–
No
No
Problem variable
Parameter
parameter
–
No
No
Literal value or parameter
Multiply
operator
mul_node
No
No
Multiplication operator
Linear Sum
operator
lin_sum_node
Yes
No
Weighted sum of variables
Sum
operator
sum_node
No
No
Sum operator
Equality
constraint
equality_node
No
No
Equality constraint
Appendix
Table 3 : Node types used in our graphs converted from FlatZinc.
Figure 10 : Results of all feature sets trained with the RF classifier on the Borda count maximisation task.
Figure 11 : Results of all feature sets trained with the MLP classifier on the Borda count maximisation task.
Figure 12 : Results of all feature sets trained with the RF classifier on the Algorithm Selection accuracy maximisation task.
Figure 13 : Results of all feature sets trained with the MLP classifier on the Algorithm Selection accuracy maximisation task.
Table 4 : Results of the ML models trained for Borda count maximisation on WL features with (all-levels) and without (last) all aggregation levels. Results report mean and median scores, as well as the p-value calculated with the Wilcoxon test.
Table 5 : Results of the ML models trained for algorithm selection accuracy maximisation on WL features with (all-levels) and without (last) all aggregation levels. Results report mean and median scores, as well as the p-value calculated with the Wilcoxon test.
Table 6 : Results of the ML models trained for parallel prediction on WL features with (all-levels) and without (last) all aggregation levels. Results report mean and median scores, as well as the p-value calculated with the Wilcoxon test.
Large neighborhood search normally selects a random subset of decision variables for iterative optimization. For efficiently solving different problems, researchers tend to design variable selection strategies by taking into account structural features from different domains. In this paper, we build an automatic pipeline that is problem-agnostic to all problems in the MiniZinc format. By prompting an LLM with our semantic guidelines, we guide the LLM to produce a graph generator that maps any instance of a problem type to a uniform weighted graph, where nodes represent decision variables and edges represent constraint relationships. These problem-agnostic graphs guide our structure-based local improvement framework (SLIM) in variable selection. Meanwhile, the weighted graph enables all problem instances to share the same generic graph representation, from which the same graph features can be extracted and used for configuration selection. We evaluated our pipeline on instances across 20 MiniZinc competition problems, finding that algorithm selection achieves a 39.5% average problem-weighted win rate against a one-shot Gurobi baseline, more than doubling the best single configuration (19.3%). Configuration and feature ablation boost the performance further to 44.0%, demonstrating that LLM-based semantic generation enables effective automated structure extraction and feature extraction for constraint optimization.
Hai Xia, Vaidyanathan Peruvemba Ramaswamy, Stefan Szeider
We propose ZeroFolio, a feature-free approach to algorithm selection that uses pretrained text embeddings instead of hand-crafted instance features. It reads the raw instance file as plain text, embeds it with a pretrained embedding model, and selects an algorithm via weighted k-nearest neighbors. Our approach is based on the observation that pretrained embeddings can distinguish problem instances without any domain knowledge or task-specific training. ZeroFolio applies to any problem domain with text-based instance formats. We evaluate our approach on 11 ASlib scenarios spanning 7 domains (SAT, MaxSAT, QBF, ASP, CSP, MIP, and graph problems). ZeroFolio outperforms a random forest trained on hand-crafted features in 9 of 11 scenarios, often substantially, and in 8 of them with every serialization seed. It wins 8 of 11 scenarios against a per-scenario-tuned random forest. On the three scenarios with published AutoFolio results from the 2015 ICON Challenge, ZeroFolio comes within a small margin of AutoFolio without any per-scenario tuning. Our ablation study on SAT12-ALL shows that inverse-distance weighting and line shuffling improve performance. We further analyze the sensitivity of our approach to the serialization seed. On the SAT12-ALL scenario, where the random forest is stronger, both methods can be combined via soft voting to achieve further improvements.
Stefan Szeider
Algorithms and Complexity Group TU Wien, Vienna, Austria
The Winner Determination Problem (WDP) in combinatorial auctions is NP-hard, and no existing method reliably predicts which instances will defeat fast greedy heuristics. The ML-for-combinatorial-optimization community has focused on learning to \emph{replace} solvers, yet recent evidence shows that graph neural networks (GNNs) rarely outperform well-tuned classical methods on standard benchmarks. We pursue a different objective: learning to predict \emph{when} a given instance is hard for greedy allocation, enabling instance-dependent algorithm selection. We design a 20-dimensional structural feature vector and train a lightweight MLP hardness classifier that predicts the greedy optimality gap with mean absolute error 0.033, Pearson correlation 0.937, and binary classification accuracy 94.7% across three random seeds. For instances identified as hard -- those exhibiting ``whale-fish'' trap structure where greedy provably fails -- we deploy a heterogeneous GNN specialist that achieves ≈0% optimality gap on all six adversarial configurations tested (vs.\ 3.75--59.24% for greedy). A hybrid allocator combining the hardness classifier with GNN and greedy solvers achieves 0.51% overall gap on mixed distributions. Our honest evaluation on CATS benchmarks confirms that GNNs do not outperform Gurobi (0.45--0.71 vs.\ 0.20 gap), motivating the algorithm selection framing. Learning \emph{when} to deploy expensive solvers is more tractable than learning to replace them.
Sungwoo Kang
Department of Electrical and Computer Engineering Korea University Seoul 02841, Republic of Korea