Sequential Time Splitting and Bounds Communication for a Portfolio of Optimization Solvers
Roberto Amadini, Peter J. Stuckey · 2014
Abstract. Scheduling a subset of solvers belonging to a given portfolio has proven to be a good strategy when solving Constraint Satisfaction Problems (CSPs). In this paper, we show that this approach can also be effective for Constraint Optimization Problems (COPs). Unlike CSPs, sequential execution of optimization solvers can communicate informa-tion in the form of bounds to improve the performance of the following solvers. We provide a hybrid and flexible portfolio approach that com-bines static and dynamic time splitting for solving a given COP. Empiri-cal evaluations show the approach is promising and sometimes even able to outperform the best solver of the porfolio. 1 Introduction and Related Work One of the main uses of Constraint Programming (CP) is to model and solve Constraint Satisfaction Problems (CSP) [19]. Solving CSPs is hard, and there are plenty of approaches that can be used to tackle them. One of the more recent trend in this research area—especially in the SAT field—is trying to solve a given