×

The life span method – a new variant of local search. (English) Zbl 0912.90239

Summary: We present a variant of local search, namely the life span method (LSM), for generic combinatorial optimization problems. The LSM can be seen as a variation of tabu search introduced by Glover. We outline applications of the LSM to several combinatorial optimization problems such as the maximum stable set problem, the traveling salesman problem, the quadratic assignment problem, the graph partitioning problem, the graph coloring problem, and the job-shop scheduling problem.

MSC:

90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research
90C10 Integer programming

Software:

Genocop; Tabu search
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E.H.L. Aarts and J.H.M Korst, Simulated Annealing and Boltzmann Machines. John Wiley & Sons, Chichester, U.K., 1989. · Zbl 0674.90059
[2] J. Adams, E. Balas and D. Zawack, The shifting bottleneck procedure for job shop scheduling problem. Management Sci.,34 (1988), 391–401. · Zbl 0637.90051 · doi:10.1287/mnsc.34.3.391
[3] R. Battiti and G. Tecchiolli, The reactive tabu search. ORSA J. Comput.,6(2) (1994), 126–140. · Zbl 0807.90094 · doi:10.1287/ijoc.6.2.126
[4] B. Bollobas, Random Graphs. Academic Press, 1985.
[5] J. Chakrapani and J. Skorin-Kapov, Massively parallel tabu search for the quadratic assignment problem. Ann. Opns. Res.,41 (1993), 327–341. · Zbl 0775.90288 · doi:10.1007/BF02022999
[6] M. Chams, A. Hertz and D. de Werra, Some experiments with simulated annealing for coloring graphs. Eur. J. Opns. Res.,32 (1987), 260–266. · Zbl 0626.90067 · doi:10.1016/S0377-2217(87)80148-0
[7] N.E. Collins, R.W. Eglese and B.L. Golden, Simulated annealing: An annotated bibliography. Amer. J. Math. Management Sci.,8 (1988), 205–307. · Zbl 0669.65047 · doi:10.1080/01966324.1988.10737241
[8] M. Dell’Amico and M. Trubian, Applying tabu search to the job-shop scheduling problem. Ann. Opns. Res.,41 (1993), 231–252. · Zbl 0771.90056 · doi:10.1007/BF02023076
[9] T.A. Feo, M.G.C. Resende and S.H. Smith, A greedy randomized adaptive search procedure for maximum independent set. Opns. Res.,42(5) (1994), 860–878. · Zbl 0815.90121 · doi:10.1287/opre.42.5.860
[10] M.A. Fleischer and S.H. Jacobson, Cybernetic Optimization by Simulated Annealing: An Implementation of Parallel Processing Using Probabilistic Feedback Contorol. Kluwer Academic Publishers, 1996. · Zbl 0877.90063
[11] 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 · doi:10.1007/BF02243141
[12] C. Friden, A. Hertz and D. de Werra, An exact algorithm based on tabu search for finding a maximum independent set in graph. Computers Opns. Res.,17(5) (1990), 375–382. · Zbl 0692.68044 · doi:10.1016/0305-0548(90)90016-Z
[13] K. Fujisawa, M. Kubo and S. Morito, Experimental analyses of the tabu search for the graph partitioning problem (in Japanese). The Institute of Electrical Engineers of Japan,114(C)-4 (1994), 430–437.
[14] K. Fujisawa, S. Morito and M. Kubo, Experimental analyses of the life span method for the maximum stable set problem. The Institute of Statistical Mathematics Cooperative Research Report,75 (1995), 135–165.
[15] K. Fujisawa, S. Morito and M. Kubo, Experimental analyses of the life span method for the quadratic assignment porblem. The Institute of Statistical Mathematics Cooperative Research Report,75 (1995), 166–188.
[16] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, 1979. · Zbl 0411.68039
[17] M. Gendreau, P. Soriano and L. Salvail, Solving the maximum clique problem using a tabu search approach. Ann. Opns. Res.,41 (1993), 385–403. · Zbl 0775.90297 · doi:10.1007/BF02023002
[18] F. Glover, Tabu search I. ORSA J. Comput.,1 (1989), 190–206. · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[19] F. Glover, Tabu search II. ORSA J. Comput.,2 (1990), 4–32. · Zbl 0771.90084 · doi:10.1287/ijoc.2.1.4
[20] F. Glover, Tabu search: fundamentals and usage. Working paper, University of Colorado, Boulder, 1995.
[21] F. Glover and M. Laguna, Tabu search. A chapter in Modern Heuristic Techniques for Combinatorial Problems (ed. C. Reeves), Blackwell Scientific Publishing, 1993, 70–141.
[22] F. Glover, E. Taillard and D. de Werra, A users guide to tabu search. Special issues of the Ann. Opns. Res. (ed. J.C. Baltzer),41 (1993), 3–28. · Zbl 0772.90063
[23] D.E. Goldberg, Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, Reading, MA, 1989. · Zbl 0721.68056
[24] A. Hertz and D. de Werra, Using tabu search techniques for graph coloring. Computing,39 (1987), 345–351. · Zbl 0626.68051 · doi:10.1007/BF02239976
[25] J.H. Holland, Adaptation in Natural and Artificial Systems. Michigan Press, 1975. · Zbl 0317.68006
[26] J.J. Hopfield and D.W. Tank, Computing with neural circuits: A model. Science,233 (1986), 625–633. · Zbl 1356.92005 · doi:10.1126/science.3755256
[27] D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: An experimental evaluation, part I, graph partitioning. Opns. Res.,37 (1989), 865–892. · Zbl 0698.90065 · doi:10.1287/opre.37.6.865
[28] D.S. Johnson, C.R. Aragon, L.A. McGeoch and C. Schevon, Optimization by simulated annealing: An experimental evaluation, part II, graph coloring and number partitioning. Opns. Res.,39 (1991), 378–406. · Zbl 0739.90055 · doi:10.1287/opre.39.3.378
[29] B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal,49 (1970), 291–307. · Zbl 0333.05001 · doi:10.1002/j.1538-7305.1970.tb01770.x
[30] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing. Science,220 (1983), 671–680. · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[31] E.L. Lawler, Combinatorial Optimization: Network and Matroids. Rinehart and Winston, New York, 1976. · Zbl 0413.90040
[32] S. Lin, Computer solutions of the traveling salesman problem. Bell System Technical Journal,44 (1965), 2245–2269. · Zbl 0136.14705 · doi:10.1002/j.1538-7305.1965.tb04146.x
[33] S. Lin and W. Kernighan, An effective heuristic algorithm for the traveling salesman problem. Opns. Res.,21 (1973), 498–516. · Zbl 0256.90038 · doi:10.1287/opre.21.2.498
[34] M. Malek, M. Guruswamy and M. Pandya, Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem. Ann. Opns. Res.,21 (1989), 59–84. · Zbl 0705.90069 · doi:10.1007/BF02022093
[35] Z. Michalewicz, Genetic Algorithm + Data Structure = Evolution Programs (2nd edition). Springer Verlag, 1994. · Zbl 0818.68017
[36] Z. Michalewicz, Evolutionary Computation and Heuristics. Kluwer Academic Publishers, 1996. · Zbl 0877.90089
[37] J.F. Muth and G.L. Thompson, Industrial Scheduling. Prentice-Hall, 1963.
[38] E.M. Palmer, Graphical Evolution. Wiley, 1985.
[39] C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982. · Zbl 0503.90060
[40] P.M. Pardalos and J. Xue, The maximum clique problem. J. Global Optim.,4 (1994), 301–328. · Zbl 0797.90108 · doi:10.1007/BF01098364
[41] J. Skorin-Kapov, Tabu search applied to the quadratic assignment problem. ORSA J. Comput.,2 (1990), 33–45. · Zbl 0752.90054 · doi:10.1287/ijoc.2.1.33
[42] E. Taillard, Parallel taboo search for the job shop scheduling problem. Technical report, Swiss Federal Institute of Technology of Lausanne, 1989. · Zbl 0807.90066
[43] H. Takayama, M. Kubo and S. Morito, Scheduling and tabu search. Comm. Opns. Res. Soc. Japan,40(1) (1995), 47–54.
[44] P.J.M. van Laarhoven, E.H.L. Aarts and J.K. Lenstra, Job shop scheduling by simulated annealing. Opns. Res.,40 (1992), 113–125. · Zbl 0751.90039 · doi:10.1287/opre.40.1.113
[45] P.J.M. van Laarhoven and E.H.L. Aarts, Simulated Annealing: Theory and Practice. Kluwer Academic Publishers, Dordrecht, The Netherlands, 1987. · Zbl 0643.65028
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.