Tabu search for graph partitioning. (English) Zbl 0851.90131

Summary: We develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle rounting, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.


90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research
90B06 Transportation, logistics and supply chain management


Tabu search
Full Text: DOI


[1] J.W. Barnes and M. Laguna, Solving the multiple-machine weighted flow time problem using tabu search, IIE Trans. 25(1993)121–127.
[2] J. Chakrapani and J. Skorin-Kapov, Massively parallel tabu search for the quadratic assignment problem, Ann. Oper. Res. 41(1993)327–341. · Zbl 0775.90288
[3] W. Dai and E. Kuh, Simultaneous floor planning and global routing for hierarchical building block layout, IEEE Trans. Comp. Aided Design ICs Syst. (1987).
[4] D. de Werra and A. Hertz, Tabu search techniques: A tutorial and an application to neural networks, OR Spektrum 11(1989)131–141. · Zbl 0672.90089
[5] T.A. Feo and M. Khellaf, A class of bounded approximation algorithms for graph partitioning, Networks 20(1990)181–195. · Zbl 0696.90074
[6] C.M. Fiduccia and R.M. Mettheyses, A linear time heuristic for improving network partitions,Proc. 19th Design Automation Conf., ACM/IEEE (1982) pp. 175–181.
[7] C. Friden, A. Hertz and D. de Werra, Stabulus: A technique for finding stable sets in large graphs with tabu search, Computing 42(1989)35–44. · Zbl 0685.68056
[8] M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph probems, Theor. Comput. Sci. 1(1976)237–267. · Zbl 0338.05120
[9] M. Gendreau, A. Hertz and G. Laporte, A tabu search heuristic for the vehicle routing problem, Manag. Sci., to appear. · Zbl 0822.90053
[10] F. Glover and H.J. Greenberg, New approaches for heuristic search: A bilateral linkage with artificial intelligence, Euro. J. Oper. Res. 39(1989)119–130. · Zbl 0658.90079
[11] F. Glover, Tabu search – Part II, ORSA J. Comp. 2 (1990).
[12] F. Glover and M. Laguna, Tabu search, in:Modern Heuristic Techniques for Combinatorial Problems, ed. C. Reeves (Blackwell, 1993). · Zbl 0774.90033
[13] F. Glover, E. Taillard and D. de Werra, A user’s guide to tabu search, Ann. Oper. Res. 41(1993)3–28. · Zbl 0772.90063
[14] F. Glover, C. McMillan and B. Novick, Interactive decision software and computer graphics for architectural and space planning, Ann. Oper. Res. 5(1985)557–573.
[15] A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 29(1987)345–351. · Zbl 0626.68051
[16] D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: An experimental evaluation. Part I: Graph partitioning, Oper. Res. 37 (1989). · Zbl 0698.90065
[17] B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J. 49(1970). · Zbl 0333.05001
[18] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing. Science 220(1983)671–680. · Zbl 1225.90162
[19] J.G. Klincewicz, Avoiding local optima in thep-hub location problem using tabu search and grasp, Ann. Oper. Res. 40(1992)121–132. · Zbl 0784.90044
[20] M. Laguna, J.W. Barnes and F. Glover, Tabu search methods for a single machine scheduling systems, J. Int. Manufact. 2(1991)63–74.
[21] M. Laguna and F. Glover, Integrating target analysis and tabu search for improved scheduling systems, Expert Syst. Appl. 6(1993)287–297.
[22] E. Nowicki and C. Smutnicki, A fast tabu search algorithm for the job shop problem, Technical Report, Technical University of Wroclaw, Poland (1993). · Zbl 0880.90079
[23] I.H. Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Ann. Oper. Res. 41(1993)421–451. · Zbl 0775.90153
[24] E. Rolland, Abstract heuristic search methods for graph partitioning, Ph.D. Dissertation, The Ohio State University, Colombus, OH (1991).
[25] D. Skorin-Kapov and J. Skorin-Kapov, On tabu search for the location of interacting hub facilities, Harriman School for Management and Policy, SUNY at Stony Brook (1992). · Zbl 0806.90075
[26] J. Skorin-Kapov, Tabu search applied to the quadratic assignment problem, ORSA J. Comp. 2 (1990). · Zbl 0752.90054
[27] E. Taillard, Robust tabu search for the quadratic assignment problem, Parallel Comp. 17(1991)443–455.
[28] S. Voss, An enhanced tabu search method for the quadratic assignment problem, Technical Report, Technische Hochschule Darmstadt (1993), to appear in Discr. Appl. Math.
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.