Ejection chain and filter-and-fan methods in combinatorial optimization

• Aarts EHL, Van Laarhoven PJM, Lenstra JK, Ulder NLJ (1994) A computational study of local search algorithms for job shop scheduling. ORSA J Comput 6(2):118–125

  Google Scholar 

• Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manage Sci 34 (3):391–401

  Google Scholar 

• Ahuja RK, Orlin JB, Sharma D (2001) Multi-exchange neighborhood search structures for the capacitated minimum spanning tree problem. Math Program 91:71–97

  Google Scholar 

• Ahuja RK, Orlin JB, Sharma D (2002) Very large-scale neighborhood search for the quadratic assignment problem. submitted to INFORMS J Comput

• Ahuja RK, Orlin JB, Sharma D (2003) A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem. Operat Res Lett 31:185–194

  Article  Google Scholar 

• Amberg A, Domschke W, Voß S (1996) Capacitated minimum spanning trees: algorithms using intelligent search. Comb Opt Theory Practice 1:9–39

  Google Scholar 

• Applegate D, Cook W, Rohe A (2003) Chained Lin-Kernighan for large traveling salesman problems. INFORMS J Comput 15:82–92

  Article  Google Scholar 

• Balas E, Vazacopoulos A (1998) Guided local search with shifting bottleneck for job shop scheduling. Manage Sci 44(2):262–275

  Google Scholar 

• Cavique L, Rego C, Themido I (1999) Subgraph ejection chains and tabu search for the crew scheduling problem. J Operat Res Soci 50:608–616

  Article  Google Scholar 

• Cao B, Glover F (1997) Tabu search and ejection chains: application to a node weighted version of the cardinality-constrained TSP. Manage Sci 43(7):908–921

  Google Scholar 

• Cela E (1998) The quadratic assignment problem: theory and algorithms. Kluwer, Boston

  Google Scholar 

• Chan HS, Dill KA (1993) The protein folding problem. Phys Today 46(2):24–32

  Google Scholar 

• Chrobak M, Szymacha T, Krawczyk A (1990) A data structure useful for finding hamiltonian cycles. Theoret Comput Sci 71:419–424

  Article  Google Scholar 

• Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. In: Mingozzi A, Toth P, Sandi C (eds) Combinatorial optimisation. Wiley, Chichester, pp 315–338

  Google Scholar 

• Cirasella J, Johnson DS, McGeoch LA, Zhang W (2001) The asymmetric traveling salesman problem: algorithms, instance generators and tests. In: Proceedings of the algorithm engineering and experimentation, third international workshop, ALENEX 2001, pp 32–59

• Cornuéjols G, Nemhauser GH, Wolsey L (1990) “The uncapacitated facility location problem. In: Mirchandani P, Francis R (eds) Discrete location theory. J Wiley, New York, pp 119–171

  Google Scholar 

• Dill KA (1985) “Theory for the folding and stability of globular proteins,”. Biochemistry 24(6): 1501-1509

  Article  Google Scholar 

• Dorndorf U, Pesch E (1994) Fast clustering algorithms. ORSA J Comput 6:141–153

  Google Scholar 

• Fisher ML (1994) Optimal solution of vehicle routing problems using minimum k-trees. Operat Res 42(4):626–642

  Google Scholar 

• Fredman ML, Johnson DS, McGeoch LA, Ostheimer G (1995) Data structures for traveling salesmen. J Algorithms 18:432–479

  Article  Google Scholar 

• Funke B, Grünert T, Irnich S (2005) A note on single alternating cycle neighborhoods for the TSP. J Heuristics, 11:135–146

  Article  Google Scholar 

• Gamboa D, Rego C, Glover F (2005) Data structures and ejection chains for solving large-scale traveling salesman problems. Eur J Operat Res 160:154–171

  Article  Google Scholar 

• Gamboa D, Rego C, Glover F (2006a) Implementation analysis of efficient heuristic algorithms for the traveling salesman problem. Comput Operat Res 33:1161–1179

  Article  Google Scholar 

• Gamboa D, Rego C, Glover F, Osterman C (2006b) An experimental evaluation of ejection chain algorithms for the traveling salesman problem. School of Business Administration, University of Mississippi, MS

• Gao LL, Robinson EP (1994) Uncapacitated facility location: general solution procedures and computational experience. Eur J Operat Res 76:410–427

  Article  Google Scholar 

• Gavish B (1982) Topological design of centralized computer networks: formulations and algorithms. Networks 12:355–377

  Google Scholar 

• Gavish B (1991) Topological design telecommunications networks—local access design methods. Ann Operat Res 33:17–71

  Article  Google Scholar 

• Glover F (1991) Multilevel tabu search and embedded search neighborhoods for the traveling salesman problem. Leeds School of Business, University of Colorado, Boulder

• Glover F (1992) New ejection chain and alternating path methods for traveling salesman problems. Comput Sci Operat Res 449–509

• Glover F (1996) Ejection chains, reference structures and alternating path methods for traveling salesman problems. Discrete Appli Math 65:223–253

  Article  Google Scholar 

• Glover F (1998) A template for scatter search and path relinking. In: Hao J-K, Lutton E, Ronald E, Schoenauer M, Snyers D (eds) Artificial evolution. Lecture notes in computer science, vol. 1363. Springer, Berlin Heidelberg New York, pp 3–51

  Google Scholar 

