Generative Adversarial Construction of Parallel Portfolios

Shengcai LIU, Ke TANG, Xin YAO

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

20 Citations (Scopus)

Abstract

Since automatic algorithm configuration methods have been very effective, recently there is increasing research interest in utilizing them for automatic solver construction, resulting in several notable approaches. For these approaches, a basic assumption is that the given training set could sufficiently represent the target use cases such that the constructed solvers can generalize well. However, such an assumption does not always hold in practice since in some cases, we might only have scarce and biased training data. This article studies effective construction approaches for the parallel algorithm portfolios that are less affected in these cases. Unlike previous approaches, the proposed approach simultaneously considers instance generation and portfolio construction in an adversarial process, in which the aim of the former is to generate instances that are challenging for the current portfolio, while the aim of the latter is to find a new component solver for the portfolio to better solve the newly generated instances. Applied to two widely studied problem domains, that is, the Boolean satisfiability problems (SAT) and the traveling salesman problems (TSPs), the proposed approach identified parallel portfolios with much better generalization than the ones generated by the existing approaches when the training data were scarce and biased. Moreover, it was further demonstrated that the generated portfolios could even rival the state-of-the-art manually designed parallel solvers. © 2013 IEEE.
Original languageEnglish
Pages (from-to)784-795
Number of pages12
JournalIEEE Transactions on Cybernetics
Volume52
Issue number2
Early online date29 Apr 2020
DOIs
Publication statusPublished - Feb 2022
Externally publishedYes

Keywords

  • Automatic portfolio construction (APC)
  • generative adversarial approach
  • parallel algorithm portfolio
  • parameter tuning

Fingerprint

Dive into the research topics of 'Generative Adversarial Construction of Parallel Portfolios'. Together they form a unique fingerprint.

Cite this