An Ejection Chain Approach for the Generalized Assignment Problem

References

• Amini M. M., Racer M. A hybrid heuristic for the generalized assignment problem. Eur. J. Oper. Res. (1995) 87:343–348Crossref, Google Scholar
• Berge C.The Theory of Graphs and Its Applications (1962) . Methuen, London, and Wiley, New York. (Translated by A. Doig.)Google Scholar
• Bertsekas D. P.Nonlinear Programming (1995) . Athena Scientific, Belmont, MAGoogle Scholar
• Cattrysse D. G., Salomon M., Van Wassenhove L. N. A set partitioning heuristic for the generalized assignment problem. Eur. J. Oper. Res. (1994) 72:167–174Crossref, Google Scholar
• Chu P. C., Beasley J. E. A genetic algorithm for the generalized assignment problem. Comput. Oper. Res. (1997) 24:17–23Crossref, Google Scholar
• Dongarra J. J. Performance of various computers using standard linear equations software. (1999) . Technical report. Computer Science Department, University of Tennessee, Knoxville, TN 37996-1301, and Mathematical Sciences Section, Oak Ridge National Laboratory, Oak Ridge, TN 37831, http://www.netlib.org/benchmark/performance.psGoogle Scholar
• Edmonds J. Maximum matching and a polyhedron with 0, 1-vertices. J. Res. National Bureau of Standards (1965) 69B:125–130Crossref, Google Scholar
• Fisher M. L. The Lagrangian relaxation method for solving integer programming problems. Management Sci. (1981) 27:1–18Link, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Company, New York) Google Scholar
• Glover F. Tabu search–A tutorial. Interfaces (1990) 20(1):74–94Link, Google Scholar
• Glover F. Ejection chain moves for generalized assignment problems. (1997) . Manuscript. Leeds School of Business, University of Colorado, Boulder, COGoogle Scholar
• Held M., Karp R. M. The traveling salesman problem and minimum spanning trees: Part II. Math. Programming (1971) 1:6–25Crossref, Google Scholar
• Johnson D. S., Paterson M. S. Local optimization and the traveling salesman problem. Automata, Languages and Programming, Lecture Notes in Computer Science (1990) (Springer-Verlag, Berlin) 446–461No.443Crossref, Google Scholar
• Kernighan B. W., Lin S. An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. (1970) 49:291–307Crossref, Google Scholar
• Laguna M., Kelly J. P., González-Velarde J. L., Glover F. Tabu search for the multilevel generalized assignment problem. Eur. J. Oper. Res. (1995) 82:176–189Crossref, Google Scholar
• Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling salesman problem. Oper. Res. (1973) 21:498–516Link, Google Scholar
• Lorena L. A. N., Narciso M. G. Relaxation heuristics for a generalized assignment problem. Eur. J. Oper. Res. (1996) 91:600–610Crossref, Google Scholar
• Lourenço H. R., Serra D. Adaptive search heuristics for the generalized assignment problem. Mathware Soft Comput. (2002) 9:209–234Google Scholar
• Lourenço H. R., Zwijnenburg M., Osman I. H., Kelly J. P. Combining the large-step optimization with tabu-search: Application to the job-shop scheduling problem. Meta-Heuristics: Theory & Applications (1996) (Kluwer Academic Publishers, Boston, MA) 661–675Crossref, Google Scholar
• Martello S., Toth P. An algorithm for the generalized assignment problem. Proc. Ninth IFORS Internat. Conf. on Operational Res. (1981) Hamburg, Germany, July 1981. North-Holland, Amsterdam, The Netherlands:589–603Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (John Wiley & Sons, Chichester, U.K.) Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the traveling salesman problem. Complex Systems (1991) 5:299–326Google Scholar
• Martin O., Otto S. W., Felten E. W. Large-step Markov chains for the TSP incorporating local search heuristic. Oper. Res. Lett. (1992) 11:219–224Crossref, Google Scholar
• Nauss R. M. Solving the generalized assignment problem: An optimizing and heuristic approach. INFORMS J. Comput. (2003) 15(3):249–266Link, Google Scholar
• Nonobe K., Ibaraki T. A tabu search approach to the CSP (constraint satisfaction problem) as a general problem solver. Eur. J. Oper. Res. (1998) 106:599–623Crossref, Google Scholar
• Osman I. H. Heuristics for the generalized assignment problem: Simulated annealing and tabu search approaches. OR Spektrum (1995) 17:211–225Crossref, Google Scholar
• Pesch E., Glover F. TSP ejection chains. Discrete Appl. Math. (1997) 76:165–181Crossref, Google Scholar
• Racer M., Amini M. M. A robust heuristic for the generalized assignment problem. Ann. Oper. Res. (1994) 50:487–503Crossref, Google Scholar
• Rego C. Relaxed tours and path ejections for the traveling salesman problem. Eur. J. Oper. Res. (1998a) 106:522–538Crossref, Google Scholar
• Rego C. A subpath ejection chain method for the vehicle routing problem. Management Sci. (1998b) 44:1447–1459Link, Google Scholar
• Rego C., Roucairol C., Osman I. H., Kelly J. P. A parallel tabu search algorithm using ejection chains for the vehicle routing problem. Meta-Heuristics: Theory & Applications (1996) (Kluwer Academic Publishers, Boston, MA) 661–675Crossref, Google Scholar
• Sahni S., Gonzalez T. P-complete approximation problems. J. Association Comput. Machinery (1976) 23:555–565Crossref, Google Scholar
• Savelsbergh M. A branch-and-price algorithm for the generalized assignment problem. Oper. Res. (1997) 45:831–841Link, Google Scholar
• Trick M. A. A linear relaxation heuristic for the generalized assignment problem. Naval Res. Logist. (1992) 39:137–151Crossref, Google Scholar
• Yagiura M., Yamaguchi T., Ibaraki T. A variable depth search algorithm with branching search for the generalized assignment problem. Optim. Methods Software (1998) 10:419–441Crossref, Google Scholar
• Yagiura M., Yamaguchi T., Ibaraki T., Voß S., Martello S., Osman I. H., Roucairol C. A variable depth search algorithm for the generalized assignment problem. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization (1999) (Kluwer Academic Publishers, Boston, MA) 459–471Crossref, Google Scholar