A Local-Search-Based Heuristic for the Demand-Constrained Multidimensional Knapsack Problem

References

• Aboudi R., Jörnsten K. Tabu search for general zero-one integer programs using the pivot and complement heuristic. ORSA J. Comput. (1994) 6:82–93Link, Google Scholar
• Balas E. An additive algorithm for solving linear programs with 0–1 variables. Oper. Res. (1965) 13:517–546Link, Google Scholar
• Balas E., Martin C. H. Pivot and complement—A heuristic for 0–1 programming. Management Sci. (1980) 26:86–96Link, Google Scholar
• Beasley J.OR Library (1995) . Available from msemga.ms.ic.ac.uk, http://www.ms.ic.ac.uk/info.htmlGoogle Scholar
• Beaujon G. J., Marin S. P., McDonald G. C. Balancing and optimizing a portfolio of R&D projects. Naval Res. Logist. (2001) 48:18–40Crossref, Google Scholar
• Cabot A. V. An enumeration algorithm for knapsack problems. Oper. Res. (1970) 18:306–311Link, Google Scholar
• Cappanera P.Discrete Facility Location and Routing of Obnoxious Activities (1999) . Ph.D. thesis, Department of Mathematics, Università degli Studi di Milano, Milan, Italy. Available at http://www.di.unipi.it/~cappanerGoogle Scholar
• Cappanera P., Gallo G., Maffioli F. Discrete facility location and routing of obnoxious activities. Discrete Appl. Math. (2002) 133:3–28Crossref, Google Scholar
• Chu P. C., Beasley J. E. A genetic algorithm for the multidimensional knapsack problem. J. Heuristics (1998) 4:63–86Crossref, Google Scholar
• Crama Y., Mazzola J. B. On the strength of relaxations of multidimensional knapsack problems. INFOR (1994) 32:219–225Google Scholar
• Dantzig G. B. Discrete variable extremum problems. Oper. Res. (1957) 5:266–277Link, Google Scholar
• Freville A. The multidimensional 0–1 knapsack problem: An overview. Eur. J. Oper. Res. (2004) 155:1–21Crossref, Google Scholar
• Freville A., Plateau G. An efficient preprocessing procedure for the multidimensional 0–1 knapsack problem. Discrete Appl. Math. (1994) 49:189–212Crossref, Google Scholar
• Gavish B., Pirkul H. Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality. Math. Programming (1985) 31:78–105Crossref, Google Scholar
• Gilmore P. C., Gomory R. E. The theory and computation of knapsack functions. Oper. Res. (1966) 14:1045–1074Link, Google Scholar
• Glover F. Surrogate constraint duality in mathematical programming. Oper. Res. (1975) 23:434–453Link, Google Scholar
• Glover F., Kochenberger G. A., Osman I. H., Kelly J. P. Critical event tabu search for multidimensional knapsack problems. Meta Heuristics: Theory and Applications (1996) (Kluwer Academic Publishers, Boston, MA) 407–427Crossref, Google Scholar
• Glover F., Laguna M.Tabu Search (1997) (Kluwer Academic Publishers, Boston, MA) Crossref, Google Scholar
• Hanafi S., Freville A. An efficient tabu search approach for the 0–1 multidimensional knapsack problem. Eur. J. Oper. Res. (1998) 106:659–675Crossref, Google Scholar
• Haul C., Voss S., Woodruff D. L. Using surrogate constraints in genetic algorithms for solving multidimensional knapsack problems. Adv. Comput. Stochastic Optim., Logic Programming, Heuristic Search (1998) (Kluwer Academic Publishers, Boston, MA) 235–251Crossref, Google Scholar
• Korte B., Schnader R., Mangasarian O. L., Meyer R. R., Robinson S. M. On the existence of fast approximation schemes. Nonlinear Programming 4 (1981) (Academic Press, New York) 415–437Crossref, Google Scholar
• Løkketangen A., Glover F. Solving zero-one mixed integer programming problems using tabu search. Eur. J. Oper. Res. (1998) 106:624–658Crossref, Google Scholar
• Magazine M. J., Chern M. S. A note on approximation schemes for multidimensional knapsack problems. Math. Oper. Res. (1984) 9:244–247Link, Google Scholar
• Magazine M. J., Oguz O. A heuristic algorithm for the multidimensional zero-one knapsack problem. Eur. J. Oper. Res. (1984) 16:319–326Crossref, Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (John Wiley and Sons, Chichester, U.K.) Google Scholar
• Martello S., Pisinger D., Toth P. New trends in exact algorithms for the 0–1 knapsack problem. Eur. J. Oper. Res. (2000) 123:325–332Crossref, Google Scholar
• Osorio M. A., Glover F., Hammer P. Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions. X Congreso Latino-Iberoamericano de Investigación de Operaciones y Sistemas, México, D.F., Mexico, September 2000 (2000) . http://optnet.itwm.fhg.de/opt-net/documents/v00w39n1Google Scholar
• Pirkul H. A heuristic solution procedure for the multiconstraint zero-one knapsack problem. Naval Res. Logist. (1987) 34:161–172Crossref, Google Scholar
• Pisinger D. Core problems in knapsack algorithms. Oper. Res. (1999) 47:570–575Link, Google Scholar
• Plastria F. Static competitive facility location: An overview of optimisation approaches. Eur. J. Oper. Res. (2001) 129:461–470Crossref, Google Scholar
• Romero-Morales D., Carrizosa E., Conde E. Semi-obnoxious location models: A global optimization approach. Eur. J. Oper. Res. (1997) 102:295–301Crossref, Google Scholar
• Selman B., Kautz H., Cohen B. Noise strategies for improving local search. Proc. AAAI-94 (1994) 1Seattle, WA:337–343Google Scholar
• Shih W. A branch and bound method for the multiconstraint 0–1 knapsack problem. J. Oper. Res. Soc. (1979) 30:369–378Crossref, Google Scholar
• Voss S., Du D. Z., Pardalos P. M. Tabu search: Applications and prospects. Network Optimization Problems: Algorithms, Applications and Complexity (1993) (World Scientific Publishing Co., Singapore) 333–353Crossref, Google Scholar
• Walser J. P. Integer optimization by local search—A domain-independent approach. Lecture Notes in Artificial Intelligence, LNAI-1637 (1999) (Springer-Verlag, Heidelberg, Germany) . Chapter 3Google Scholar