Skip to main content
SpringerLink
Log in

Convergent Lagrangian and domain cut method for nonlinear knapsack problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

The nonlinear knapsack problem, which has been widely studied in the OR literature, is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to separable nondecreasing constraints. In this paper we develop a convergent Lagrangian and domain cut method for solving this kind of problems. The proposed method exploits the special structure of the problem by Lagrangian decomposition and dual search. The domain cut is used to eliminate the duality gap and thus to guarantee the finding of an optimal exact solution to the primal problem. The algorithm is first motivated and developed for singly constrained nonlinear knapsack problems and is then extended to multiply constrained nonlinear knapsack problems. Computational results are presented for a variety of medium- or large-size nonlinear knapsack problems. Comparison results with other existing methods are also reported.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bell, D.E., Shapiro, J.F.: A convergent duality theory for integer programming. Oper. Res. 25, 419–434 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  2. Bretthauer, K.M., Shetty, B.: The nonlinear resource allocation problem. Oper. Res. 43, 670–683 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bretthauer, K.M., Shetty, B.: A pegging algorithm for the nonlinear resource allocation problem. Comput. Oper. Res. 29, 505–527 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  4. Cochran, W.G.: Sampling Techniques. Wiley, New York (1963)

    Google Scholar 

  5. Cooper, M.W.: The use of dynamic programming for the solution of a class of nonlinear programming problems. Nav. Res. Logist. Q. 27, 89–95 (1980)

    Article  MATH  Google Scholar 

  6. Cooper, M.W.: Survey of methods of pure nonlinear integer programming. Manag. Sci. 27, 353–361 (1981)

    Article  MATH  Google Scholar 

  7. Djerdjour, M., Mathur, K., Salkin, H.M.: A surrogate relaxation based on algorithm for a general class quadratic multi-dimensional knapsack problem. Oper. Res. Lett. 7, 253–258 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  8. Dyer, M.E., Walker, J.: Solving the subproblem in the Lagrangian dual of separable discrete programs with linear constraints. Math. Program. 24, 107–112 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  9. Fisher, M.L.: The Lagrangian relaxation method for solving integer programming problems. Manag. Sci. 27, 1–18 (1981)

    Article  MATH  Google Scholar 

  10. Fisher, M.L., Shapiro, J.F.: Constructive duality in integer programming. SIAM J. Appl. Math. 27, 31–52 (1974)

    Article  MATH  MathSciNet  Google Scholar 

  11. Geoffrion, A.M.: Lagrangean relaxation for integer programming. Math. Program. Study 2, 82–114 (1974)

    MathSciNet  Google Scholar 

  12. Grossmann, I.E., Kravanja, Z.: Mixed-integer nonlinear programming: a survey of algorithms and applications. In: Conn, A.R., Coleman, T.F., Biegler, L.T., Santosa, F.N. (eds.) Large-Scale Optimization with Applications, Part II: Optimization Design and Control. Springer, New York (1997)

    Google Scholar 

  13. Gupta, O.K., Ravindran, A.: Branch and bound experiments in convex nonlinear integer programming. Manag. Sci. 31, 1533–1546 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  14. Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, vols. 1 and 2. Springer, Berlin (1993)

    Google Scholar 

  15. Hochbaum, D.S.: A nonlinear knapsack problem. Oper. Res. Lett. 17, 103–110 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  16. Hochbaum, D.S., Shanthikumar, J.G.: Convex separable optimization is not much harder than linear optimization. J. Assoc. Comput. Mach. 37, 843–862 (1990)

    MATH  MathSciNet  Google Scholar 

  17. Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Heidelberg (1993)

    Google Scholar 

  18. Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge (1988)

    MATH  Google Scholar 

  19. Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization. Springer, Berlin (1985)

    MATH  Google Scholar 

  20. Kodialam, M.S., Luss, H.: Algorithm for separable nonlinear resource allocation problems. Oper. Res. 46, 272–284 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  21. Korner, F.: A hybrid method for solving nonlinear knapsack problems. Eur. J. Oper. Res. 38, 238–241 (1989)

    Article  MathSciNet  Google Scholar 

  22. Lemaréchal, C., Renaud, A.: A geometric study of duality gaps, with applications. Math. Program. 90, 399–427 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  23. Li, D., Sun, X.L.: Success guarantee of dual search in nonlinear integer programming: P-th power Lagrangian method. J. Glob. Optim. 18, 235–254 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  24. Li, D., Sun, X.L.: Nonlinear Integer Programming. Springer, New York (2006)

    MATH  Google Scholar 

  25. Li, D., White, D.J.: P-th power Lagrangian method for integer programming. Ann. Oper. Res. 98, 151–170 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  26. Marsten, R.E., Morin, T.L.: A hybrid approach to discrete mathematical programming. Math. Program. 14, 21–40 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  27. Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990)

    MATH  Google Scholar 

  28. Mathur, K., Salkin, H.M., Mohanty, B.B.: A note on a general non-linear knapsack problems. Oper. Res. Lett. 5, 79–81 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  29. Mathur, K., Salkin, H.M., Morito, S.: A branch and search algorithm for a class of nonlinear knapsack problems. Oper. Res. Lett. 2, 55–60 (1983)

    Article  MathSciNet  Google Scholar 

  30. Melman, A., Rabinowitz, G.: An efficient method for a class of continuous nonlinear knapsack problems. SIAM Rev. 42, 440–448 (1991)

    Article  MathSciNet  Google Scholar 

  31. Michelon, P., Maculan, N.: Lagrangian decomposition for integer nonlinear programming with linear constraints. Math. Program. 52, 303–313 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  32. Minoux, M., Tuy, H.: Discrete monotonic global optimization. Technical report. http://www.mat.univie.ac.at/~neum/glopt/mss/MinT02.pdf (2002)

  33. Neame, P., Boland, N., Ralph, D.: An outer approximation subdifferential method for piecewise affine optimization. Math. Program. 87, 57–86 (2000)

    MATH  MathSciNet  Google Scholar 

  34. Parker, R.G., Rardin, R.L.: Discrete Optimization. Academic Press, Boston (1988)

    MATH  Google Scholar 

  35. Shapiro, J.F.: A survey of Lagrangian techniques for discrete optimization. Ann. Discrete Math. 5, 113–138 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  36. Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic, Dordrecht (1999)

    MATH  Google Scholar 

  37. Shor, N.Z.: Minimization Methods for Non-Differentiable Functions. Springer, Berlin (1985)

    MATH  Google Scholar 

  38. Sun, X.L., Li, D.: Asymptotic strong duality for bounded integer programming: a logarithmic-exponential dual formulation. Math. Oper. Res. 25, 625–644 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  39. Sun, X.L., Li, D.: Optimality condition and branch and bound algorithm for constrained redundancy optimization in series systems. Optim. Eng. 3, 53–65 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  40. Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic, Dordrecht (2002)

    MATH  Google Scholar 

  41. Tillman, F.A., Hwuang, C.L., Kuo, W.: Optimization of System Reliability. Dekker, New York (1980)

    Google Scholar 

  42. Tuy, H.: Monotonic optimization: problems and solution approaches. SIAM J. Optim. 11, 464–494 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  43. Tzafestas, S.G.: Optimization of system reliability: a survey of problems and techniques. Int. J. Syst. Sci. 11, 455–486 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  44. Vidal, R.V.V.: A simple method to solve some simple allocation problems. IIE Trans. 19, 234–237 (1987)

    Article  Google Scholar 

  45. Zhao, X., Luh, P.B.: New boundle methods for solving Lagrangian relaxation dual problems. J. Optim. Theory Appl. 113, 373–397 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  46. Ziegler, H.: Solving certain singly constrained convex optimization problems in production planning. Oper. Res. Lett. 1, 246–252 (1982)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, NT, Hong Kong

    D. Li

  2. Department of Management Science, School of Management, Fudan University, Shanghai, 200433, China

    X. L. Sun

  3. Department of Management Science and Engineering, International Business College, Qingdao University, Qingdao, 266071, China

    J. Wang

  4. School of Mathematics, The University of Edinburgh, Edinburgh, EH9 3JZ, UK

    K. I. M. McKinnon

Authors
  1. D. Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. X. L. Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. J. Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. K. I. M. McKinnon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to D. Li.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Li, D., Sun, X.L., Wang, J. et al. Convergent Lagrangian and domain cut method for nonlinear knapsack problems. Comput Optim Appl 42, 67–104 (2009). https://doi.org/10.1007/s10589-007-9113-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-007-9113-1

Keywords

Search

Navigation