The nonlinear multidimensional knapsack problem is defined as the minimization of a convex function with multiple linear constraints. The methods developed for nonlinear multidimensional programming problems are often applied to solve the nonlinear multidimensional knapsack problems, but they are inefficient or limited since most of them do not exploit the characteristics of the knapsack problems. In this paper, by establishing structural properties of the continuous separable nonlinear multidimensional knapsack problem, we develop a multi-tier binary solution method for solving the continuous nonlinear multidimensional knapsack problems with general structure. The computational complexity is polynomial in the number of variables. We presented two examples to illustrate the general application of our method and we used statistical results to show the effectiveness of our method.
Bonnans, J.F. (1994) Local Analysis of Newton-Type Methods for Variational Inequalities and Nonlinear Programming. Applied Mathematics and Optimization, 29, 161-186. https://doi.org/10.1007/BF01204181
Coleman, T.F. and Li, Y. (1994) On the Convergence of Interior-Reflective Newton Methods for Nonlinear Minimization Subject to Bounds. Mathematical Programming, 67, 189-224. https://doi.org/10.1007/BF01582221
Van Hentenryck, P., Michel, L. and Benhamou, F. (1998) Constraint Programming over Nonlinear Constraints. Science of Computer Programming, 30, 83-118. https://doi.org/10.1016/S0167-6423(97)00008-7
Borchers, B. and Mitchell, J.E. (1994) An Improved Branch and Bound Algorithm for Mixed Integer Nonlinear Programs. Computers & Operations Research, 21, 359-367. https://doi.org/10.1016/0305-0548(94)90024-8
Leyffer, S. (2001) Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming. Computational Optimization and Applications, 18, 295-309. https://doi.org/10.1023/A:1011241421041
Byrd, R.H., Hribar, M.E. and Nocedal, J. (1999) An Interior Point Algorithm for Large-Scale Nonlinear Programming. SIAM Journal on Optimization, 9, 877-900. https://doi.org/10.1137/S1052623497325107
Benson, H.Y., Vanderbei, R.J. and Shanno, D.F. (2002) Interior-Point Methods for Nonconvex Nonlinear Programming: Filter Methods and Merit Functions. Computational Optimization and Applications, 23, 257-272. https://doi.org/10.1023/A:1020533003783
Spellucci, P. (1998) An SQP Method for General Nonlinear Programs Using only Equality Constrained Subproblems. Mathematical Programming, 82, 413-448. https://doi.org/10.1007/BF01580078
Zhu, Z. and Zhang, K. (2004) A New SQP Method of Feasible Directions for Nonlinear Programming. Applied Mathematics and Computation, 148, 121-134. https://doi.org/10.1016/S0096-3003(02)00832-9
Nie, P.Y. and Ma, C.F. (2006) A Trust Region Filter Method for General Non-Linear Programming. Applied Mathematics and Computation, 172, 1000-1017. https://doi.org/10.1016/j.amc.2005.03.004
Nie, P.Y. (2007) Sequential Penalty Quadratic Programming Filter Methods for Nonlinear Programming. Nonlinear Analysis: Real World Applications, 8, 118-129. https://doi.org/10.1016/j.nonrwa.2005.06.003
Bretthauer, K.M. and Shetty, B. (2002b) The Nonlinear Knapsack Problem-Algo- rithms and Applications. European Journal of Operational Research, 138, 459-472. https://doi.org/10.1016/S0377-2217(01)00179-5
Bretthauer, K.M. and Shetty, B. (1995) The Nonlinear Resource Allocation Problem. Operations Research, 43, 670-683. https://doi.org/10.1287/opre.43.4.670
Kodialam, M.S. and Luss, H. (1998) Algorithms for Separable Nonlinear Resource Allocation Problems. Operations Research, 46, 272-284. https://doi.org/10.1287/opre.46.2.272
Bretthauer, K.M. and Shetty, B. (2002a) A Pegging Algorithm for the Nonlinear Resource Allocation Problem. Computers & Operations Research, 29, 505-527. https://doi.org/10.1016/S0305-0548(00)00089-7
Zhang, B. and Hua, Z. (2008) A Unified Method for a Class of Convex Separable Nonlinear Knapsack Problems. European Journal of Operational Research, 191, 1-6. https://doi.org/10.1016/j.ejor.2007.07.005
Kiwiel, K.C. (2008) Breakpoint Searching Algorithms for the Continuous Quadratic Knapsack Problem. Mathematical Programming, 112, 473-491. https://doi.org/10.1007/s10107-006-0050-z
Sharkey, T.C., Romeijn, H.E. and Geunes, J. (2011) A Class of Nonlinear Nonseparable Continuous Knapsack and Multiple-Choice Knapsack Problems. Mathematical Programming, 126, 69-96. https://doi.org/10.1007/s10107-009-0274-9
Morin, T.L. and Marsten, R.E. (1976) An Algorithm for Nonlinear Knapsack Problems. Management Science, 22, 1147-1158. https://doi.org/10.1287/mnsc.22.10.1147
Ohtagaki, H., Iwasaki, A., Nakagawa, Y. and Narihisa, H. (2000) Smart Greedy Procedure for Solving a Multidimensional Nonlinear Knapsack Class of Reliability Optimization Problems. Mathematical and Computer Modelling, 31, 283-288. https://doi.org/10.1016/S0895-7177(00)00097-2
Li, D., Sun, X.L. and Wang, F.L. (2006) Convergent Lagrangian and Contour Cut Method for Nonlinear Integer Programming with a Quadratic Objective Function. SIAM Journal on Optimization, 17, 372-400. https://doi.org/10.1137/040606193
Li, D., Sun, X.L., Wang, J. and McKinnon, K.I. (2009) Convergent Lagrangian and Domain Cut Method for Nonlinear Knapsack Problems. Computational Optimization and Applications, 42, 67-104. https://doi.org/10.1007/s10589-007-9113-1
Quadri, D., Soutif, E. and Tolla, P. (2009) Exact Solution Method to Solve Large Scale Integer Quadratic Multidimensional Knapsack Problems. Journal of Combinatorial Optimization, 17, 157-167. https://doi.org/10.1007/s10878-007-9105-1
Wang, H., Kochenberger, G. and Glover, F. (2012) A Computational Study on the Quadratic Knapsack Problem with Multiple Constraints. Computers & Operations Research, 39, 3-11. https://doi.org/10.1016/j.cor.2010.12.017
Abdel-Malek, L.L. and Areeratchakul, N. (2007) A Quadratic Programming Approach to the Multi-Product Newsvendor Problem with Side Constraints. European Journal of Operational Research, 176, 1607-1619. https://doi.org/10.1016/j.ejor.2005.11.002
Abdel-Malek, L.L. and Otegbeye, M. (2013) Separable Programming/Duality Approach to Solving the Multi Constrained Newsboy/Gardener Problem. Applied Mathematical Modelling, 37, 4497-4508. https://doi.org/10.1016/j.apm.2012.09.059
Zhang, B. (2012) Multi-Tier Binary Solution Method for Multi-Product Newsvendor Problem with Multiple Constraints. European Journal of Operational Research, 218, 426-434. https://doi.org/10.1016/j.ejor.2011.10.053