Local search with alternating neighborhoods

Yu. A. Kochetov ; N. Mladenovich ; P. Khansen

Diskretnyj analiz i issledovanie operacij, Tome 10 (2003) no. 1, pp. 11-43.

Bibliographie

[1] Goncharov E. N., Kochetov Yu. A., “Veroyatnostnyi poisk s zapretami dlya diskretnykh zadach bezuslovnoi optimizatsii”, Diskret. analiz i issled. operatsii. Ser. 2, 9:2 (2002), 13–30 | MR | Zbl

[2] Dobrynin A. A., “Postroenie grafov s palindromnym polinomom Vinera”, Vychislitelnye sistemy, Sb. nauch. tr., no. 151, In-t matematiki SO RAN, Novosibirsk, 1994, 37–54 | MR

[3] Kemeni Dzh., Snell Dzh., Konechnye tsepi Markova, Nauka, M., 1970

[4] Papadimitriu X., Staiglits K., Kombinatornaya optimizatsiya: Algoritmy i slozhnost, Mir, M., 1985 | MR

[5] Gastrigin L. A., “Sluchainyi poisk – spetsifika, etapy istorii i predrassudki”, Voprosy kibernetiki, no. 33, Nauch. sovet po kompleksnoi probleme “Kibernetika” AN SSSR, M., 1978, 3–16

[6] Ford L., Falkerson D., Potoki v setyakh, Mir, M., 1966 | Zbl

[7] Aarts E. H. L., Korst J. H. M., Simulated annealing and Boltzmann machines, Wiley, Chichester, 1989 | MR | Zbl

[8] Aarts E. H. L., Korst J. H. M., Laarhoven van F. J. M., “Simulated annealing”, Local search in combinatorial optimization, Wiley, Chichester, 1997, 91–120 | MR | Zbl

[9] Ahnja R. K., James O. E., Orlin B., Punnen A. P., “A survey of very large-scale neighborhood search techniques”, Discrete Appl. Math., 123:1–3 (2002), 75–102 | MR

[10] Bent R., Van Hentenryck P., A two stage hybrid local search for the vehicle routing problem with time windows, Report CS-01-06. Dept. of Comput. Sci., Brown Univ., 2001

[11] Besten den M., Stiitzle T., “Neighborhood revisited: An experimental investigation into the effectiveness of variable neighborhood descent for scheduling”, MIC2001 – 4th Metaheuristics International Conference (Porto, July 16–21, 2001), 545–549

[12] Bock F., “An algorithm for solving traveling-salesman and related network optimization problems”, Abstract, Bulletin Fourteenth National Meeting of the Operations Research Society of America, 1958, 897

[13] Boese K. D., Kahng A. B., Muddu S., “A new adaptive multi-start technique for combinatorial global optimizations”, Oper. Res. Lett., 16:2 (1994), 101–114 | DOI | MR

[14] Braysy O., Local search and variable neighborhood search algorithm for the vehicle routing with time windows. Acta Wasaensia, Preprint. No 87, 2001, 168 pp.

[15] Brimberg J., Hansen P., Lih K.-W., Mladenovic N. Breton M., “An oil pipeline design problem”, Les Cahiers du GERAD G-2000-73, Monreal, Canada, 2000

[16] Brimberg J., Hansen P., Mladenovic N., “Convergence of veriable neighborhood search”, Les Cahiers du GERAD G-2000-73, Monreal, Canada, 2000

[17] Brimberg J., Hansen P., Mladenovic N., Taillard E., “Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem”, Oper. Res., 48:3 (2000), 444–460 | DOI

[18] Brimberg J., Mladenovic N., “A variable neighborhood algorithm for solving the continuous location-allocation problem”, Stud. Locat. Anal., 10 (1996), 1–12 | MR | Zbl

[19] Brucker P., Hurink J., Werner F., “Improving local search heuristics for some scheduling problems. Pt II”, Discrete Appl. Math., 72:1–2 (1997), 47–69 | DOI | MR | Zbl

[20] Burkard R. E., Deineko V. G., Woeginger G. J., “The traveling salesman problem and the PQ-tree”, Integer programming and combinatorial optimization, Proc., Lecture Notes in Comput. Sci., 1084, Springer, Berlin, 1996, 490–504 | MR

