Titulo Estágio
Implicit enumeration for representation systems in multiobjective optimization
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
DEI-FCTUC / ECOS
Enquadramento
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. The goal is to compute the Pareto-optimal set or a good approximation of it.
Usually, implicit enumeration algorithms for multiobjective optimization problems, such as branch-and-bound and dynamic programming fail to provide the complete Pareto-optimal set in a reasonable amount of time. Still, such approaches can be modified in a way that a (approximate) representative subset of the Pareto-optimal set is achieved in much less amount of time.
Objetivo
The goal of this project is to develop implicit enumeration algorithms for multiobjective combinatorial optimization problems that are able to return a representative subset of the Pareto-optimal set, or an approximation of it, according to some notion of representation.
The MSc student will investigate the application of branch-and-bound and dynamic programming approaches for the biobjective knapsack problem to find representative subsets. The uniformity indicator will be used as main notion of representation, but other indicators may also be considered. The main focus is on finding a representation with a given cardinality that contains only Pareto-optimal solutions, but relaxations can also be considered, such as approximations of bounded cardinality to the optimal representation. Finally, the MSc student will perform an in-depth experimental study of the approaches developed within this project, comparing the run-times and quality of the approximation achieved.
Plano de Trabalhos - Semestre 1
1. Literature review about concepts of multiobjective optimization, biobjective knapsack and representation of the Pareto optimal set.
2. Implementation of a branch-and-bound for the biobjective knapsack.
3. Experimental analysis.
4. Writing of the intermediate report.
Plano de Trabalhos - Semestre 2
1. Design and analysis of algorithmic strategies to find representative subsets.
2. Implementation of the above strategies in the branch-and-bound for the biobjective knapscak problem.
3. Experimental analysis.
4. Writing of the thesis.
Condições
The MSc student will have access to the computing environment at ECOS. This project has a grant associated.
Orientador
Luís Paquete e José Rui Figueira (IST-UL)
paquete@dei.uc.pt 📩