Accelerating Parallel Algorithm Portfolio Construction

Parallel Algorithm Portfolio (PAP) is a promising approach to solving computationally hard problems efficiently. A portfolio is a set of problem solvers, each optimized for different problem types. However, the portfolio configuration process is computationally expensive, requiring numerous solver evaluations. This paper explores two methods to accelerate PAP construction. The first method leverages the vast amount of data generated during portfolio configuration to train a surrogate model, reducing the need for costly evaluations. The second method investigates training portfolios on smaller problem instances before applying them to more complex target instances. A comprehensive experimental study on the Traveling Salesman Problem instances demonstrates that both methods significantly reduce computational time, albeit at the cost of slightly reducing portfolio performance.