Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs

The Multilevel algorithm (ML) has been applied successfully as a metaheuristic for different combinatorial optimization problems: Graph Partitioning, Traveling Salesman, Graph Coloring, see refs. [6,7,18]. The main difficulty of ML are the convergence times needed to obtain solutions at a distance o...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Hernandez, G., Bravo, F., Montealegre, P., Nuñez, F., Salinas, L.
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2010
Materias:
Ciencias Informáticas
Graph Bisection Problem
Multilevel + Neural Network Heuristic
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/152730
http://39jaiio.sadio.org.ar/sites/default/files/39jaiio-hpc-07.pdf
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-152730
record_format dspace
spelling I19-R120-10915-1527302023-05-10T20:02:58Z http://sedici.unlp.edu.ar/handle/10915/152730 http://39jaiio.sadio.org.ar/sites/default/files/39jaiio-hpc-07.pdf issn:1851-9326 Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs Hernandez, G. Bravo, F. Montealegre, P. Nuñez, F. Salinas, L. 2010 2010 2023-05-10T16:51:11Z en Ciencias Informáticas Graph Bisection Problem Multilevel + Neural Network Heuristic The Multilevel algorithm (ML) has been applied successfully as a metaheuristic for different combinatorial optimization problems: Graph Partitioning, Traveling Salesman, Graph Coloring, see refs. [6,7,18]. The main difficulty of ML are the convergence times needed to obtain solutions at a distance of 7% - 5% to the best known solution in large scale problems. In order to reduce these convergence times we studied numerically a Parallel Multilevel heuristic with Neural Network partitioning and uncoarsening + refinement phases (PML+PNN) for the Graph Bisection Problem on geometrically connected graphs. Our main result establish that for graphs with n∊[4000,12000] vertices, the performance of the parallel ML+NN heuristic increases linearly as n increases with respect to the parallel ML heuristic. For n∊{10000,12000} the distance to the best solution found is 0.32,0.25 respectively that is obtained with a quadratic computing time. This suggests improving the performance of the PML+PNN heuristic by means of a hill climbing improvement heuristic. Sociedad Argentina de Informática e Investigación Operativa Objeto de conferencia Objeto de conferencia http://creativecommons.org/licenses/by-nc-sa/4.0/ Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) application/pdf 3249-3257
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Graph Bisection Problem
Multilevel + Neural Network Heuristic
spellingShingle Ciencias Informáticas
Graph Bisection Problem
Multilevel + Neural Network Heuristic
Hernandez, G.
Bravo, F.
Montealegre, P.
Nuñez, F.
Salinas, L.
Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs
topic_facet Ciencias Informáticas
Graph Bisection Problem
Multilevel + Neural Network Heuristic
description The Multilevel algorithm (ML) has been applied successfully as a metaheuristic for different combinatorial optimization problems: Graph Partitioning, Traveling Salesman, Graph Coloring, see refs. [6,7,18]. The main difficulty of ML are the convergence times needed to obtain solutions at a distance of 7% - 5% to the best known solution in large scale problems. In order to reduce these convergence times we studied numerically a Parallel Multilevel heuristic with Neural Network partitioning and uncoarsening + refinement phases (PML+PNN) for the Graph Bisection Problem on geometrically connected graphs. Our main result establish that for graphs with n∊[4000,12000] vertices, the performance of the parallel ML+NN heuristic increases linearly as n increases with respect to the parallel ML heuristic. For n∊{10000,12000} the distance to the best solution found is 0.32,0.25 respectively that is obtained with a quadratic computing time. This suggests improving the performance of the PML+PNN heuristic by means of a hill climbing improvement heuristic.
format Objeto de conferencia
Objeto de conferencia
author Hernandez, G.
Bravo, F.
Montealegre, P.
Nuñez, F.
Salinas, L.
author_facet Hernandez, G.
Bravo, F.
Montealegre, P.
Nuñez, F.
Salinas, L.
author_sort Hernandez, G.
title Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs
title_short Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs
title_full Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs
title_fullStr Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs
title_full_unstemmed Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs
title_sort multilevel + neural network heuristic for the graph bisection problem on geometrically connected graphs
publishDate 2010
url http://sedici.unlp.edu.ar/handle/10915/152730
http://39jaiio.sadio.org.ar/sites/default/files/39jaiio-hpc-07.pdf
work_keys_str_mv AT hernandezg multilevelneuralnetworkheuristicforthegraphbisectionproblemongeometricallyconnectedgraphs
AT bravof multilevelneuralnetworkheuristicforthegraphbisectionproblemongeometricallyconnectedgraphs
AT montealegrep multilevelneuralnetworkheuristicforthegraphbisectionproblemongeometricallyconnectedgraphs
AT nunezf multilevelneuralnetworkheuristicforthegraphbisectionproblemongeometricallyconnectedgraphs
AT salinasl multilevelneuralnetworkheuristicforthegraphbisectionproblemongeometricallyconnectedgraphs
_version_ 1765660142354825216

Ejemplares similares