Titulo Estágio
Exact and evolutionary multiobjective optimisation of network topologies
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
DEI
Enquadramento
Network topology optimisation problems commonly arise in the utilities (electricity, gas, and water), computer and telecommunications industries, among others. They typically involve the minimisation of the network cost, including fixed, operational, and maintenance costs, under capacity and, eventually, reliability constraints.
Network topologies may vary considerably. For example, power transport and water distribution networks typically include cycles (loops) and multiple sources and sinks, whereas rooted-tree network topologies are common in power distribution, telecommunications and computer networks. Even the simplest formulations typically involve at least two objectives, one related to network connectivity and another related to network capacity. Such objectives are often non-linear, but even simplified linear formulations may result in optimisation problems that are hard to solve (in the computational sense), despite the fact that individual objectives can be evaluated easily.
Objetivo
This work is concerned with the study of multiobjective network topology optimisation problems and the development and evaluation of optimisation algorithms to solve them, both exact and evolutionary. In particular, the so-called cable-trench (CT) problem will be considered, which is a combination of the single-source shortest-path (SSSP) and minimum-spanning-tree (MST) problems. Although both the SSSP and the MST problems can be solved in polynomial time, the CT problem has been shown to be NP-hard [1]. Therefore, it makes for a very interesting benchmark problem on which to test and evaluate different network optimisation algorithms.
Plano de Trabalhos - Semestre 1
1. Literature review on network topology optimisation, exact search procedures (including branch-and-bound) and evolutionary algorithms.
2. Development and implementation of an exact solver for the (single-objective) CT problem.
3. Development and implementation of evolutionary algorithms for the single-objective formulation of the CT problem.
4. Preliminary evaluation of the performance of the algorithms developed.
Plano de Trabalhos - Semestre 2
5. Development and implementation of an exact solver for the bi-objective formulation of the CT problem (SSSP-MST trade-off).
6. Development and implementation of evolutionary algorithms for the bi-objective formulation of the CT problem.
7. Comparative study involving the algorithms developed and other approaches from the literature, including a statistical analysis of their performance.
8. Extensions to other network topology optimisation problems (e.g., looped, degree-constrained or multiple source network design, network expansion) or application to realistic problem instances (e.g., power distribution).
9. Dissertation writing.
Condições
Ideally, candidates will have successfully completed the Evolutionary Computation course. The work will be carried out in the CISUC ECOS laboratories. A computer cluster is available to support the experimental evaluation of the algorithms developed.
Observações
References
[1] Francis J. Vasko, Robert S. Barbieri, Brian Q. Rieksts, Kenneth L. Reitmeyer, and Kenneth L. Stott Jr., "The cable trench problem: combining the shortest path and minimum spanning tree problems," in Computers & Operations Research, vol. 29, pp. 441-458, 2002.
Orientador
Carlos Manuel Mira da Fonseca
cmfonsec@dei.uc.pt 📩