Titulo Estágio
An hypervolume dichotomic scheme for multiple objectives
Á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.
The hypervolume scalarization has been proposed in [1] and it consists of a particular product of the objective functions. It is possible to use this scalarization to generate all optimal solutions of a multiobjective optimization problem. Recently, an hypervolume dichotomic scheme has been proposed to solve biobjective optimization problems using hypervolume scalarizations. This approach iteratively bisects the objective space into two disjoint regions, each of which is bounded by a reference point and corresponds to a scalarized subproblem to be solved. No implementation of this approach is publicly available.
Objetivo
The goal of this MSc project is to implement the hypervolume dichotomic scheme that was recently proposed, extend it to any number of objective functions and make it publicly available (in git-hub). The implementation should allow the hypervolume scalarized problems to be solved by an Integer Linear Programming solver, such as CPLEX and/or SCIP. Finally, the implementation should be compared against known scalarized approaches such as epsilon-contraint. This project is related to the MSc project "Hypervolume scalarizations for multiobjective graph optimization problems"
Plano de Trabalhos - Semestre 1
- Literature review on multiobjective optimization
- Implementation of the hypervolume dichotomic scheme for two objectives
- Connection with ILP solvers
- Writing of the intermediate report
Plano de Trabalhos - Semestre 2
- Extension of the framework to multiple objectives
- 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 📩