[21] Burke E. K., Causmaecker de P., Petrovic S., Berghe G. V., “Variable neighbourhood search for nurse rostering problems”, MIC'2001 – 4th Metaheuristics Intern. conf. (Porto July 16–21), 2001, 755–760

[22] Burke E. K., Cowling P., Keuthen R., “Effective local and guided variable neighborhood search methods for the asymmetric traveling salesman problem”, Proc. of the Evo Workshops, Lecture Notes in Comput. Sci., 2037, Springer, Berlin, 2001, 203–212 | Zbl

[23] Campos de L. M., Puerta J. M., “Stochastic local algorithms for linear ning belief networks: searching in the space of the orderings”, Symbolic and quantitative approaches to reasoning with uncerfainty. 6th European conf. ECSQARU 2001, Proceedings (Toulouse, September 19–21, 2001), Lecture Notes in Comput. Sci., 2143, Springer, Berlin, 2001, 228–239 | Zbl

[24] Caporossi G., Dobrynin A. A., Gutman I., Hansen P., “Trees with palindromic Hosoya polynomials”, Graph Theory Notes N.Y., 37 (1999), 10–16 | MR

[25] Caporossi G., Hansen P., “Variable neighborhood search for extremal graphs”, Discrete Math., 212:1–2 (2000), 29–44 | DOI | MR | Zbl

[26] Costa M-C., Monclar F-R., Zrikem M., “Variable neighborhood search for the optimization of cable layout problem”, MIC2001 – 4th Metaheuristics Intern. conf. (Porto, July 16–21), 2001, 749–753

[27] Crainic T. G., Gendreau M., Hansen P., Hoeb N., Mladenović N., “Parallel variable neighbourhood search for the $p$-median”, MIC'2001 – 4th Metaheuristics Intern. conf. (Porto, July 16–21), 2001, 595–599

[28] Crispim J., Brandao J., “Reactive tabu search and variable neighbourhood descent applied to the vehicle routing problem with backhauls”, MIC'2001 – 4th Metaheuristics Intern. conf. (Porto, July 16–21), 2001, 631–636

[29] Croes G. A., “A method for solving-traveling salesman problems”, Oper. Res., 6 (1958), 791–812 | DOI | MR

[30] Davidovic T., Hansen P., Mladenovic N., “Variable neighborhood search for multiprocessor scheduling with communication delays”, MIC'2001 – 4th Metaheuristics Intern. conf. (Porto, July 16–21), 2001, 737–741

[31] Desrosiers J., Mladenovic N., Villeneuve D., “Design of balanced MBA student teams”, MIC'2001 – 4th Metaheuristics Intern. conf. (Porto, July 16–21), 2001, 281–285

[32] Droste S., Jansen T., Wegener I., “Optimization with randomized search heuristics – the NFL theorem, realistic scenarios, and difficult functions”, Theoretical Comput. Sci., 287:1 (2002), 131–144 | DOI | MR | Zbl

[33] “Fajtlowicz S.”, Discrete Math., 72:2 (1988), 113–118 | MR

[34] Feo T., Resende M., “Greedy randomized adaptive search”, J. Global Optim., 6 (1995), 109–133 | DOI | MR | Zbl

[35] Festa P., Pardalos P. M., Resende M. G. C., Ribeiro C. C., “GRASP and VNS for max-cut”, MIC'2001 – 4th Metaheuristics Intern. conf. (Porto, July 16–21), 2001, 371–376

[36] Fridman M. L., Johnson D. S., McGeoch L. A., Ostheimer G., “Data structures for traveling salesman”, J. Algorithms, 18:3 (1995), 432–479 | DOI | MR

[37] Gendreau M., Hertz A., Laporte G., “New insertion and postoptimization procedures for the traveling selesman problem”, Oper. Res., 40:6 (1992), 1086–1094 | DOI | MR | Zbl

[38] Gendreau M., Hertz A., Laporte G., “The traveling selesman problem with back hauls”, Comput. Oper. Res., 23:5 (1996), 501–508 | DOI | MR | Zbl

[39] Ghiani G., Hertz A., Laporte G., “Recent algorithmic advances for arc routing problems”, Les Cahiers du GERAD G-2000-40, Monreal, Canada, 2000

