Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A nonmonotone GRASP

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

Abstract

A greedy randomized adaptive search procedure (GRASP) is an iterative multistart metaheuristic for difficult combinatorial optimization problems. Each GRASP iteration consists of two phases: a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought. Repeated applications of the construction procedure yields different starting solutions for the local search and the best overall solution is kept as the result. The GRASP local search applies iterative improvement until a locally optimal solution is found. During this phase, starting from the current solution an improving neighbor solution is accepted and considered as the new current solution. In this paper, we propose a variant of the GRASP framework that uses a new “nonmonotone” strategy to explore the neighborhood of the current solution. We formally state the convergence of the nonmonotone local search to a locally optimal solution and illustrate the effectiveness of the resulting Nonmonotone GRASP on three classical hard combinatorial optimization problems: the maximum cut problem (MAX-CUT), the weighted maximum satisfiability problem (MAX-SAT), and the quadratic assignment problem (QAP).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. The QAPLIB - A Quadratic Assignment Problem Library has an online version at http://anjos.mgi.polymtl.ca/qaplib/.

References

  1. Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: Probability distribution of solution time in grasp: an experimental investigation. J. Heuristics 8, 343–373 (2002)

    Article  MATH  Google Scholar 

  2. Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: Ttt plots: a perl program to create time-to-target plots. Optim. Lett. 1, 355–366 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alvarez-Valdes, R., Parreño, F., Tamarit, J.M.: Reactive GRASP for the strip-packing problem. Comput. Oper. Res. 35(4), 1065–1083 (2008)

    Article  MATH  Google Scholar 

  4. Andrade, D.V., Resende, M.G.C.: GRASP with path-relinking for network migration scheduling. In: Proceedings of the international network optimization conference (INOC 2007) (2007)

  5. Andres, C., Miralles, C., Pastor, R.: Balancing and scheduling tasks in assembly lines with sequence-dependent setup times. Eur. J. Oper. Res. 187(3), 1212–1223 (2008)

    Article  MATH  Google Scholar 

  6. Areibi, S., Vannelli, A.: A GRASP clustering technique for circuit partitioning. In: Gu, J., Pardalos, P.M., (eds.), Satisfiability Problems, vol. 35 of DIMACS series on discrete mathematics and theoretical computer science, pp. 711–724. American Mathematical Society, Providence (1997)

  7. Arroyo, J.E.C., Vieira, P.S., Vianna, D.S.: A GRASP algorithm for the multi-criteria minimum spanning tree problem. Ann. Oper. Res. 159, 125–133 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Asano, T.: Approximation algorithms for MAX-SAT: Yannakakis vs. Goemans–Williamson. In: 5th IEEE Israel symposium on the theory of computing and systems, pp. 24–37 (1997)

  9. Atkinson, J.B.: A greedy randomised search heuristic for time-constrained vehicle scheduling and the incorporation of a learning strategy. J. Oper. Res. Soc. 49, 700–708 (1998)

    Article  MATH  Google Scholar 

  10. Barahona, F.: The max-cut problem in graphs not contractible to \(k_5\). Oper. Res. Lett. 2, 107–111 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  11. Bard, J.F., Huang, L., Jaillet, P., Dror, M.: A decomposition approach to the inventory routing problem with satellite facilities. Transp. Sci. 32, 189–203 (1998)

    Article  MATH  Google Scholar 

  12. Battiti, R., Protasi, M.: Approximate algorithms and heuristics for the MAX-SAT. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, vol. 1, pp. 77–148. Kluwer Academic Publishers, Berlin (1998)

    Chapter  Google Scholar 

  13. Benlic, U., Hao, J.-K.: Breakout local search for maximum clique problems. Comput. Oper. Res. 40(1), 192–206 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  14. Binato, S., Hery, W.J., Loewenstern, D., Resende, M.G.C.: A greedy randomized adaptive search procedure for job shop scheduling. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys on Metaheuristics, pp. 58–79. Kluwer Academic Publishers, Berlin (2002)

    Google Scholar 

  15. Brusco, M.J., Stahl, S.: Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices. J. Classif. 17(2), 197–223 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  16. Burer, S., Monteiro, R.D.C.: Rank-two relaxation heuristics for max-cut and other binary quadratic programs. SIAM J. Optim. 12, 503–521 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  17. Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. SIAM Press, Philadelphia (2009)

  18. Burkard, R.E., Karisch, S.E., Rendl, F.: QAPLIB—a quadratic assignment problem library. J. Global Optim. 10, 391–403 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  19. Carreto, C., Baker, B.: A GRASP interactive approach to the vehicle routing problem with backhauls. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys on Metaheuristics, pp. 185–200. Kluwer Academic Publishers, Berlin (2002)

    Chapter  Google Scholar 

  20. Chen, J., Friesen, D., Zheng, H.: Tight bound on johnson’s algorithm for MAX-SAT. In: Proceedings of the 12th annual IEEE conference on computational complexity, pp. 274–281 (1997)

  21. Christofides, N., Benavent, E.: An exact algorithm for the quadratic assignment problem. Oper. Res. 37(5), 760–768 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  22. Commander, C.W.: Maximum cut problem, MAX-CUT. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 1991–1999. Springer, Berlin (2009)

    Chapter  Google Scholar 

  23. Contreras, I.A., Díaz, J.A.: Scatter search for the single source capacitated facility location problem. Ann. Oper. Res. 157, 73–89 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  24. Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the third annual ACM symposium on theory of computing, pp. 151–158 (1971)

  25. Cravo, G.L., Ribeiro, G.M., Nogueira Lorena, L.A.: A greedy randomized adaptive search procedure for the point-feature cartographic label placement. Comput. Geosci. 34(4), 373–386 (2008)

    Article  Google Scholar 

  26. Drezner, Z., Hahn, P.M., Taillard, É.D.: Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods. Ann. Oper. Res. 139, 65–94 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  27. Eschermann, B., Wunderlich, H.J.: Optimized synthesis of self-testable finite state machines. In: 20th international symposium on fault-tolerant computing (FFTCS 20), pp. 390–397 (1990)

  28. Facchiano, A., Festa, P., Marabotti, A., Milanesi, L., Musacchia, F.: Solving Biclustering with a GRASP-like Metaheuristic: Two Case-Studies on Gene Expression Analysis, vol. 7548 of Lecture Notes in Computer Science, pp. 253–267. Springer, Berlin (2012)

  29. Feige, U., Goemans, M.X.: Approximating the value of two proper proof systems, with applications to MAX-2SAT and MAX-DICUT. In: Proceeding of the third Israel symposium on theory of computing and systems, pp. 182–189 (1995)

  30. Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67–71 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  31. Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Global Optim. 6, 109–133 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  32. Ferone, D., Festa, P., Resende, M.G.C.: Hybrid metaheuristics for the far from most string problem. In: Proceedings of HM 2013, vol. 7919 of lecture notes in computer science, pp. 174–188. Springer, Berlin (2013)

  33. Festa, P.: On some optimization problems in molecular biology. Math. Biosci. 207(2), 219–234 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  34. Festa, P.: A biased random-key genetic algorithm for data clustering. Math. Biosci. 245(1), 76–85 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  35. Festa, P., Pardalos, P.M.: Efficient solutions for the far from most string problem. Ann. Oper. Res. 196(1), 663–682 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  36. Festa, P., Pardalos, P.M., Pitsoulis, L.S., Resende, M.G.C.: GRASP with path-relinking for the weighted MAXSAT problem. ACM J. Exp. Algorithmics 11, 1–16 (2006)

    MathSciNet  MATH  Google Scholar 

  37. Festa, P., Pardalos, P.M., Resende, M.G.C.: Algorithm 815: FORTRAN subroutines for computing approximate solution to feedback set problems using GRASP. ACM Trans. Math. Softw. 27, 456–464 (2001)

    Article  MATH  Google Scholar 

  38. Festa, P., Pardalos, P.M., Resende, M.G.C., Ribeiro, C.C.: Randomized heuristics for the MAX-CUT problem. Optim. Methods Softw. 17(6), 1033–1058 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  39. Festa, P., Resende, M.G.C.: GRASP: an annotated bibliography. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys on Metaheuristics, pp. 325–367. Kluwer Academic Publishers, Berlin (2002)

    Chapter  Google Scholar 

  40. Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP—Part I: algorithms. Int. Trans. Oper. Res. 16(1), 1–24 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  41. Festa, P., Resende, M.G.C.: An annotated bibliography of GRASP—Part II: applications. Int. Trans. Oper. Res. 16(2), 131–172 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  42. Festa, P., Resende, M.G.C.: GRASP: basic components and enhancements. Telecommun. Syst. 46(3), 253–271 (2011)

    Article  Google Scholar 

  43. Frinhani, R.M.D., Silva, R.M.A., Mateus, G.R., Festa, P., Resende, M.G.C.: GRASP with Path-Relinking for Data Clustering: A Case Study for Biological Data, vol. 6630 of Lecture Notes in Computer Science, pp. 410–420. Springer, Berlin (2011)

  44. Fujisawa, K., Fukuda, M., Fojima, M., Nakata, K.: Numerical evaluation of SDPA (semidefinite programming algorithm). In: High performance optimization, pp. 267–301. Kluwer Academic Publishers, Berlin (2000)

  45. Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company, New York (1979)

    MATH  Google Scholar 

  46. Geoffrion, A.M., Graves, G.W.: Scheduling parallel production lines with changeover costs: practical applications of a quadratic assignment/LP approach. Oper. Res. 24, 595–610 (1976)

    Article  MATH  Google Scholar 

  47. Glover, F.: Tabu search—Part I. ORSA J. Comput. 1, 190–206 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  48. Glover, F.: Tabu search—Part II. ORSA J. Comput. 2, 4–32 (1990)

    Article  MATH  Google Scholar 

  49. Glover, F.: Tabu search and adaptive memory programing—advances, applications and challenges. In: Barr, R.S., Helgason, R.V., Kennington, J.L. (eds.) Interfaces in Computer Science and Operations Research, pp. 1–75. Kluwer, Berlin (1996)

    Google Scholar 

  50. Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Berlin (1997)

    Book  MATH  Google Scholar 

  51. Goëffon, A., Richer, J.-M., Hao, J.-K.: Progressive tree neighborhood applied to the maximum parsimony problem. IEEE/ACM Trans. Comput. Biol. Bioinf. 5(1), 136–145 (2008)

    Article  Google Scholar 

  52. Goemans, M.X., Williamson, D.P.: A new \(\frac{3}{4}\) approximation algorithm for the maximum satisfiability problem. SIAM J. Discr. Math. 7, 656–666 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  53. Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42(6), 1115–1145 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  54. Goldberg, D.E.: Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Boston (1989)

    MATH  Google Scholar 

  55. Grippo, L., Lampariello, F., Lucidi, S.: A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23, 707–716 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  56. Grippo, L., Palagi, L., Piacentini, M., Piccialli, V., Rinaldi, G.: Speedp: an algorithm to compute sdp bounds for very large max-cut instances. Math. Program. 136(2), 353–373 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  57. Grötschel, M., Pulleyblank, W.R.: Weakly bipartite graphs and the max-cut problem. Oper. Res. Lett. 1, 23–27 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  58. Hadlock, F.O.: Finding a maximum cut of a planar graph in polynomial time. SIAM J. Comp. 4, 221–225 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  59. Hansen, P., Mladenović, N.: Developments of variable neighborhood search. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 415–439. Kluwer Academic Publishers, Berlin (2002)

    Chapter  Google Scholar 

  60. Hastad, J.: Some optimal inapproximability results. J. ACM 48, 798–859 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  61. Heffley, D.R.: The quadratic assignment problem: a note. Econometrica 40(6), 1155–1163 (1972)

    Article  Google Scholar 

  62. Heffley, D.R.: Decomposition of the koopmansbeckmann problem. Reg. Sci. Urban Econ. 10(4), 571–580 (1980)

    Article  Google Scholar 

  63. Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10, 673–696 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  64. Hirsch, M.J., Meneses, C.N., Pardalos, P.M., Ragle, M.A., Resende, M.G.C.: A continuous GRASP to determine the relationship between drugs and adverse reactions. In: Seref, O., Kundakcioglu, O.E., Pardalos, P.M., (eds.), Data Mining, Systems Analysis, and Optimization in Biomedicine, vol. 953 of AIP Conference Proceedings, pp. 106–121. Springer, Berlin (2007)

  65. Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256–278 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  66. Karisch, S.E., Rendl, F., Clausen, J.: Solving graph bisection problems with semidefinite programming. SIAM J. Comput. 12, 177–191 (2000)

    MathSciNet  MATH  Google Scholar 

  67. Karloff, H., Zwick, U.: A \(\frac{7}{8}\)-approximation algorithm for MAX-3SAT. In: Proceedings of the 38th annual IEEE symposium on foundations of computer science, pp. 406–415 (1997)

  68. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

    Chapter  Google Scholar 

  69. Kirkpatrick, S.: Optimization by simulated annealing: quantitative studies. J. Stat. Phys. 34, 975–986 (1984)

    Article  MathSciNet  Google Scholar 

  70. Koopmans, T.C., Beckmann, M.J.: Assignment problems and the location of economic activities. Econometrica 25, 53–76 (1957)

    Article  MathSciNet  MATH  Google Scholar 

  71. Krarup, J., Pruzan, P.M.: Computer-aided layout design. Math. Program. Study 9, 75–94 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  72. Laguna, M., Martí, R.: A GRASP for coloring sparse graphs. Comput. Optim. Appl. 19, 165–178 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  73. De Leone, R., Festa, P., Marchitto, E.: A bus driver scheduling problem: a new mathematical model and a GRASP approximate solution. J. Heuristics 17(4), 441–466 (2011)

    Article  MATH  Google Scholar 

  74. De Leone, R., Festa, P., Marchitto, E.: Solving a bus driver scheduling problem with randomized multistart heuristics. Int. Trans. Oper. Res. 18(6), 707–727 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  75. Li, Y., Pardalos, P.M.: Generating quadratic assignment test problems with known optimal permutations. Comput. Optim. Appl. 1, 163–184 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  76. Li, Y., Pardalos, P.M., Resende, M.G.C.: A greedy randomized adaptive search procedure for the quadratic assignment problem. In Pardalos, P.M., Wolkowicz, H., (eds.), Quadratic Assignment and Related Problems, vol. 16 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pp. 237–261. American Mathematical Society, Providence (1994)

  77. Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21, 498–516 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  78. Loiola, E.M., Maia de Abreu, N.M., Boaventura-Netto, P.O., Hahn, P., Querido, T.: A survey for the quadratic assignment problem. Euro. J. Oper. Res. 176, 657–690 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  79. Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT–25, 1–7 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  80. Martí, R., Laguna, M.: Heuristics and meta-heuristics for 2-layer straight line crossing minimization. Discr. Appl. Math. 127(3), 665–678 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  81. Mautor, T.: Contribution à la résolution des problèmes d’implanation: algorithmes séquentiels et parallèles pour l’affectation quadratique. PhD thesis, Université Pierre et Marie Curie, Paris, France. In: French (1992)

  82. Mavridou, T., Pardalos, P.M., Pitsoulis, L.S., Resende, M.G.C.: A GRASP for the biquadratic assignment problem. Euro. J. Oper. Res. 105, 613–621 (1998)

    Article  MATH  Google Scholar 

  83. Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24, 1097–1100 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  84. Nugent, C.E., Vollman, T.E., Ruml, J.: An experimental comparison of techniques for the assignment of facilities to locations. Oper. Res. 16, 150–173 (1968)

    Article  Google Scholar 

  85. Osman, I.H., Al-Ayoubi, B., Barake, M.: A greedy random adaptive search procedure for the weighted maximal planar graph problem. Comput. Ind. Eng. 45(4), 635–651 (2003)

    Article  Google Scholar 

  86. Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425–440 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  87. Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Prentice-Hall, Upper Saddle River (1982)

    MATH  Google Scholar 

  88. Pardalos, P.M., Pitsoulis, P.S., Resende, M.G.C.: Algorithm 769: Fortran subroutines for approximate solution of sparse quadratic assignment problems using GRASP. ACM Trans. Math. Softw. 23, 196–208 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  89. Pardalos, PM, Resende, M.G.C., (eds.): Handbook of Applied Optimization. Oxford University Press, Oxford (2002)

  90. Pardalos, P.M., Wolkowicz, H.: Quadratic assignment and related problems. In: Pardalos, P.M., Wolkowicz, H. (eds.) High Performance Optimization. American Mathematical Society, Providence (1994)

    Google Scholar 

  91. Poljak, S., Rendl, F., Wolkowicz, H.: A recipe for semidefinite relaxation for \(0\)-\(1\) quadratic programming. J. Global Optim. 7, 51–73 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  92. Pu, G.G., Chong, Z., Qiu, Z.Y., Lin, Z.Q., He, J.F.: A hybrid heuristic algorithm for HW-SW partitioning within timed automata. In: Proceedings of Knowledge-based Intelligent Information and Engineering Systems, vol. 4251 of Lecture Notes in Artificial Intelligence, pp. 459–466. Springer, Berlin (2006)

  93. Resende, M.G.C., Feo, T.A.: A GRASP for satisfiability. In: Johnson, D.S., Trick, M.A., (eds.), Cliques, Coloring, and Satisfiability: The Second DIMACS Implementation Challenge, vol. 26 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pp. 499–520. American Mathematical Society, Providence (1996)

  94. Resende, M.G.C., Pitsoulis, L.S., Pardalos, P.M.: Approximate solution of weighted MAX-SAT problems using GRASP. In: Gu, J., Pardalos, P.M., (eds.), Satisfiability problems, vol. 35 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pp. 393–405. American Mathematical Society, Providence (1997)

  95. Resende, M.G.C., Pitsoulis, L.S., Pardalos, P.M.: Approximate solutions of weighted MAX-SAT problems using GRASP. In: Du, D.-Z., Gu, J., Pardalos, P.M. (eds.) Satisfiability Problem: Theory and Applications, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 393–405. American Mathematical Society, Providence (1997)

    Google Scholar 

  96. Resende, M.G.C., Pitsoulis, L.S., Pardalos, P.M.: Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP. Discr. Appl. Math. 100, 95–113 (2000)

    Article  MATH  Google Scholar 

  97. Resende, M.G.C., Ribeiro, C.C.: A GRASP for graph planarization. Networks 29, 173–189 (1997)

    Article  MATH  Google Scholar 

  98. Ribeiro, C.C., Urrutia, S.: Heuristics for the mirrored traveling tournament problem. Euro. J. Oper. Res. 179, 775–787 (2007)

    Article  MATH  Google Scholar 

  99. Robertson, A.J.: A set of greedy randomized adaptive local search procedure (GRASP) implementations for the multidimensional assignment problem. Comput. Optim. Appl. 19, 145–164 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  100. Roucairol, C.: Du sequentiel au parallele: la recherche arborescente et son application a la programmation quadratique en variables 0 et 1. PhD thesis, Université Pierre et Marie Curie, Paris, France. (In French) (1987)

  101. Sahni, S., Gonzales, T.: P-complete approximation problems. J. Assoc. Comput. Mach. 23, 555–565 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  102. Scriabin, M., Vergin, R.C.: Comparison of computer algorithms and visual based methods for plant layout. Manag. Sci. 22, 172–187 (1975)

    Article  Google Scholar 

  103. Shor, N.Z.: Quadratic optimization problems. Soviet J. Comput. Syst. Sci. 25, 1–11 (1987)

    MathSciNet  MATH  Google Scholar 

  104. Skorin-Kapov, J.: Tabu search applied to the quadratic assingnment problem. ORSA J. Comput. 2(1), 33–45 (1990)

    Article  MATH  Google Scholar 

  105. Steinberg, L.: The backboard wiring problem: a placement algorithm. SIAM Rev. 3, 37–50 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  106. Thonemann, U.W., Bölte, A.: An improved simulated annealing algorithm for the quadratic assignment problem. Technical report, Department of Production and Operations Research (1994)

  107. Trevisan, L.: Approximating satisfiable satisfiability problems. Algorithmica 28(1), 145–172 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  108. Trevisan, L., Sorkin, G.B., Sudan, M., Williamson, D.P.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074–2097 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  109. Wilhelm, M.R., Ward, T.L.: Solving quadratic assignment problems by simulated annealing. IIE Trans. 19(1), 107–119 (1987)

    Article  Google Scholar 

  110. Yannakakis, M.: On the approximation of maximum Satisfiability. In: Proceedings of the Third ACM-SIAM symposium on discrete algorithms, pp. 1–9 (1992)

