.png){kind=icon}
.png){kind=icon}
Return
Automatic algorithm selection for Pseudo-Boolean optimization with given computational time limits
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2024.106836.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Machine learning (ML) techniques have been proposed to automatically select the best solver from a portfolio of solvers. They have been applied to various problems including Boolean Satisfiability, Traveling Salesperson and Graph Coloring. These techniques are used to implement meta-solvers that receive, as input, the instance of a problem, predict the best-performing solver in the portfolio, 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 meta-solvers, , 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. In this study, we focus on 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, named PBO_MS, improves dramatically on the performance of Mixed Integer Programming solver Gurobi, which is the best-performing single solver in the portfolio. We generalize the anytime meta-solver by predicting a given number p >= 1 of best solvers in the portfolio and then run these, each with equal share of the specified time limit. This anytime p-meta-solver is shown here to outperform both the anytime 1-meta-solver as well as a fixed selection of p solvers by a wide margin.
Keywords:
Algorithm selection
PBO
Combinatorial optimization
ML
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
View more organizations