A deterministic annealing algorithm for approximating a solution of the min-bisection problem.

*(English)*Zbl 1335.90104Summary: The min-bisection problem is an NP-hard combinatorial optimization problem. In this paper an equivalent linearly constrained continuous optimization problem is formulated and an algorithm is proposed for approximating its solution. The algorithm is derived from the introduction of a logarithmic-cosine barrier function, where the barrier parameter behaves as temperature in an annealing procedure and decreases from a sufficiently large positive number to zero. The algorithm searches for a better solution in a feasible descent direction, which has a desired property that lower and upper bounds are always satisfied automatically if the step length is a number between zero and one. We prove that the algorithm converges to at least a local minimum point of the problem if a local minimum point of the barrier problem is generated for a sequence of descending values of the barrier parameter with a limit of zero. Numerical results show that the algorithm is much more efficient than two of the best existing heuristic methods for the min-bisection problem, Kernighan-Lin method with multiple starting points (MSKL) and multilevel graph partitioning scheme (MLGP).

##### MSC:

90C35 | Programming involving graphs or networks |

68W25 | Approximation algorithms |

90C59 | Approximation methods and heuristics in mathematical programming |

Full Text:
DOI

##### References:

[1] | Aiyer, S.; Niranjan, M.; Fallside, F., A theoretical investigation into the performance of the Hopfield model, IEEE transactions on neural networks, 1, 204-215, (1990) |

[2] | Amin, C. O. (2005). A spectral heuristic for bisecting random graphs. Available online: www.interscience.wiley.com · Zbl 1297.05213 |

[3] | Berg, J. van den (1996). Neural relaxation dynamics. Ph.D. thesis. The Netherlands: Erasmus University of Roterdam · Zbl 0875.68738 |

[4] | Bout, D.van den; Miller, T., Graph partitioning using annealed networks, IEEE transactions on neural networks, 1, 192-203, (1990) |

[5] | Bui, T.N.; Moon, B.R., Genetic algorithm and graph partitioning, IEEE transactions on computers, 45, 7, 841-855, (1996) · Zbl 1049.68605 |

[6] | Cichocki, A.; Unbehaunen, R., Neural networks for optimization and signal processing, (1993), John Wiley & Sons New York |

[7] | Dang, C.; Xu, L., A Lagrange multiplier and Hopfield-type barrier function method for the traveling salesman problem, Neural computation, 14, 303-324, (2001) · Zbl 0995.90079 |

[8] | Durbin, R.; Willshaw, D., An analogue approach to the traveling salesman problem using an elastic network method, Nature, 326, 689-691, (1987) |

[9] | Feig, U.; Kuauthgamer, R., A polylogarithmic approximation of the minimum bisection, SIAM review, 48, 1, 99-130, (2006) |

[10] | Gee, A.; Aiyer, S.; Prager, R., An analytical framework for optimizing neural networks, Neural networks, 6, 79-97, (1993) |

[11] | Gee, A.; Prager, R., Polyhedral combinatorics & neural networks, Neural computation, 6, 161-180, (1994) |

[12] | Gil, C.; Ortega, J.; Diaz, A.F.; Montoya, M.D.G., Annealing based heuristics and genetic algorithms for circuit partitioning in parallel test generation, Future generation computer systems, 14, 439-451, (1998) |

[13] | Hendrickson, B., & Leland, R. (1993). A multilevel algorithm for partitioning graphs. Tech. report SAND93-1301. Albuquerque, NM: Sandia National Laboratories · Zbl 0816.68093 |

[14] | Hopfield, J.; Tank, D., Neural computation of decisions in optimization problems, Biological cybernetics, 52, 141-152, (1985) · Zbl 0572.68041 |

[15] | Horio, Y.; Ikeguchi, T.; Aihara, K., A mixed analog/digital chaotic neuro-computer system for quadratic assignment problems, Neural networks, 18, 505-513, (2005) |

[16] | Ishii, T.; Iwata, K.; Nagamochi, H., Bisecting a 4-connected graph with three resource sets, Discrete applied mathematics, 155, 1441-1450, (2007) · Zbl 1142.05068 |

[17] | Jerrum, M.; Sorkin, G.B., The metropolis algorithm for graph bisection, Discrete applied mathematics, 82, 155-175, (1998) · Zbl 0932.60079 |

[18] | Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM journal on scientific computing, 20, 1, 359-392, (1998) · Zbl 0915.68129 |

[19] | Kernighan, B.W.; Lin, S., An efficient heuristic procedure for partitioning graphs, The Bell system technical journal, 49, 291-307, (1970) · Zbl 0333.05001 |

[20] | Loiola, E.M.; Abreu, N.M.M.de; Boaventura-Netto, P.O.; Hahn, P.; Querido, T., A survey for the quadratic assignment problem, European journal of operational research, 176, 657-690, (2007) · Zbl 1103.90058 |

[21] | Minoux, M., Mathematical programming: theory and algorithms, (1986), John Wiley & Sons New York · Zbl 0602.90090 |

[22] | Murty, K.G.; Kabadi, S.N., Some NP-complete problems in quadratic and nonlinear programming, Mathematical programming, 39, 117-129, (1987) · Zbl 0637.90078 |

[23] | Peterson, C.; Soderberg, B., A new method for mapping optimization problems onto neural networks, International journal of neural systems, 1, 3-22, (1989) |

[24] | Rangarajan, A.; Gold, S.; Mjolsness, E., A novel optimizing network architecture with applications, Neural computation, 8, 1041-1060, (1996) |

[25] | Saab, Y.; Rao, V., On the graph bisection problem, IEEE transactions on circuits and systems-1: fundamental theory and applications, 39, 9, 760-762, (1992) · Zbl 0768.05056 |

[26] | Simic, P., Statistical mechanics as the underlying theory of elastic and neural optimizations, Networks, 1, 89-103, (1990) · Zbl 0850.82038 |

[27] | Soper, A.J.; Walshaw, C.; Cross, M., A combined evolutionary search and multilevel optimization approach to graph-partitioning, Journal of global optimization, 29, 225-241, (2004) · Zbl 1084.90049 |

[28] | Urahama, K., Gradient projection network: analog solver for linearly constrained nonlinear programming, Neural computation, 6, 1061-1073, (1996) |

[29] | Wacholder, E.; Han, J.; Mann, R., A neural network algorithm for the multiple traveling salesman problem, Biological cybernetics, 61, 11-19, (1989) · Zbl 0679.68108 |

[30] | Waugh, F.; Westervelt, R., Analog neural networks with local competition: I. dynamics and stability, Physical review E, 47, 4524-4536, (1993) |

[31] | Wolfe, W.; Parry, M.; MacMillan, J., Hopfield-style neural networks and the TSP, IEEE international conference on neural networks, 7, 4577-4582, (1994) |

[32] | Wu, J., Annealing by two sets of interactive dynamics, IEEE transactions on systems, man, and cybernetics-part B: cybernetics, 34, 3, 1519-1525, (2004) |

[33] | Xu, L. (1994). Combinatorial optimization neural nets based on a hybrid of Lagrange and transformation approaches. In Proceedings of the world congress on neural networks (pp. 399-404) |

[34] | Yuille, A.; Kosowsky, J., Statistical physics algorithms that converge, Neural computation, 6, 341-356, (1994) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.