Download references

Author information

Authors and Affiliations

  1. Fakultät für Mathematik, TU Dortmund, Dortmund, Germany

    M. De Santis

  2. Department of Mathematics and Applications, University of Napoli FEDERICO II, Napoli, Italy

    P. Festa

  3. Istituto di Analisi dei Sistemi ed Informatica-CNR, Rome, Italy

    G. Liuzzi

  4. Dipartimento di Ingegneria Informatica Automatica e Gestionale, “La Sapienza” University of Rome, Rome, Italy

    S. Lucidi

  5. Dipartimento di Matematica, University of Padova, Padua, Italy

    F. Rinaldi

Authors
  1. M. De Santis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. Festa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. G. Liuzzi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. S. Lucidi
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. F. Rinaldi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to P. Festa.

Appendices

Appendix 1: Detailed tables for MAX-CUT, MAX-SAT and QAP

In this appendix, we report the detailed tables related to the comparison between NM-GRASP and the original version of GRASP for MAX-CUT, MAX-SAT and QAP. The first column of the three tables reports the name of the instance. The remaining columns report for each of the two approaches the average CPU time (Time), the average number of iterations (Iter), the average objective function value (Obj) with the standard deviation in brackets, and the best objective function value obtained over the ten runs (Best Obj) with the number of times the best value is obtained in brackets.

