Abstract

For NP-hard problems like Pseudo-Boolean Optimization (PBO), solver performance varies dramatically across instances, making algorithm selection a critical bottleneck. Current Automatic Algorithm Selection (AAS) systems for PBO depend primarily on static problem features, ignoring crucial dynamic information. In contrast, AAS for Boolean Satisfiability (SAT) has demonstrated that probing features, gathered from short solver runs, are essential for making high-quality, time-sensitive predictions. This work improves AAS for PBO by systematically integrating and evaluating these powerful probing features. We investigate their impact across a range of machine learning frameworks, including regression, multiclass/multilabel classification, and a novel hybrid model. This investigation culminates in MetaPB, a new open-source meta-solver that combines both static and probing features for superior solver selection. On benchmarks from the 2024 PBO competition, MetaPB outperforms the best individual solver in its portfolio [by X%]. Remarkably, it achieves performance competitive with Gurobi — a leading commercial solver — while using an entirely open-source portfolio. This study not only establishes a new state of the art for AAS in PBO but also challenges the prevailing view of algorithm selection as a pure classification task, highlighting the power of hybrid, regression-informed approaches.