Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/98261
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Fonseca, Carlos Manuel Mira da | - |
dc.contributor.author | Outeiro, Samuel Barroca do | - |
dc.date.accessioned | 2022-02-02T23:10:29Z | - |
dc.date.available | 2022-02-02T23:10:29Z | - |
dc.date.issued | 2021-11-09 | - |
dc.date.submitted | 2022-02-02 | - |
dc.identifier.uri | https://hdl.handle.net/10316/98261 | - |
dc.description | Dissertação de Mestrado em Engenharia Informática apresentada à Faculdade de Ciências e Tecnologia | - |
dc.description.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. | por |
dc.description.abstract | 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. | eng |
dc.description.sponsorship | FCT | - |
dc.description.sponsorship | Outro - MobiWise: From Mobile Sensing to Mobility Advising (P2020 SAICTPAC/0011/2015), co-financed by COMPETE 2020, Portugal 2020 - Operational Program for Competitiveness and Internationalization (POCI), European Union’s European Regional Development Fund (ERDF), and the Foundation for Science and Technology (FCT) | - |
dc.language.iso | eng | - |
dc.relation | info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB/00326/2020/PT | - |
dc.rights | openAccess | - |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | - |
dc.subject | Procura Construtiva | por |
dc.subject | Otimização Combinatória | por |
dc.subject | Algoritmos Exatos | por |
dc.subject | Meta-heurísticas | por |
dc.subject | Software de Otimização | por |
dc.subject | Constructive Search | eng |
dc.subject | Combinatorial Optimization | eng |
dc.subject | Exact Algorithms | eng |
dc.subject | Metaheuristics | eng |
dc.subject | Optimization Software | eng |
dc.title | An Application Programming Interface for Constructive Search | eng |
dc.title.alternative | Uma Interface de Programação de Aplicações para Procura Construtiva | por |
dc.type | masterThesis | - |
degois.publication.location | DEI- FCTUC | - |
degois.publication.title | An Application Programming Interface for Constructive Search | eng |
dc.peerreviewed | yes | - |
dc.identifier.tid | 202921395 | - |
thesis.degree.discipline | Informática | - |
thesis.degree.grantor | Universidade de Coimbra | - |
thesis.degree.level | 1 | - |
thesis.degree.name | Mestrado em Engenharia Informática | - |
uc.degree.grantorUnit | Faculdade de Ciências e Tecnologia - Departamento de Engenharia Informática | - |
uc.degree.grantorID | 0500 | - |
uc.contributor.author | Outeiro, Samuel Barroca do::0000-0003-1064-6318 | - |
uc.degree.classification | 18 | - |
uc.degree.presidentejuri | Pereira, Vasco Nuno Sousa Simões | - |
uc.degree.elementojuri | Fonseca, Carlos Manuel Mira da | - |
uc.degree.elementojuri | Machado, Fernando Jorge Penousal Martins | - |
uc.contributor.advisor | Fonseca, Carlos Manuel Mira da::0000-0001-5162-2457 | - |
item.openairetype | masterThesis | - |
item.fulltext | Com Texto completo | - |
item.languageiso639-1 | en | - |
item.grantfulltext | open | - |
item.cerifentitytype | Publications | - |
item.openairecristype | http://purl.org/coar/resource_type/c_18cf | - |
Appears in Collections: | UC - Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Master_Thesis___An_Application_Programming_Interface_for_Constructive_Search___Final_Final_Document.pdf | 2.41 MB | Adobe PDF | View/Open |
Page view(s)
115
checked on Jul 16, 2024
Download(s)
181
checked on Jul 16, 2024
Google ScholarTM
Check
This item is licensed under a Creative Commons License