Probing features for automatic algorithm selection for pseudo-boolean optimization

Read full text Summarise with VIRAT
Authors: Amanda Paz Salinas Pinto
Cited by: 0

Summary

No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.

Summarise with VIRAT Free to try with your Science Catalogs account.

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 thesis addresses this gap by systematically integrating and evaluating probing features within AAS frameworks for PBO. The study investigates their effectiveness across multiple machine learning paradigms, including regression-based models, multiclass and multilabel classification approaches, and a novel hybrid framework that combines predictive and decision-oriented strategies. The outcome of this investigation is MetaPB, a new open-source meta-solver that leverages both static and probing features to improve solver selection performance. Extensive empirical evaluation on benchmark instances from the 2024 PBO Competition demonstrates that MetaPB consistently outperforms the best individual solver in the portfolio. Furthermore, despite relying exclusively on open-source(...).

Fields of Study & Subjects

Constraint Satisfaction and Optimization Metaheuristic Optimization Algorithms Research Machine Learning and Data Classification

Publication details

Journal / source
CRIS
Publication date
23 March 2026
Language
EN