Automatic Construction of Parallel Portfolios via Explicit Instance Grouping
This addresses the challenge of reducing human effort in building solver portfolios for computationally hard problems, though it appears incremental as it builds on existing automatic construction methods.
The paper tackles the problem of automatically constructing parallel portfolios for solving hard computational problems by explicitly grouping instances, and the proposed method achieved consistently superior performance compared to state-of-the-art automatic methods and rivaled hand-designed solvers.
Simultaneously utilizing several complementary solvers is a simple yet effective strategy for solving computationally hard problems. However, manually building such solver portfolios typically requires considerable domain knowledge and plenty of human effort. As an alternative, automatic construction of parallel portfolios (ACPP) aims at automatically building effective parallel portfolios based on a given problem instance set and a given rich design space. One promising way to solve the ACPP problem is to explicitly group the instances into different subsets and promote a component solver to handle each of them.This paper investigates solving ACPP from this perspective, and especially studies how to obtain a good instance grouping.The experimental results showed that the parallel portfolios constructed by the proposed method could achieve consistently superior performances to the ones constructed by the state-of-the-art ACPP methods,and could even rival sophisticated hand-designed parallel solvers.