Generating heuristics for the quadratic unconstrained binary optimization problem using automatic algorithm configuration

Abstract

In this work, we study an automated approach to the design of heuristic algorithms to solve the Quadratic Unconstrained Binary Optimization Problem (QUBO). Our approach is an extension of the work of Souza and Ritt (2018), who represent a design space of algorithms by a context-free grammar which is later explored by an algorithm configurator. We extend this work by introducing a new platform for design space exploration of heuristics for QUBO with a modular architecture and new components. Using this platform and the grammar-based approach, we were able to find algorithms that are very competitive and sometimes better than the state of the art in commonly used instances in the literature

Neste trabalho, estudamos uma abordagem automatizada para o projeto de algoritmos heurísticos para resolver o Problema de Otimização Binária Quadrática Ir restrita (QUBO). Nossa abordagem é uma extensão do trabalho de Souza and Ritt (2018), que representam um espaço de design de algoritmos por uma gramática li vre de contexto que posteriormente é explorada por um configurador de algoritmos. Estendemos este trabalho introduzindo uma nova plataforma para exploração do espaço de design de heurísticas para QUBO com uma arquitetura modular e no vos componentes. Usando essa plataforma e a abordagem baseada em gramática, conseguimos encontrar algoritmos muito competitivos e às vezes melhores do que o estado da arte em instâncias comumente usadas na literatura.