[40] Glover F., “Tabu search: pt I”, ORSA J. Comp., 1 (1989), 190–206 | MR | Zbl

[41] Glover F., “Tabu search: pt II”, ORSA J. Comp., 2 (1990), 4–32 | Zbl

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

[43] Goldberg D. E., Genetic algorithms in search, optimization, and machine learning, Addison-Wesley, Reading, MA, 1989

[44] Gonzales C. G., Perez-Brito D., “A variable neighborhood search for solving linear ordering problem”, MIC2001 – 4th Metaheuristics Intern. conf. (Porto, July 16–21), 2001, 181–185

[45] Grover L. K., “Local search and the local structure of NP-complete problems”, Oper. Res. Lett., 12:4 (1992), 235–244 | DOI | MR

[46] Gutin G., “Exponential neighborhood local search for the traveling salesman problem”, Comput. Oper. Res., 26:4 (1999), 313–320 | DOI | MR | Zbl

[47] Gutin G., Yeo A., “Small diameter neighborhood graphs for the traveling salesman problem: at most four moves from tour to tour”, Comput. Oper. Res., 26:4 (1999), 321–327 | DOI | MR | Zbl

[48] Gutman I., “Some properties of the Wiener polynomial”, Graph Theory Notes N.Y., 25, 1993, 13–18

[49] Gutman I., Estrada E., Ivanciuc O., “Some properties of the Wiener polynomial of trees”, Graph Theory Notes N.Y., 36, 1999, 7–13 | MR

[50] Hansen P., Jaumard B., Mladenovic N., Parreira A., “Variable neighborhood search for weighted maximum satisfiability problem”, Les Cahiers du GERAD G-2000-62, Monreal, Canada, 2000

[51] Hansen P., Mladenovic N., “Variable neighborhood search for the $p$-median”, Location Sci., 5 (1997), 207–226 | DOI | MR | Zbl

[52] Hansen P., Mladenovic N., “An introduction to variable neighborhood search”, Metaheuristics, advances and trends in local search paradigms for optimization, Kluwer Acad. Publ., Dordrecht, 1999, 433–458 | MR | Zbl

[53] Hansen P., Mladenovic N., “Variable neighborhood search: principles and applications”, invited review, European J. Oper. Res., 130:3 (2001), 449–467 | DOI | MR | Zbl

[54] Hansen P., Mladenović N., “J-Means: a new local search heuristic for minimum sum-of-squares clustering”, Pattern Recognition, 34 (2001), 405–413 | DOI | Zbl

[55] Hansen P., Mladenović N., “Development of variable neighborhood search”, Essays and surveys in metaheuristics, Kluwer Acad. Publ., Dordrecht, 2002, 415–440 | MR

[56] Hansen P., Mladenović N., Perez-Brito D., “Variable neighborhood decomposition search”, J. Heuristics, 7:4 (2001), 335–350 | DOI | Zbl

[57] Hansen P., Mladenović N. Urosevic D., “Variable neighborhood search for maximum clique”, Les Cahiers du GERAD G-2001-25, Monreal, Canada, 2001

[58] Hertz A., Laporte G., Mittaz M., “A tabu search heuristic for the capacitated arc routing problem”, Oper. Res., 48:1 (2000), 129–135 | DOI | MR | Zbl

[59] Hosoya H., “On some counting polynomials in chemistry”, Discrete Appl. Math., 19:2 (1988), 239–257 | DOI | MR | Zbl

[60] Hwang F. K., Richards D. S., Winter P., The Steiner tree problem, North-Holland, Amsterdam, 1992 | MR | Zbl

[61] Johnson D. S., “Local optimization and the traveling salesman problem”, Automata, languages, and programming, Proc., Lecture Notes in Comput. Sci., 443, Springer-Verl., Berlin, 1990, 446–461 | MR

[62] Johnson D. S., Aragon C. R., McGeoch L. A., Schevon C., “Optimization by simulated annealing: an experimental evaluation, part I: Graph partitioning”, Oper. Res., 37:6 (1989), 865–892 | DOI | Zbl

[63] Johnson D. S., McGeoch L. A., “The traveling salesman problem: a case study”, Local search in combinatorial optimization, Wiley, Chichester, 1997, 215–310 | MR | Zbl

