Titulo Estágio
Subset selection algorithms in multiobjective optimization
Área Tecnológica
Sistemas Evol. e Comp.
Local do Estágio
DEI
Enquadramento
Typically, multiobjective optimization problems are solved according to the Pareto principle of optimality: A solution is called Pareto-optimal if no other feasible solution exists which is better in all objectives. Each of these Pareto-optimal solutions corresponds to a different compromise among the objective functions and each of them is potentially relevant for a decision maker. Therefore, the goal of multiobjective optimization is to compute the Pareto-optimal set or, since this set is usually very large in practice, a good approximation of it. The quality of the approximation (or representation) of the Pareto-optimal set can be determined in several manners: cardinality, accuracy, representation error or cluster density.
Objetivo
The goal of this project is to develop efficient algorithms that select i) a subset of a point set that is close as possible from another point set; ii) a representative subset of a point set. In this work, it is assumed that the point sets contain only nondominated elements and the cardinality of the subset to be chosen is fixed a priori.
The first task is related to subset selection procedures within heuristic approaches to multiobjective optimization. The goal is to choose a subset of solutions at each iteration that is as close as possible from a reference set, for instance, the Pareto-optimal set. Some work is already done for the case of the epsilon-indicator as a measure of closeness between nondominated point sets (see Section 5 of article A.Ponte, L Paquete, J.R. Figueira, On beam search for multicriteria combinatorial optimization problems. Proc. of the 9th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (available at http://eden.dei.uc.pt/~paquete/papers/cpaior.pdf). The goal is to implement the approach described in the article and extend it to more than two dimensions.
The second task is a topic of a bilateral research project RepSys - Representation Systems with Quality Guarantees for Multi-Objective Optimization Problems, with Kaiserslautern University of Technology and University of Wuppertal, in Germany. The goal is to develop algorithms that select the representative subset of the Pareto-optimal set that maximizes a given measure, such as epsilon-indicator, hypervolume, uniformity and coverage, or combination thereof. Some part of this work is already described for uniformity and coverage measures (L.Paquete, CM Fonseca, K.Klamroth, M.Stiglmayr, Concise representation of nondominated sets in discrete multicriteria optimization, submitted to the 21st International Symposium on Mathematical Programming, 2012).
A final outcome of this work is to make the implementations available to the community (e.g., see hypervolume implementation in http://iridia.ulb.ac.be/~manuel/hypervolume).
Plano de Trabalhos - Semestre 1
During the first semester, it is expected that the student makes a literature review, focusing on the following topics:
- principles of multiobjective optimization;
- properties of non-dominated point sets with respect to hypervolume and epsilon-indicator;
- principles of dynamic programming;
- optimization problems in facility/location, in particular, p-center and p-dispersion;
- other algorithmic contributions for subset selection.
At the end of the first semester, the student should be able to formalize the two subset selection problems.
The following plan indicates the main topics covered in the first semester:
- Literature review (3 months)
- Subset selection problem formulations for tasks i) and ii) (1 months)
- Writing of the thesis (1 month)
Plano de Trabalhos - Semestre 2
In the second semester, the student should implement the algorithms for the variants of the subset selection problem:
- Implementation and testing of the algorithms for task i) (2 months)
- Implementation and testing of the algorithms for task ii) (2 months)
- Writing of the thesis (1 month)
Condições
Although there is currently no funding available for this project, the student will have access to the rooms of ECOS research group and to the computer cluster. The student will have the opportunity of interacting with an active group of Portuguese and German researchers and learn about a new interesting field in optimization and algorithms.
Orientador
Luis Paquete
paquete@dei.uc.pt 📩