AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Reactive Dialectic Search Portfolios for MaxSAT
Carlos Ansótegui, Josep Pon, Meinolf Sellmann, Kevin Tierney

Last modified: 2017-02-12

Abstract


Metaheuristics have been developed to provide general purpose approaches for solving hard combinatorial problems. While these frameworks often serve as the starting point for the development of problem-specific search procedures, they very rarely work efficiently in their default state. We combine the ideas of reactive search, which adjusts key parameters during search, and algorithm configuration, which fine-tunes algorithm parameters for a given set of problem instances, for the automatic compilation of a portfolio of highly reactive dialectic search heuristics for MaxSAT. Even though the dialectic search metaheuristic knows nothing more about MaxSAT than how to evaluate the cost of a truth assignment, our automatically generated solver defines a new state of the art for random weighted partial MaxSAT instances. Moreover, when combined with an industrial MaxSAT solver, the self-assembled reactive portfolio was able to win four out of nine gold medals at the recent 2016 MaxSAT Evaluation on random, crafted, and industrial partial and weighted-partial MaxSAT instances.

Keywords


heuristic search; reactive search; optimization; maxsat

Full Text: PDF