Short-Term Scientific Mission

Exploring Path Relinking for the Multiobjective Quasi-Clique Problem

Main theme: Single- and Multiobjective Optimisation
Grantee: Daniela Santos, University of Coimbra, Coimbra, Portugal
Host: Kathrin Klamroth, University of Wuppertal, Wuppertal, Germany

Start date: 2024-09-12
End date: 2024-09-28
Awarded: 2024-07-03
Report approved: 2024-10-28

Description

Given a simple undirected graph G, a quasi-clique is a subgraph of G with density at least γ (0 < γ ≤ 1). The Multiobjective Quasi-Clique Problem (MOQC) aims to find a quasi-clique with maximum number of vertices and maximum density. This STSM aims to advance our understanding of MOQC and leverage its unique properties to propose an efficient heuristic based on Path Relinking, which generates candidates by exploring paths between elite solutions. Our prior work shows that a subset of MOQC’s efficient solutions can be identified in polynomial time and may serve as elite solutions in our Path Relinking approach.

Achievements

Since our earlier research showed that MOQC can be efficiently solved through the related Multiobjective Subgraph (MOS) problem – focused on maximizing edges while minimizing vertices – this STSM addressed the MOS problem to solve MOQC. Outcomes include the discovery that extreme supported quasi-cliques for MOS exhibit a nested property, leading to an efficient Path-Relinking-based heuristic with randomized vertex removal and degree-based moves. The extreme supported points for MOS were used to derive an upper bound to guide the efficiency of the heuristic. Preliminary results showed that the heuristic performed well in terms of solution quality compared to the results from exact methods.