Automatic Construction of Parallel Portfolios via Explicit Instance Grouping

Liu, Shengcai1; Tang, Ke2; Yao, Xin2

2019

THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE

1560-+

2275 E BAYSHORE RD, STE 160, PALO ALTO, CA 94303 USA

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE

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.

通讯

英语

CPCI-S ; EI

Program for University Key Laboratory of Guangdong Province[2017KSYS008]

Computer Science ; Engineering

Computer Science, Artificial Intelligence ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic

WOS:000485292601070

20203509101420

Domain Knowledge ; Formal logic

Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Artificial Intelligence:723.4 ; Operations Research:912.3 ; Optimization Techniques:921.5

Web of Science

1.Univ Sci & Technol China, Sch Comp Sci & Technol, Hefei 230027, Anhui, Peoples R China
2.Southern Univ Sci & Technol, Univ Key Lab Evolving Intelligent Syst Guangdong, Dept Comp Sci & Engn, Shenzhen 518055, Peoples R China

Liu, Shengcai,Tang, Ke,Yao, Xin. Automatic Construction of Parallel Portfolios via Explicit Instance Grouping[C]. 2275 E BAYSHORE RD, STE 160, PALO ALTO, CA 94303 USA:ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE,2019:1560-+.