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.
References
[1]
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
[2]
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
[3]
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
[4]
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
[5]
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
[6]
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
[7]
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
[8]
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
[9]
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
[10]
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
[11]
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
[12]
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
[13]
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
[14]
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
[15]
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
[16]
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
[17]
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
[18]
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
[19]
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
[20]
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
[21]
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
[22]
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
[23]
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
[24]
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
[25]
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
[26]
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
[27]
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
