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.
Adaptive Large Neighborhood Search; Graph partitioning; Tabu Search
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
ago-2021
Article (author)
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/849669
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 6
social impact