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 23000 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;
2021-01-01

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 23000 vertices. The quality of the heuristic solutions is assessed comparing them with the solutions of a polynomially solvable combinatorial relaxation.
2021
Graph partitioning, Tabu Search, Adaptive Large Neighborhood Search
File in questo prodotto:
File Dimensione Formato  
Metaheuristics_for_the_Minimum_Gap_Graph_Partitioning_Problem.pdf

accesso aperto

Descrizione: Articolo principale
: Pre-Print (o Pre-Refereeing)
Dimensione 435.49 kB
Formato Adobe PDF
435.49 kB Adobe PDF Visualizza/Apri

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/11311/1194098
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 6
social impact