Titulo Estágio
Application of Machine Learning to Multi-objective Optimization Algorithms
Áreas de especialidade
Sistemas Inteligentes
Local do Estágio
CISUC-DEI
Enquadramento
Optimization algorithms are fundamental to numerous fields, including
operations research, computer science, and engineering. Traditional
optimization techniques, while powerful, often struggle with
high-dimensional, non-linear, and dynamic problems. Implicit enumeration
algorithms are critical for solving combinatorial optimization problems,
providing systematic approaches to explore feasible solutions. However,
the efficiency of these algorithms often depends on particular
algorithmic decisions, such as the node to expand or variable ordering
in branch-and-bound algorithms, which can significantly impact their
performance. Machine learning offers the potential to optimize these
decisions, enhancing the efficiency of implicit enumeration algorithms
[1].
Objetivo
This works aims to apply ML techniques for improving implicit
enumeration algorithms for combinatorial optimization problems by
letting these techniques learn the best algorithmic decisions. In
particular, the goal is to study the application of these techniques in
the context of dynamic programming algorithms, based on the
Nemhauser-Ullman principle, for multi-objective knapsack problems [2], considering input data generated from different distributions and with different degrees of constrainedness.
The performance of these algorithms is highly dependent of the ordering
of the variables. A primary goal is to understand if it possible to
learn better strategies for ordering the variables, either a priori or
in a dynamic manner.
Plano de Trabalhos - Semestre 1
- State of the art analysis
- Identification of target optimization algorithms
- Identification of suitable ML strategies
- Initial experimental setup
Plano de Trabalhos - Semestre 2
- Implementation of the identified ML strategies
- Experimental analysis
- Analysis and report of the results
Condições
Orientadores:
Luís Paquete
Marco Simões
Observações
[1] Yoshua Bengio, Andrea Lodi, Antoine Prouvost: Machine learning for
combinatorial optimization: A methodological tour d'horizon. Eur. J.
Oper. Res. 290(2): 405-421 (2021)
[2] José Rui Figueira, Luís Paquete, Marco Simões, Daniel Vanderpooten:
Algorithmic improvements on dynamic programming for the bi-objective {0,
1} knapsack problem. Comput. Optim. Appl. 56(1): 97-111(2013)
Datasets are generated by the student using distributions with different degrees of constrainedness.
Orientador
Marco Simões
msimoes@dei.uc.pt 📩