[64] Johnson D. S., Papadimitriou S. H., Yannakakis M., “How easy is local search?”, J. Comput. System Sci., 37:1 (1988), 79–100 | DOI | MR | Zbl

[65] Kernighan B. W., Lin S., “An efficient heuristic procedure for partitioning graphs”, Bell Syst. Tech. J., 49 (1970), 291–307 | Zbl

[66] Kolish R., Hartman S., “Heuristic algorithms for the resource-costrained project scheduling problem: classification and computational analysis”, Project scheduling: recent models, algorithms and applications, Kluwer Acad. Publ., Dordrecht, 1999, 147–178

[67] Krentel M. W., “Structure in locally optimal solutions”, Proc. of the 30th annual sympos. on foundation of comput. sci., IEEE Comput. Soc. Press, Los Alamihos, CA, 1989, 216–222

[68] Krentel M. W., “On finding and verifying locally optimal solutions”, SIAM J. Comput., 19:4 (1990), 742–751 | DOI | MR

[69] Laarhoven van P. J. M., Aarts E. H. L., Lenstra J. K., “Job shop scheduling by simulated annealing”, Oper. Res., 40:1 (1992), 113–125 | DOI | MR | Zbl

[70] Lepovic M., Gutman I., “A collective property of trees and chemical trees”, J. Chem. Inform. Comput. Sci., 38:5 (1998), 823–826 | DOI

[71] Lin S., “Computer solutions of the traveling salesman problem”, Bell Syst. Tech. J., 44 (1965), 2245–2269 | MR | Zbl

[72] Lin S., Kernighan B. W., “An efficient heuristic algorithm for the traveling-salesman problem”, Oper. Res., 21:2 (1973), 498–516 | DOI | MR | Zbl

[73] Lopez F. G., Batista B. M., Moreno-Perez J., Moreno-Vega M., The parallel variable neighborhood search for the $p$-median problem, Res. Rep. Univ. of La Laguna, Spain, 2000

[74] Loudni S., Boizumault P., “VNS/LDS+CP: A hybrid method for constraint optimization in anytime contexts”, MIC2001 – 4th Metaheuristics Intern. Conf. (Porto, July 16–21), 2001, 761–765

[75] Macken C. A., Hagan P. S., Perelson A. S., “Evolutionary walks on rugged landscapes”, SIAM J. Appl. Math., 51:3 (1991), 799–827 | DOI | MR | Zbl

[76] Martins S. L., Resende M. G. C., Ribeiro C. C., Pardalos P., “A parallel GRASP for the Steiner tree problem in graphs using a hybrid local search strategy”, J. Global Optim., 17 (2000), 267–283 | DOI | MR | Zbl

[77] Mittaz M., Problemes de cheminements optimaux dans des reseaux avec contraintes associess aux arrcs, Ph. D. Thesis, Ecole Polytechnique Federale de Lausanne, Switzerland, 2001

[78] Mladenović N., Hansen P., “Variable neighborhood search”, Comput. Oper. Res., 24 (1997), 1097–1100 | DOI | MR | Zbl

[79] Mladenović N., Moreno J. P., Moreno-Vega A., “A chain-interchange heuristic method”, Yugos. J. Oper. Res., 6 (1996), 41–54 | MR | Zbl

[80] Mladenović N., Petrović J., Kovacević-Vujcić V., Cangalovic M., Solving spread spectrum radar polyphase cade design problem by tabu search and variable neighborhood search, SMG Rep. R-00-09, European J. Oper. Res., Univ. Libre Bruxelles, Belgium, 2000 (to appear) | MR

[81] Mladenović N., Urošević D., “Variable neighborhood search for the $k$-cardinality tree”, MIC2001 – 4th Metaheuristics Intern. conf. (Porto, July 16–21, 2001), 743–748

[82] Motwani R., Raghavan P., Randomized algorithms, Cambridge Univ. Press, Cambridge, 1995 | MR | Zbl

[83] Nicholson T. A. J., “A sequential method for discrete optimization problems and its application to the assignment, traveling salesman and tree scheduling problems”, J. Inst. Math. Appl., 13 (1965), 362–375

