Reactive Dialectic Search Portfolios for MaxSAT

Authors

  • Carlos Ansótegui Universitat de Lleida
  • Josep Pon Universitat de Lleida
  • Meinolf Sellmann IBM Research
  • Kevin Tierney University of Paderborn

Keywords:

heuristic search, reactive search, optimization, maxsat

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.

Downloads

Published

2017-02-12

How to Cite

Ansótegui, C., Pon, J., Sellmann, M., & Tierney, K. (2017). Reactive Dialectic Search Portfolios for MaxSAT. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/10660

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization