Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/98261
Title: An Application Programming Interface for Constructive Search
Other Titles: Uma Interface de Programação de Aplicações para Procura Construtiva
Authors: Outeiro, Samuel Barroca do
Orientador: Fonseca, Carlos Manuel Mira da
Keywords: Procura Construtiva; Otimização Combinatória; Algoritmos Exatos; Meta-heurísticas; Software de Otimização; Constructive Search; Combinatorial Optimization; Exact Algorithms; Metaheuristics; Optimization Software
Issue Date: 9-Nov-2021
Project: info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB/00326/2020/PT
Serial title, monograph or event: An Application Programming Interface for Constructive Search
Place of publication or event: DEI- FCTUC
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.
Description: Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia
URI: http://hdl.handle.net/10316/98261
Rights: openAccess
Appears in Collections:UC - Dissertações de Mestrado

Show full item record

Page view(s)

39
checked on Aug 19, 2022

Download(s)

36
checked on Aug 19, 2022

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons