Titulo Estágio
Hypervolume scalarizations for multiobjective graph optimization problems
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
ALGO Lab, Adaptive Computation Group, CISUC, DEI, FCTUC
Enquadramento
Optimization problems with multiple objectives arise in many real-life applications. However, in general, there is no single solution that is optimal for all objectives. For instance, there is no single path from Coimbra to Lisbon that optimizes cost and time since the fastest path may not be the cheapest; just consider highways. Under some assumptions on the decision maker preferences, is possible to solve a multiobjective optimization problem by scalarizing it, that is, to formalize a related single-objective problem such that an optimal solution to this problem is also optimal for the multiobjective problem. Some common scalarizations are weighted sum, epsilon-constraint method and achievement scalarizing functions.
The hypervolume scalarization has been proposed recently in [1] and it consists of a particular product of the objective functions. This scalarization presents some interesting properties, but it leads to particular quadratic formulations for which very little is known; see [1] for the case of a particular variant of the biobjective knapsack problem.
Objetivo
The goal of this MSc project is to formalize hypervolume scalarized problems of known multiobjective graph problems, such as the minimum spanning tree problem and the shortest path problem, as well as to develop exact and/or approximation algorithms for these problems. This project extends previous work for biobjective knapsack problems in [1], for which a linearization of the quadratic scalarized formulation was achieved and an approximation algorithm with provable quality guarantee was devised. This project is related to the MSc project "An hypervolume dichotomic scheme for multiple objectives".
Plano de Trabalhos - Semestre 1
- Literature review on multiobjective problems and graph problems (shortest path and minimum spanning tree)
- Hypervolume scalarization for graph problems with a quadratic formulation and linearizations
- Experimental analysis with an ILP solver
- Writing of the intermediate report
Plano de Trabalhos - Semestre 2
- Design of an exact or approximation algorithm for the hypervolume scalarization
- Experimental analysis
- Writing of the final report
Condições
This MSc project arises within an existent collaboration with Dr. Michael Stiglmayr and Dr. Britta Schulze, from the Optimization Group, University of Wuppertal, Germany. It is targeted for students that would like to deepen their knowledge on algorithms and optimization. A research grant is available for at least 3 months.
Observações
[1] On the rectangular knapsack problem - approximation of a specific quadratic knapsack problem. B. Schulze, M. Stiglmayr, L. Paquete, C.M. Fonseca, D. Willems, S. Ruzika. Mathematical Methods of Operations Research, 2020.
Orientador
Luís Paquete
paquete@dei.uc.pt 📩