×

zbMATH — the first resource for mathematics

An exact algorithm for the 0-1 linear knapsack problem with a single continuous variable. (English) Zbl 1229.90167
Summary: The 0-1 linear knapsack problem with a single continuous variable (KPC) is an extension of the binary knapsack problem (KP). It is an NP-hard problem. In this paper, we show that KPC can be reduced to KP and a pseudo-knapsack problem (PKP), which is similar to the traditional knapsack problem except that the profits of items may be non-positive, and the weight sum has two sided limits on capacity. We use the dynamic programming algorithm COMBO [S. Martello, D. Pisinger and P. Toth, “Dynamic programming and strong bounds for the 0-1 knapsack problem”, Manag. Sci. 45, No. 3, 414–424 (1999)] to solve KP, and modify the branch and bound method EXPKNAP [D. Pisinger, Eur. J. Oper. Res. 87, No. 1, 175–187 (1995; Zbl 0914.90199)] for KP to solve the PKP. Numerical experiments show the efficiency of our method.

MSC:
90C27 Combinatorial optimization
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Atamtürk A.: On the facets of the mixed-integer knapsack polyhedron. Math. Program. 98, 145–175 (2003) · Zbl 1082.90073 · doi:10.1007/s10107-003-0400-z
[2] Balas E., Ceria S., Comuéjols G.: A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58, 295–324 (1993) · Zbl 0796.90041 · doi:10.1007/BF01581273
[3] Balas E., Ceria S., Comuéjols G.: Mixed 0–1 programming by lift-and-project in a branch-and-cut framework. Manag. Sci. 42, 1229–1246 (1996) · Zbl 0880.90105 · doi:10.1287/mnsc.42.9.1229
[4] Buther, M., Briskorn, D.: Reducing the 0–1 knapsack problem with a single continuous variable to the standard 0–1 knapsack problem. Manuskripte aus den Instituten fur Betriebswirtschaftslehre der Universitat Kiel 629 (2007)
[5] Garey M.R., Johnson D.S.: Computers and Intractability–A Guide to the Theory of NP-completeness. Freeman W.H. and Company, San Francisco (1979) · Zbl 0411.68039
[6] Gorman M.F., Ahire S.: A major appliance manufacturer rethinks its inventory policies for service vehicles. Interfaces 36(5), 407–419 (2006) · doi:10.1287/inte.1060.0232
[7] Hoare C.A.R.: Quicksort. Comput. J. 5(1), 10–15 (1962) · Zbl 0108.13601 · doi:10.1093/comjnl/5.1.10
[8] Kellerer H., Pferschy U., Pisinger D.: Knapsack Problems. Springer, Berlin (2004) · Zbl 1103.90003
[9] Letchford A.N., Lodi A.: Strengthening Chvátal-Gomory cuts and gomory fractional cuts. Oper. Res. Lett. 30(2), 74–82 (2002) · Zbl 1027.90062 · doi:10.1016/S0167-6377(02)00112-8
[10] Marchand H., Wolsey L.A.: The 0–1 knapsack problem with a single continuous variable. Math. Program. 85, 15–33 (1999) · Zbl 0956.90021 · doi:10.1007/s101070050044
[11] Marchand H., Wolsey L.A.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 363–371 (2001) · Zbl 1163.90671 · doi:10.1287/opre.49.3.363.11211
[12] Martello S., Pisinger D., Toth P.: Dynamic programming and strong bounds for the 0–1 knapsack problem. Manag. Sci. 45(3), 414–424 (1999) · Zbl 1231.90338 · doi:10.1287/mnsc.45.3.414
[13] Martello S., Pisinger D., Toth P.: New trends in exact algorithms for the 0–1 knapsack problem. Eur. J. Oper. Res. 123, 325–332 (2000) · Zbl 0961.90090 · doi:10.1016/S0377-2217(99)00260-X
[14] Papadimitriou C.H.: On the complexity of integer programming. J. ACM 28, 765–768 (1981) · Zbl 0468.68050 · doi:10.1145/322276.322287
[15] Pisinger D.: An expanding-core algorithm for the exact 0–1 Knapsack Problem. Eur. J. Oper. Res. 87, 175–187 (1995) · Zbl 0914.90199 · doi:10.1016/0377-2217(94)00013-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.