Titulo Estágio
Exact and evolutionary multiobjective optimisation of network topologies
Área Tecnológica
Sistemas Evol. e Comp.
Local do Estágio
DEI / CISUC
Enquadramento
Network topology optimisation problems commonly arise in the utilities (power, 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. In addition, the planning of the expansion of existing (or even new) networks may be considered, since it is usually uneconomical to build a whole network at once, and demand typically grows in time as services become available.
Network topologies vary considerably depending on the application domain. For example, power distribution networks usually have a rooted-tree structure, whereas power transport and water distribution networks typically include cycles (loops) and multiple sources and sinks. Also, there may be additional constraints on the network, such as maximum edge length and/or node degree.
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 to network capacity. In an electrical network, for example, connectivity is related to the existence of power lines, whereas capacity depends on the grade of the cables used in each line stretch. Such objectives are often non-linear, and modelling the behaviour of real-world networks tends to involve more or less complex numerical calculations. However, even simplified linear formulations may result in optimisation problems that are hard to solve (in the computational sense), despite the fact that the 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 optimisers 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. 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.
Orientador
Carlos M. Fonseca
cmfonsec@dei.uc.pt 📩