# Automatic Algorithm Selection for Pseudo-Boolean Optimization with Given Computational Time Limits

arXiv: https://arxiv.org/abs/2309.03924 · HTML: https://mlsanity.com/paper/2309.03924/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 84 references that are in the map.
- First posted on arXiv 7 Sep 2023.

## Builds on (most cited first, 10 of 10)

- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [A Survey on the Explainability of Supervised Machine Learning](https://mlsanity.com/paper/2011.07876/) (2020)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [ASlib: A Benchmark Library for Algorithm Selection](https://mlsanity.com/paper/1506.02465/) (2015)
- [Machine Learning Methods in Solving the Boolean Satisfiability Problem](https://mlsanity.com/paper/2203.04755/) (2022)
- [The Algorithm Selection Competitions 2015 and 2017](https://mlsanity.com/paper/1805.01214/) (2018)
- [Solver Scheduling via Answer Set Programming](https://mlsanity.com/paper/1401.1024/) (2014)
- [A Multi-Engine Approach to Answer Set Programming](https://mlsanity.com/paper/1306.4925/) (2013)
- [Incremental Cardinality Constraints for MaxSAT](https://mlsanity.com/paper/1408.4628/) (2014)

## Abstract (arXiv)

Machine learning (ML) techniques have been proposed to automatically select the best solver from a portfolio of solvers, based on predicted performance. These techniques have been applied to various problems, such as Boolean Satisfiability, Traveling Salesperson, Graph Coloring, and others. These methods, known as meta-solvers, take an instance of a problem and a portfolio of solvers as input. They then predict the best-performing solver and execute it to deliver a solution. Typically, the quality of the solution improves with a longer computational time. This has led to the development of anytime selectors, which consider both the instance and a user-prescribed computational time limit. Anytime meta-solvers predict the best-performing solver within the specified time limit. Constructing an anytime meta-solver is considerably more challenging than building a meta-solver without the "anytime" feature. In this study, we focus on the task of designing anytime meta-solvers for the NP-hard optimization problem of Pseudo-Boolean Optimization (PBO), which generalizes Satisfiability and Maximum Satisfiability problems. The effectiveness of our approach is demonstrated via extensive empirical study in which our anytime meta-solver improves dramatically on the performance of Mixed Integer Programming solver Gurobi, which is the best-performing single solver in the portfolio. For example, out of all instances and time limits for which Gurobi failed to find feasible solutions, our meta-solver identified feasible solutions for 47% of these.