Genetic local search the graph partitioning problem under cardinality constraints

Yu. A. Kochetov   ; A. V. Plyasunov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 52 (2012) no. 1, pp. 164-176

Résumé

For the graph partitioning problem under cardinality constraints, a genetic local search method is developed. At each iteration of the method, there is a set of local optima of the problem. This set is used to search for new local optima with a smaller error. The local search problem with certain polynomially searchable neighborhoods is proved to be tight PLS-complete. It is shown that, in the worst case, number of local improvements can be exponentially large for any pivoting rule. Numerical experiments are performed in the special case of edge weights equal to unity, when local search is a polynomial-time procedure. The results of the experiments indicate that the method is highly efficient and can be applied to large-scale problems.

Bibliographie

[1] Ausiello G., Crescenzi P., Gambosi G. et al., Complexity and approximation: combinatorial optimization problems and their approximability properties, Springer, Berlin, 1999 | MR | Zbl

[2] Goldschmit O., Hochbaum D.S., “Polynomial algorithm for the $k$-cut problem”, Proc. 29'th Ann. IEEE Symp. Foundations of Computer Sci., IEEE Comput. Soc., 1988, 444–451

[3] Vazirani V.V., Approximation algorithms, Springer, Berlin, 2001 | MR

[4] Saran H., Yazirani V.V., “Finding $k$-cuts within twice the optimal”, SIAM J. Comput., 24 (1995), 101–108 | DOI | MR | Zbl

[5] Guttmann-Beck N., Hassin R., “Approximation algorithms for minimum $k$-cut”, Algorithmica, 27:2 (2000), 198–207 | DOI | MR | Zbl

[6] Kochetov Yu.A., “Vychislitelnye vozmozhnosti lokalnogo poiska v kombinatornoi optimizatsii”, Zh. vychisl. matem. i matem. fiz., 48:5 (2008), 788–807 | MR | Zbl

[7] Kochetov Yu.A., Paschenko M.G., Plyasunov A.V., “O slozhnosti lokalnogo poiska v zadache o $p$-mediane”, Diskretnyi analiz i issled. operatsii. Ser. 2, 12:2 (2005), 44–71 | MR | Zbl

[8] Alekseeva E., Kochetov Yu., Plyasunov A., “Complexity of local search for the $p$-median problem”, European J. Operat. Res., 191 (2008), 736–752 | DOI | MR | Zbl

[9] Walshaw C., Graph partitioning archive http://staffweb.cms.gre.ac.uk/~c.walshaw/partition

[10] Nurminskii E.A., “Dekompozitsiya i parallelizatsiya vychislitelnykh protsessov na osnove feierovskikh protsessov s malym vozmuscheniem”, Tp. XIV Baikalskoi mezhdunar. shkoly-seminara “Metody optimizatsii i ikh prilozheniya”, v. 1, ISEM SO RAN, Irkutsk, 2008, 128–137

[11] Chopra S., Rao M.R., “The partition problem”, Math. Program., 59 (1993), 87–115 | DOI | MR | Zbl

[12] Rendl F., Wolkowicz H., “A projection technique for partitioning the nodes of a graph”, Ann. Operat. Res., 58 (2005), 155–179 | DOI | MR

[13] Bertold T., “Automatic detection of orbitopal symmetries”, Abstracts of OR-2008 Conf., 2008, 198, Augsburg

[14] Peinhardt M., “Breaking model symmetry for graph partitioning”, Abstracts of OR-2008 Conf., 2008, 198, Augsburg

[15] Dreo J., Petrowski A., Siarry P., Taillard E., Metaheuristics for hard optimization, Springer, Berlin, 2006 | MR | Zbl

[16] Kernighan B.W., Lin S., “An effective heuristic procedure for partitioning graphs”, Bell System Techn. J., 49 (1970), 291–307 | Zbl

[17] Fiduccia C.M., Mattheyses R.M., “A linear-time heuristic for improving network partitions”, Proc. XIX Design Automation Conf., 1982, 175–181, IEEE Comput. Soc. Press, Los Alamitos. CA | DOI

[18] Laszewski G., “Intelligent structural operators for the $k$-way graph partitioning problem”, Proc. IV Internat. Conf. Genetic Algorithms, 1991, 45–52

[19] Moraglio A., Kim Y.-H., Yoon Y., Moon B.-R., “Geometric crossovers for multiway graph partitioning”, Evolutionary Comput., 15 (2007), 445–474 | DOI

[20] Glover F., Laguna M., Tabu search, Kluwer Acad. Publ., Boston, 1997 | MR

[21] Yannakakis M., “Computational complexity”, Local Search in Combinatorial Optimizat., 1997, 19–55, Wiley, Chichesfer | MR | Zbl

[22] Kochetov Yu., “Facility location: Discrete models and local search methods”, Combinatorial Optimizat. Meth. and Applic., 2011, 97–134, IOS Press, Amsterdam

[23] Hooker J.N., Integrated methods for optimization, Springer, New York, 2007 | MR

[24] Posypkin M.A., Sigal I.X., “Primenenie parallelnykh evristicheskikh algoritmov dlya uskoreniya parallelnogo metoda vetvei i granits”, Zh. vychisl. matem. i matem. fiz., 47:9 (2007), 1524–1537 | MR

[25] Garanzha V.A., Golikov A.I., Evtushenko Yu.G., Nguen M.X., “Parallelnaya realizatsiya metoda Nyutona dlya resheniya bolshikh zadach lineinogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 49:8 (2009), 1369–1384 | MR | Zbl