Titulo Estágio
A programming interface for the implementation of combinatorial optimization algorithms
Áreas de especialidade
Sistemas Inteligentes
Engenharia de Software
Local do Estágio
DEI-FCTUC
Enquadramento
Although there are currently many software environments for optimisation with evolutionary algorithms and other metaheuristics, achieving a clear separation between problem and solver implementations remains a challenge. The main difficulty arises in connection with the implementation of search operators, such as mutation and recombination operators in evolutionary algorithms, which typically requires knowledge of how solutions are represented. As a result, search operators are seen as belonging neither to the problem or to the solver, but as standing somewhere between the two as entities of a third kind. Such search operator components must combine problem-specific and solver-specific information, forcing either the application developer to learn about the inner workings of the optimisation algorithms to be used or the solver developer to understand the details of each particular application.
In contrast, linear programming (LP) and mixed integer programming (MIP) solvers achieve a clear separation between the problem, which is specified using a declarative language, and the solver, which can be applied to any problem specified in that language, even if performance may depend strongly on how the problem itself is formulated. A negative aspect of this scenario is that MIP formulations often hide the structure of combinatorial problems from the solver, hindering performance and leading solver developers to devise ways to recover that information in some way in order to be competitive. Nevertheless, MIP solvers are probably the most successful family of optimisation software to date.
This Master’s thesis will explore the problem-specific and solver-specific aspects of local search and evolutionary search operators in order to achieve a complete separation between problem and solver implementations in the context of combinatorial optimisation with metaheuristics.
Objetivo
The main objectives of this work are the development of a programming interface specification for combinatorial optimisation problems and metaheuristic optimisation algorithms, and the proof-of-concept implementation of several metaheuristics and several combinatorial optimisation problems according to that specification. The development of a library to support modular building of problem implementations by practitioners and or of state-of-the-art solver implementations are additional objectives. Evaluation will consider the generality of the proposed approach and its performance implications, among other issues.
Plano de Trabalhos - Semestre 1
1. Familiarisation with existing software frameworks for optimisation with metaheuristics.
2. Study of geometric search operators in evolutionary algorithms and related concepts.
3. Programming interface specification.
4. Proof-of-concept implementation of search operators for a small set of illustrative combinatorial optimisation problems according to the proposed specification.
5. Intermediate report writing.
Plano de Trabalhos - Semestre 2
1. Implementation of state-of-the-art evolutionary and local search algorithms based on the proposed programming interface.
2. Selection and implementation of combinatorial application problems to be used as benchmark.
3. Evaluation of the proposed approach against existing alternative implementations.
4. Dissertation writing.
Condições
Good background in evolutionary computation, algorithms and data structures, and software development. The work will be carried out in the CISUC ECOS laboratories. A computer cluster is available to support the development and evaluation of the algorithms developed.
Observações
Co-advisor: Prof. Nuno Laranjeiro.
Orientador
Carlos Manuel Mira da Fonseca
cmfonsec@dei.uc.pt 📩