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...
Guardado en:
Autores principales: | , , , , |
---|---|
Formato: | Objeto de conferencia |
Lenguaje: | Inglés |
Publicado: |
2010
|
Materias: | |
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: |
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 |