Titulo Estágio
Exact algorithms for multiobjective spanning tree problems
Áreas de especialidade
Sistemas Inteligentes
Engenharia de Software
Local do Estágio
ECOS/CISUC
Enquadramento
Multiobjective minimum spanning tree problems arise in many real-life applications with several objectives; for instance, when planning a telecommunication network that minimizes the length of the cable and maximizes the network reliability. Clearly, there is no single optimal spanning tree for this problem, since the most reliable network may not be the one that uses less cable. Hence, for this problem, one has to develop algorithms whose output is a set of “trade-off” (also called efficient) spanning trees, and from which the a decision maker chooses the most preferable according to the application at hand. This problem is related to the (single-objective) minimum spanning tree problem, which can be solved with Kruskal's algorithm, but it is much harder to be solved.
Objetivo
In this project, the goal is to design, implement and analyse branch and bound algorithms for solving the multiobjective minimum spanning tree problem. The student should analyse and discuss the effect of several enumeration strategies and the running time of the branch-and-bound, as well as to relate it with some instance features such as the degree of conflict between the objectives and number of efficient solutions to be found.The best implementations should be publicly available at a git repository.
The enumeration of unique spanning trees is discussed in [1]. A MSc thesis about the min-max regret version of the minimum spanning tree problem presents a branch and bound approach, from which notions of upper and lower bounds can be used [2]. In addition, Sourd and Spanjaard [3] present a branch-and-bound algorithm for this problem. However, implementations of exact algorithms for the multiobjective minimum spanning tree problem are not publicly available.
Plano de Trabalhos - Semestre 1
1) Literature review on multiobjective optimization and spanning tree problems
2) Implementation of an enumeration algorithm based on the approach described in [1] and bounds based on [2].
3) Writing of the intermediate report
Plano de Trabalhos - Semestre 2
1) Implementation of the branch and bound, considering different enumerations methods and other notions of bound (see [3]).
2) Experimental analysis
3) Writing of the final report
Condições
This MSc project arises within an existent collaboration with Prof. Daniel Vanderpooten, from Paris-Dauphine University, and Prof. José R. Figueira, from IST, University of Lisbon. It is targeted for students that would like to deepen their knowledge on algorithms, data structures and efficient implementations. Therefore, the student should have an excellent grade on these topics at BSc and MSc level. The student can use the computational resources from ECOS group for performing experiments. This project has no funding available.
Observações
[1] N.G. Harold and E.W. Myers, Finding all spanning trees of directed and undirected graphs. SIAM Journal on Computing, 7(3):280--287, 1978.
[2] N. Godinho, Algorithms for the min-max regret spanning tree problem, MSc thesis in Informatics Engineering, University of Coimbra, 2017.
[3] F. Sourd and O. Spanjaard. A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem. INFORMS Journal on Computing, 20(3):472--484, 2008.
[4] T.J.R.Stidsen, K.A.Andersen. A hybrid approach for biobjective optimization. Discrete Optimization, 28, 89-114, 2018.
Orientador
Luís Paquete
paquete@dei.uc.pt 📩