Titulo Estágio
An Application Programming Interface for Constructive Search
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
DEI
Enquadramento
Combinatorial optimisation algorithms can be broadly divided into two classes: local search approaches and constructive search approaches. Local search approaches work by iteratively trying to improve a current solution by modifying it in some way. The rules that govern such modifications define a neighbourhood structure on the search space, and a solution that is at least as good as any other solution in its neighbourhood is called a local optimum. Thus, local search approaches solve a local formulation of a global optimisation problem. The absolute quality of the locally optimal solutions thus obtained depends critically on the choice of neighbourhood, even if also on the details of the local search algorithm itself. Although neighbourhoods are usually defined based on the internal structure of the solutions and on how solution components contribute to overall solution quality, the search algorithms themselves can only access the external neighbourhood structure and an a measure of the overall quality of each solution.
In contrast, constructive approaches depend on and directly exploit knowledge of the internal structure of solutions, often in combination with how solution components affect overall solution quality. For this reason, constructive approaches are potentially more powerful than pure local search approaches on problems where the relation between internal solution structure and overall solution quality is well understood. Constructive search approaches include exact implicit enumeration approaches such as Dynamic Programming and Branch and Bound, as well as heuristic approaches such as Ant Colony Optimisation and GRASP algorithms.
It has been pointed out that constructive search can also be interpreted as a local search procedure acting on an extended search space that includes complete and incomplete solutions, where the neighbourhood structure is defined by the applicable construction rules. This Master’s thesis will explore the potential of such a unifying view of constructive and local search in connection with the software implementation of both problems and solvers.
Objetivo
The main objective of this work is the extension of the CA15140 Combinatorial Optimisation API (https://github.com/cmfonseca/nasf4nio) to support constructive search by exploring the connections between local search and constructive search, and the proof-of-concept implementation of several combinatorial optimisation problems and solvers, both exact and heuristic, according to that specification. 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 constructive search and for local search
2. Implementation of constructive search algorithms for a small set of illustrative combinatorial optimisation problems according to an established constructive search framework
3. Preliminary proposal of an extension of the CA15140 Combinatorial Optimisation API to support constructive search
4. Intermediate report writing
Plano de Trabalhos - Semestre 2
1. Selection and implementation of combinatorial optimisation problems to be used as benchmarks
2. Implementation of state-of-the-art constructive search algorithms based on the proposed API
3. Evaluation of the proposed approach against existing alternative implementations
4. Dissertation writing
Condições
Good background in algorithms, data structures and evolutionary computation. The work will be carried out in the CISUC AC laboratories.
Orientador
Carlos Manuel Mira da Fonseca
cmfonsec@dei.uc.pt 📩