Short-Term Scientific Mission

Grouping Strategies on Two-Phase Methods for Biobjective Combinatorial Optimisation

Main theme: Single- and Multiobjective Optimisation
Grantee: Felipe Mota, University of Coimbra, Coimbra, Portugal
Host: Daniel Vanderpooten, Université Paris-Dauphine-PSL, Paris, France

Start date: 2025-03-10
End date: 2025-03-21
Awarded: 2025-01-29
Report approved: 2025-04-25

Description

This STSM aims to improve two-phase methods for multiobjective combinatorial optimisation problems. A widely spread strategy in this field is to divide the search for nondominated points into two steps. The first step will be responsible for finding the supported points, which can be obtained with a sequence of weighted-sum scalarisations of the problem. To find the non-supported points in the second phase, a common choice is using ranking algorithms. These algorithms can waste computational effort by visiting the same solution multiple times. We try to avoid such behaviour by tackling multiple search areas together.

Achievements

The STSM promoted advances in two-phase methods for multi-objective combinatorial optimisation problems. In particular, several strategies that group search zones delimited by supported points found in the first phase were proposed and tested empirically. Moreover, the concept of coverage of search zones was extended, allowing to skip more search zones without compromising the optimality. Finally, the mission resulted in a public repository for the biobjective spanning tree problem and a paper submission to a journal.

Publication

@article{Mota2025Grouping,
	author = {Mota, Felipe O. and Paquete, Lu{\' i}s and Vanderpooten, Daniel},
	doi = {10.48550/arXiv.2504.06869},
	year = {2025},
	title = {Grouping strategies on two-phase methods for bi-objective combinatorial optimization},
	url = {https://arxiv.org/abs/2504.06869},
	howpublished = {https://arxiv.org/abs/2504.06869},
}