Objeto de conferencia
Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs
Autor
Hernandez, G.
Bravo, F.
Montealegre, P.
Nuñez, F.
Salinas, L.
Institución
Resumen
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