An Exact Algorithm for the Two-Constraint 0–1 Knapsack Problem

References

• Bagchi A., Bhattacharyya N., Chakravarti N. LP relaxation of the two dimensional knapsack problem with box and GUB constraints. Eur. J. Oper. Res. (1996) 89:609–617Crossref, Google Scholar
• Balas E., Zemel E. An algorithm for large zero-one knapsack problems. Oper. Res. (1980) 28:1130–1154Link, Google Scholar
• Campello R., Maculan N. An O(n3) worst case bounded special LP knapsack (0–1) with two constraints. RAIRO Recherche Opérationnelle (1988) 22:27–32Crossref, Google Scholar
• Chu P. C., Beasley J. E. A genetic algorithm for the multidimensional knapsack problem. J. Heuristics (1998) 4:63–86Crossref, Google Scholar
• Dantzig G. B. Discrete variable extremum problems. Oper. Res. (1957) 5:266–277Link, Google Scholar
• Escudero L. F., Martello S., Toth P., Mitra G., Maros I., Sciomachen A. On tightening 0–1 programs based on extensions of pure 0–1 knapsack and subset-sum problems. Applied Mathematical Programming and Modeling III, Annals of Operational Research (1998) 81(J. C. Baltzer AG, Basel, Switzerland) 379–404Google Scholar
• Fréville A., Plateau G. An exact search for the solution of the surrogate dual of the 0–1 bidimensional knapsack problem. Eur. J. Oper. Res. (1993) 68:413–421Crossref, Google Scholar
• Fréville A., Plateau G. The 0–1 bidimensional knapsack problem: Toward an efficient high-level primitive tool. J. Heuristics (1996) 2:147–167Crossref, 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
• Glover F. Surrogate constraint duality in mathematical programming. Oper. Res. (1975) 23:434–453Link, Google Scholar
• Martello S., Toth P. A new algorithm for the 0–1 knapsack problem. Management Sci. (1988) 34:633–644Link, Google Scholar
• Martello S., Toth P.Knapsack Problems: Algorithms and Computer Implementations (1990) (Wiley, Chichester, U.K) Google Scholar
• Martello S., Toth P. Upper bounds and algorithms for hard 0–1 knapsack problems. Oper. Res. (1997) 45:768–778Link, Google Scholar
• Martello S., Pisinger D., Toth P. Dynamic programming and strong bounds for the 0–1 knapsack problem. Management Sci. (1999) 45:414–424Link, Google Scholar
• Megiddo N., Tamir A. Linear time algorithms for some separable quadratic programming problems. Oper. Res. Lett. (1993) 13:203–211Crossref, Google Scholar
• Pisinger D., Toth P., Du D.-Z., Pardalos P. M. Knapsack problems. Handbook of Combinatorial Optimization (1999) 1(Kluwer Academic Publishers, Boston, MA) Google Scholar
• Weingartner H. M., Ness D. N. Methods for the solution of the multidimensional 0/1 knapsack problem. Oper. Res. (1967) 15:83–103Link, Google Scholar