An exact algorithm for the 0–1 linear knapsack problem with a single continuous variable | Journal of Global Optimization Skip to main content
Springer Nature Link
Log in

An exact algorithm for the 0–1 linear knapsack problem with a single continuous variable

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

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 (Martello et al., Manag Sci 45(3):414–424, 1999) to solve KP, and modify the branch and bound method EXPKNAP (Pisinger, Eur J Oper Res 87:175–187, 1995) for KP to solve the PKP. Numerical experiments show the efficiency of our method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Atamtürk A.: On the facets of the mixed-integer knapsack polyhedron. Math. Program. 98, 145–175 (2003)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Google Scholar 

  6. Gorman M.F., Ahire S.: A major appliance manufacturer rethinks its inventory policies for service vehicles. Interfaces 36(5), 407–419 (2006)

    Article  Google Scholar 

  7. Hoare C.A.R.: Quicksort. Comput. J. 5(1), 10–15 (1962)

    Article  Google Scholar 

  8. Kellerer H., Pferschy U., Pisinger D.: Knapsack Problems. Springer, Berlin (2004)

    Google Scholar 

  9. Letchford A.N., Lodi A.: Strengthening Chvátal-Gomory cuts and gomory fractional cuts. Oper. Res. Lett. 30(2), 74–82 (2002)

    Article  Google Scholar 

  10. Marchand H., Wolsey L.A.: The 0–1 knapsack problem with a single continuous variable. Math. Program. 85, 15–33 (1999)

    Article  Google Scholar 

  11. Marchand H., Wolsey L.A.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49, 363–371 (2001)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  14. Papadimitriou C.H.: On the complexity of integer programming. J. ACM 28, 765–768 (1981)

    Article  Google Scholar 

  15. Pisinger D.: An expanding-core algorithm for the exact 0–1 Knapsack Problem. Eur. J. Oper. Res. 87, 175–187 (1995)

    Article  Google Scholar 

Download references

Author information

Author notes

  1. Geng Lin

    Present address: Department of Mathematics, Minjiang University, Fuzhou, 350108, China

Authors and Affiliations

  1. Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou, 350108, China

    Geng Lin & Wenxing Zhu

  2. School of Computational and Applied Mathematics, University of the Witwatersrand, Wits 2050, Johannesburg, South Africa

    M. M. Ali

Authors
  1. Geng Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wenxing Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. M. Ali
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wenxing Zhu.

Additional information

Research supported in part by the National Natural Science Foundation of China under Grants 60773126 and 61070020, in part by the National Key Basic Research Science Foundation (NKBRSF) of China under Grant 2011CB808000, and in part by the Research Fund for the Doctoral Program (RFDP) of China under Grant 20093514110004.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lin, G., Zhu, W. & Ali, M.M. An exact algorithm for the 0–1 linear knapsack problem with a single continuous variable. J Glob Optim 50, 657–673 (2011). https://doi.org/10.1007/s10898-010-9642-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-010-9642-5

Keywords

Search

Navigation