The Minimum Gap Graph Partitioning Problem (MGGPP) consists in partitioning a vertex-weighted undirected graph into a given number of connected subgraphs with the minimum difference between the largest and the smallest weight in each subgraph. We propose a two-level Tabu Search algorithm and an Adaptive Large Neighborhood Search algorithm to solve the MGGPP in reasonable time on instances with up to about 23 000 vertices. The quality of the heuristic solutions is assessed comparing them with the solutions of a polynomially solvable combinatorial relaxation.
Metaheuristics for the Minimum Gap Graph Partitioning Problem / M. Bruglieri, R. Cordone. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 132:(2021 Aug), pp. 105301.1-105301.18. [10.1016/j.cor.2021.105301]
Metaheuristics for the Minimum Gap Graph Partitioning Problem
R. Cordone
2021
Abstract
The Minimum Gap Graph Partitioning Problem (MGGPP) consists in partitioning a vertex-weighted undirected graph into a given number of connected subgraphs with the minimum difference between the largest and the smallest weight in each subgraph. We propose a two-level Tabu Search algorithm and an Adaptive Large Neighborhood Search algorithm to solve the MGGPP in reasonable time on instances with up to about 23 000 vertices. The quality of the heuristic solutions is assessed comparing them with the solutions of a polynomially solvable combinatorial relaxation.
| File | Dimensione | Formato | |
|---|---|---|---|
|
MGGP_COR.pdf
accesso aperto
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
744.17 kB
Formato
Adobe PDF
|
744.17 kB | Adobe PDF | Visualizza/Apri |
|
1-s2.0-S0305054821000939-main.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
2.68 MB
Formato
Adobe PDF
|
2.68 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
