Automatic construction of parallel portfolios via explicit instance grouping

Shengcai LIU, Ke TANG, Xin YAO

Research output: Journal PublicationsJournal Article (refereed)peer-review

17 Citations (Scopus)

Abstract

Exploiting parallelism is becoming more and more important in designing efficient solvers for computationally hard problems. However, manually building parallel solvers 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 configuration 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 on two widely studied problem domains, the boolean satisfiability problems (SAT) and the traveling salesman problems (TSP), 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. © 2019, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Original languageEnglish
Pages (from-to)1560-1568
Number of pages9
JournalProceedings of the AAAI Conference on Artificial Intelligence
Volume33
Issue number1
DOIs
Publication statusPublished - 2019
Externally publishedYes

Bibliographical note

This work was supported by the National Key Research and Development Program of China (Grant No. 2017YFB1003102), the Natural Science Foundation of China (Grant Nos. 61672478 and 61806090), Shenzhen Peacock Plan (Grant No. KQTD2016112514355531), and the Program for University Key Laboratory of Guangdong Province(Grant No. 2017KSYS008).

Fingerprint

Dive into the research topics of 'Automatic construction of parallel portfolios via explicit instance grouping'. Together they form a unique fingerprint.

Cite this