Appendix 2: Time to target-plots analysis on MAX-CUT problems

To plot the empirical distribution, we associate with the i-th sorted running time \((t_i)\) a probability \(p_i = (i - \frac{1}{2} )/100\), and plot the points \(z_i = (t_i , p_i )\), for \(i = 1,\ldots ,100\). For the instances g1250.n, G40, sg3dl142000.mc, and toruspm3-15-50 we fixed as target values 2518, 2275, 2379, and 2925, respectively. These values represent a standard target for both heuristics. As we can see in Fig. 9, apart from the instance toruspm3-15-50 where for 3 runs the classical GRASP is better, we can notice that the NM-GRASP is always superior. It is able to reach the target value in less than 100 s CPU time for all the runs, while in several runs the classical GRASP needs more than 1000 s.

Fig. 9
figure 9

TTTplots for the easy targets

Full size image
Fig. 10
figure 10

TTTplots for the classical GRASP targets

Full size image
Fig. 11
figure 11

TTTplots for the Nonmonotone GRASP targets

Full size image

Figure 10 depicts the empirical distributions of the random variable time-to-target-solution-value using as target values 2532, 2293, 2382, and 2932, for the instances g1250.n, G40, sg3dl142000.mc, and toruspm3-15-50, respectively. These values are the best objective function values found by the classical GRASP over 10 runs. As we can see from the plots, also in this case, the NM-GRASP is able to reach the target value in less than 100 s for all the runs. On the other hand, the classical GRASP failed to reach the target solution within the time limit in several runs, especially for instances g1250.n and G40.

By using instances g1250.n, G40, sg3dl142000.mc, and toruspm3-15-50, we plot in Fig. 11 the empirical distributions of the random variable time-to-target-solution-value using as target values 2556, 2362, 2420, and 2980, respectively. These target values are the best cuts found by the NM-GRASP over 10 runs. In this case, the classical GRASP failed to reach the target solution within the time limit for all runs and all instances. On the contrary, the NM-GRASP is able to reach the target solution for all runs for instances g1250.n and sg3dl142000.mc.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

De Santis, M., Festa, P., Liuzzi, G. et al. A nonmonotone GRASP. Math. Prog. Comp. 8, 271–309 (2016). https://doi.org/10.1007/s12532-016-0107-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-016-0107-9

Keywords

Mathematics Subject Classification

Search

Navigation