• Glover F, Laguna M (1997) Tabu Search. Kluwer, Boston

  Google Scholar 

• Gonçalves JF, Mendes JJM, Resende MGC (2005) A hybrid genetic algorithm for the job shop scheduling problem. Eur J Operat Res 167:77–95

  Article  Google Scholar 

• Grabowski J, Wodecki M (2005) A very fast tabu search algorithm for job shop problem. In: Rego C, Alidaee B (eds) Metaheuristic optimization via memory and evolution: tabu search and scatter search. Kluwer, Boston, pp 191–211

  Google Scholar 

• Greistorfer P, Rego C (2006) A simple filter-and-fan approach to the facility location problem. Comput Operat Res 33(9):2590–2601

  Article  Google Scholar 

• Helsgaun K (2000) An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur J Operat Res 126:106–130

  Article  Google Scholar 

• Johnson DS, McGeoch LA (1997) The traveling salesman problem: a case study in local optimization. In: Local search in combinatorial optimization: Aarts EHL, Lenstra JK (eds) J Wiley, 215–310

• Johnson DS, McGeoch LA, Glover F, Rego C (2000) 8th DIMACS implementation challenge: the traveling salesman problem. http://www.research. att.com/~dsj/chtsp/

• Kanellakis PC, Papadimitriou CH (1980) Local search for the asymmetric traveling salesman problem. Operat Res 28:1086–1099

  Google Scholar 

• Lengauer T (1993) Algorithmic research problems in molecular bioinformatics. In: Proceedings of the second israel symposium on theory of computing systems, ISTCS 1993, Natanya, Israel, 177–192

• Lesh N, Mitzenmacher M, Whitesides S (2003) A complete and effective move set for simple protein folding. In: Proceedings of the 7th annual international conference on research in computational molecular biology (RECOMB), ACM Press, New York, pp 188–195

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

  Article  Google Scholar 

• Mathew F, Rego C (2006) Recent advances in heuristic algorithms for the capacitated minimum spanning tree problem. In: Proceedings of the 37th annual meeting of decision sciences institute (DSI). 31021–31026

• Mathew F, Rego C, Glover F (2006) A filter-and-fan algorithm for the capacitated minimum spanning tree. School of Business Administration, University of Mississippi, MS

• Nowichi E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manage Sci 42(6):797–813

  Google Scholar 

• Osterman C, Rego C (2003) The satellite list and new data structures for symmetric traveling salesman problems. School of Business Administration, University of Mississippi, MS

• Patterson R, Pirkul H, Rolland E (1999) Memory adaptive reasoning for solving the capacitated minimum spanning tree problem. J Heuristics 5:159–180

  Article  Google Scholar 

• Pinedo ML (2006) Planning and scheduling in manufacturing and services. Series in operations research and financial engineering. Springer, Berlin Heidelberg New York

  Google Scholar 

• Rego C (1998a) Relaxed tours and path ejections for the traveling salesman problem. Eur J Operat Res 106:522–538

  Article  Google Scholar 

• Rego C (1998b) A subpath ejection method for the vehicle routing problem. Manage Sci 44(10):1447–1459

  Google Scholar 

• Rego C (2001) Node ejection chains for the vehicle routing problem: sequential and parallel algorithms. Parallel Comput 27:201–222

  Article  Google Scholar 

• Rego C, Duarte R (2006) A filter and fan approach for the job shop scheduling problem. School of Business Administration, University of Mississippi, MS

• Rego C, Glover F (2002) Local search and metaheuristics for the traveling salesman problem. In: Gutin G, Punnen A (eds) The traveling salesman problem and its variations. Kluwer, Boston, pp 309–368

  Google Scholar 

• Rego C, Glover F, Gamboa D, Osterman C (2006a) A doubly-rooted stem-and-cycle ejection chain algorithm for asymmetric traveling salesman problems. School of Business Administration, University of Mississippi, MS

• Rego C, Li H, Glover F (2006b) A filter-and-fan approach to the 2D HP model of the protein folding problem. School of Business Administration, University of Mississippi, MS

• Rego C, James T, Glover F (2006c) “An ejection chain algorithm for the quadratic assignment problem,” School of Business Ad on, University of Mississippi, MS

• Richards FM (1991) The protein folding problem. Sci Am 264(1):54–7, 60–3

  Google Scholar 

• Rochat Y, Taillard E (1995) Probabilistic intensification and diversification in local search for vehicle routing. J Heuristics. 1:147–167

  Article  Google Scholar 

• Sabuncuoglu I, Bayiz M (1999) Job shop scheduling with beam search. Eur J Operat Res 118: 390–412

  Article  Google Scholar 

• Sharaiha YM, Gendreau M, Laporte G, Osman IH (1997) A tabu search algorithm for the capacitated shortest spanning tree problem. Networks 29:161–171

  Article  Google Scholar 

• Taillard E (1993) Parallel iterative search methods for vehicle routing problems. Networks 23: 661–673

  Google Scholar 

• Yagiura M, Ibaraki T, Glover F (2004) “An ejection chain approach for the generalized assignment problem”. INFORMS J Comput, 16:133–151

  Article  Google Scholar 

Download references