[84] Ochi L. S., Silva M. B., Drummond L., “Metaheuristics based GRASP and VNS for solvimg the traveling purchaser problem”, MIC'2001 – 4th Metaheuristics Intern. conf. (Porto, July 16–21), 2001, 489–494

[85] Osman I. H., Laporte G., “Metaheuristics: a bibliography”, Ann. Oper. Res., 63 (1996), 513–628 | DOI | MR

[86] Page E. S., “On Monte Carlo methods in congestion problems. I: Searching for an optimum in discrete situations”, Oper. Res., 13:2 (1965), 291–299 | DOI | MR | Zbl

[87] Pesant G., Gendreau M., “A view of local search in constraint programming”, Principles and practice of constraint programming-CP 96, Lecture Notes in Comput. Sci., 1118, Springer, Berlin, 1996, 353–366

[88] Pesant G., Gendreau M., “A constraint programming framework for local search methods”, J. Heuristics, 5 (1999), 255–279 | DOI | Zbl

[89] Punnen A. P., The traveling salesman problem: new polynomial approximation algorithms and domination analysis, Res. Rep. St. John Univ. New Brunswick, 1996

[90] Reiter S., Sherman G., “Discrete optimizing”, J. Soc. Indust. Appl. Math., 13 (1965), 864–889 | DOI | MR | Zbl

[91] Resende M. G. C., Pitsoulis L. S., Pardalos P. M., “Approximate solution of weighted MAX-SAT problem using GRASP”, Satisfiability problem: theory and applications, Amer. Math. Soc., Providence, PI, 1997, 393–405 | MR | Zbl

[92] Ribeiro C., Uchoa E., Werneck R., A hybrid GRASP with perturbations for the Steiner problem in graphs, Technical rep. Comput. Sci. Dep. Catolic Univ. of Rio de Janeiro, 2001 | MR

[93] Rodriggue I., Moreno-Vega M., Moreno-Perez J., Heuristics for routingmedian problems, SMG Rep. Univ. Libre de Bruxelles, Belgium, 1999

[94] Schaffer A. A., Yannakakis M., “Simple local search problems that are hard to solve”, SIAM J. Comput., 20:1 (1991), 56–87 | DOI | MR

[95] Schumacher C., Black box search – framework and methods, Ph. D. Thesis, The Univ. of Tennessee, Knoxville, USA, 2000 | Zbl

[96] Shaw P., “Using constraint programming and local search methods to solve vehicle routing problems”, Principles and practice of constraint programming, CP'98, 1998, 417–431

[97] Stadler P. F., “Correlation in landscapes of combinatorial optimization problems”, Europhys. Lett., 20 (1992), 479–482 | DOI | MR

[98] Taillard E., Voss S., “POPMUSIC – Partial optimization metaheuristic under special intensification conditions”, Essays and surveys in metaheuristics, Kluwer Acad. Publ., Dordrecht, 2001, 613–630 | MR

[99] Tovey C. A., “Local improvement on discrete structures”, Local search in combinatorial optimization, Wiley, Chichester, 1997, 57–90 | MR

[100] Verhoeven M. G. A., “Tabu search for resource-constrained scheduling”, European J. Oper. Res., 106:2 (1998), 266–276 | DOI | Zbl

[101] Verhoeven M. G. A., Severens M. E. M., Aarts E. H. L., “Local search for Steiner trees in graphs”, Modern search methods, John Wiley and Sons, Inc., N.Y., 1996, 117–129

[102] Verhoeven M. G. A., Swinkels P. C. J., Aarts E. H. L., Parallel local search and the traveling salesman problem, Working paper. Philips Res. Lab. Eindhoven, 1995

[103] Weiner P., Savage S. L., Bagchi A., “Neighborhood search algorithms for quaranteeing optimal traveling salesman tours must be inefficient”, J. Comput. System Sci., 12:1 (1976), 25–35 | MR | Zbl

[104] Wolpert D. H., Macready W. J., No free lunch theorem for search, Rep. SFI-TR-95-02-010, The Santa Fe Inst., Santa Fe, 1995 | MR

[105] Yannakakis M., “Computational complexity”, Local search in combinatorial optimization, Wiley, Chichester, 1997, 19–55 | MR | Zbl