An Application Programming Interface for Constructive Search

Abstract

A utilização prática de otimização está intimamente relacionada com a disponibilidade de ferramentas de software para a suportar. As abordagens atuais para otimização combinatória caem em duas categorias: modelos de caixa branca (ou transparente) tais como Programação Linear Inteira (ILP) e Programação por Restrições (CP), e modelos de problemas e algoritmos (tipicamente heurísticos) de caixa cinzenta/preta que são diretamente implementados em software. Estes últimos poderão ser mais flexíveis e fáceis de integrar em fluxos de trabalho existentes. Contudo, a falta de convenções para a modelação/implementação de problemas de otimização em software dificultam a sua adoção na prática. De facto, distintos frameworks de software de otimização tipicamente obrigam a que os problemas estejam implementados nessa framework. Para além disso, a maioria das frameworks focam-se principalmente em algoritmos de procura local ao invés de procura construtiva. Assim, surge uma oportunidade para o desenvolvimento de uma Interface de Programação de Aplicações (API) para problemas e algoritmos de procura construtiva.Esta API separa o (modelo do) problema do algoritmo que o resolve através da especificação de várias operações elementares e abstratas que os problemas precisam de implementar e que os algoritmos podem usar independentemente do problema. Tanto algoritmos exatos, como (meta)heurísticos são suportados, dos quais se destacam o Branch & Bound, o Beam Search, o GRASP, os algoritmos de Ant Colony Optimization, entre outros.As consequências da abstração proposta para o desenvolvimento de novos algoritmos de procura construtiva são também discutidos neste trabalho. Em particular, é conduzido um estudo sobre o efeito dos modelos de problemas no desempenho de algoritmos. Este estudo sugere que um melhor modelo poderá potencialmente beneficiar todos os algoritmos que o usam.

Optimization practice is intimately related to the availability of software tools to support it. Current approaches to combinatorial optimization typically fall into one of two broad classes: glass-box mathematical programming formulations and solvers such as Integer Linear Programming (ILP) and Constraint Programming (CP), and black/grey-box problem models and (usually heuristic) algorithms implemented directly in software. The latter may be more flexible and easier to integrate into existing workflows. However, the lack of a de-facto standard for modelling/implementing optimization problems in software hinders its adoption in practice. In fact, different optimization software frameworks usually require problems to be implemented in that framework. In addition, most frameworks strongly emphasize local search algorithms over constructive search. Thus, an opportunity arises for the development of an Application Programming Interface (API) for constructive-search problems and algorithms.This API separates the problem formulation from the algorithm that solves it by specifying a number of abstract elementary operations that problems must implement and solvers can use in a problem-independent way. Both exact and (meta)heuristic algorithms are supported, including Branch & Bound, Beam Search, GRASP, Ant Colony Optimization algorithms, among others.The implications of the proposed abstraction for the development of novel constructive-search algorithms are also discussed in this work. Notably, a study is conducted on the effect of the problem model on solver performance. This study suggests that improved models may potentially benefit all solvers that use them.