The nonlinear multidimensional knapsack problem is defined as minimizing a convex function with multiple linear constraints. The nonlinear knapsack problem is a class of nonlinear programming, and some methods designed for nonlinear programming can be applied for solving the nonlinear multidimensional knapsack problems. The general nonlinear programming problems have been intensively studied in the last decades, and some different methods have been developed, such as Newton method   , branch and bound method  , interior point method  , sequential quadratic programming method   and the filter method  . These methods are designed for nonlinear programming problems, and some of them are inefficient or limited for solving the nonlinear knapsack problems since they do not consider the characteristics of the knapsack problems.
Generally, it is much faster and more reliable to solve knapsack problems with specialized methods than with standard methods . Many researchers studied the solution methods for the nonlinear knapsack problems based on the specialized knapsack structures. Most of the research studied the problems with single constraint. Two basic specialized methods are mainly applied for solving the single-constraint nonlinear knapsack problem. One is the multiplier search method , and another is the pegging method  . Recently, some new methods are proposed for efficiently solving the single-constraint nonlinear knapsack problem. Zhang and Hua developed a united method for solving a class of continuous separable nonlinear knapsack problems . Kiwiel developed the breakpoint searching method for the continuous quadratic knapsack problem . Sharkey et al. studied a general class of nonlinear non-separable continuous knapsack problem .
Most research of nonlinear knapsack problems studied the one-dimensional problems with continuous or integer variables, and the proposed methods cannot be directly extended for solving multi-dimensional problems. Some researchers attempted to solve multi-dimensional problems with integer-valued variables. Morin and Marsten firstly studied the nonlinear multidimensional knapsack problems and developed the imbedded state space approach . Some researchers investigate the efficiency of other methods, such as smart greedy method , cut method  , branch and bound method  and branch and cut method . Other research studied different applications of multidimensional knapsack, e.g., multi-product newsvendor problems with multiple constraints    . The continuous separable nonlinear multidimensional knapsack problems with general structure have not been well studied due to its complexity, and the specialized methods are very limited.
This paper establishes some structural properties of the continuous separable nonlinear multidimensional knapsack problem, and develops a multi-tier binary solution method for solving a class of 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 application of our method, and the statistical study with the randomly generated instances for different problem sizes are reported to show the effectiveness of our method.
The paper is organized as follows. In Section 2, the nonlinear multidimensional knapsack problem is described. Section 3 studies the structural properties of the problem, and develops the algorithm. Section 4 presents the illustrative examples and the statistical results. Finally, the concluding remarks are given in Section 5. All proofs are listed in Appendix.
2. Problem Formulation
The continuous separable nonlinear multidimensional knapsack problem studied in this paper is as follows (denoted as problem P):
The notation used in this paper is listed in Table 1.
In problem P, all objective functions are convex and differentiable, the unit resource coefficient for all , the resource constraints for all , and the lower and upper bounds satisfy for all .
Since the objective functions and the feasible domain in problem P are all convex, the optimality condition for problem P can be characterized using KKT conditions. Let , , be the Lagrange multiplier vector for the constraints given in Equation (2), and , , , be the Lagrange multiplier vectors for the constraints in Equation (3). Thus, the Lagrange function for problem P can be written as:
Table 1. Notation.
Let , . The KKT conditions for problem P can be summarized as the following proposition.
Proposition 1: The KKT conditions for problem P are:
Since is convex in , is an increasing function of . Let be the point that satisfies if and . If , we let . If , we set . Then is the optimal solution to the objective function in Equation (1) without any constraint. We summarize it as
3. Structural Properties and Solution Method
In this section, we first investigate the structural properties of the optimal solution to problem P. Then we develop a solution method based on the structural properties for solving problem P.
3.1. Structural Properties
We denote by problem PR the knapsack relaxation problem from problem P, in which the constraints in Equation (2) are relaxed. This implies that we do not consider Equation (2) in problem PR. By analyzing the solution to problem PR, we can find the way to construct the solution to problem P. We let ( ) be the optimal solution to problem PR, then ( ) has the following property.
Proposition 2: The optimal solution to problem PR is .
If holds for some , then the corresponding constraints in problem P are inactive, which can be removed from problem P. In the following, without loss of generality, we assume that for all . The KKT conditions in Equation (7) are met at either , or . The condition implies that there is enough resource j at the optimal solution, and hence the j-th constraint is inactive.
means that the j-th constraint is active, and knapsack space of the j-th constraint must be fully utilized at the optimal solution.
We denote by the optimal solution to problem P and the corresponding Lagrange multiplier vector. Let be a solution of the KKT conditions in Equation (5) and Equation (6). We denote by , then we have the following proposition.
Proposition 3. (a) , .
(b) If satisfies or , , then we have .
For any given , we let and be the optimal so-
lution of Equations (5) and (6) and , . For
ease of exposition, we denote problem P as , where is the objective function vector. Problem with , , is an constraint problem with the objective function and the first knapsack constraints of problem P.
By analyzing the structural properties of and , we can prove the following proposition.
Proposition 4. (a) If satisfies or , then we have .
(b) is the optimal solution to problem with , .
From Proposition 4(a), we know that the optimal solution to problem is obtained in two possible cases: 1) , which means
that the constraint is not binding and it can be removed
from problem . Therefore, can be obtained by solving problem , which has the same structure as problem ; 2)
, which implies that is an active constraint, and the optimal solution must be obtained at with .
Since problem can be solved by solving problem in the case of . In the following, we study the case of . Proposition 4(b) indicates that problem determines the optimal values of and , . For any , the resource constraints could be active or inactive, and the N decision variables could take bound values or non-bound values.
If , , constraint j will be active, thus we denote by the active constraint set for the given . Note that includes at least one active constraint for the case of .
From Equation (5), we know if , , and if , . For the given , we define the non-bound variable set , and lower and upper bound variable sets and as
Let , , , and . For the given , without changing the orders of indices j and i, we re-index the constraints in the active constraint set as , and we re-index the variables in the non-bound variable set as , and re-index the variables in and as , and , respectively. As a result, constraint M in the original problem is re-indexed as constraint m, and is also restated as .
We define , , and substitute
into , then we have
Taking the derivative of Equation (12), we get
Since , are differentiable convex, we know is increasing and . Note that has the same structure as . So we define
, and , , then Equation (13) can be rewritten in matrix form:
In order to solve , , from Equation (14), we further define
and denote by , the m-1 dimensional determinant in which the j column of is replaced by . We have the following formula from Equation (14) and Equation (15):
Notice that the above results have similar structures as the results in Zhang . Using the similar way, we can prove that
Since constraint M in the original problem is re-indexed as constraint m, and is also restated as , then is equivalent to in problem P with the original index, thus we know that is a decreasing in .
Therefore, there are three possible cases: 1) When , we get the optimal solution to problem by solving problem ; 2) If and , we obtain the optimal solution to problem by setting ; 3) When and , we can solve problem by studying problem , with .
3.2. Solution Method
According to Proposition 2, we can solve by searching the optimal value of . Before presenting the solution method, we first study the bounds for . The lower bound for is 0, and the upper bound for is given in the following proposition.
Proposition 5. The upper bound of is .
From Proposition 4, we get the optimal value of if the optimal solution to problem satisfies
Since is decreasing in , the optimal solution can be found by applying the binary search over . Since Problem has the same structure as problem , we can use a multi-tier binary search method to solve problem P. Main steps of the multi-tier binary search method are given in Algorithm 1.
Step 1: If , then let , stop;
Step 2: Let , ;
Step 3: Let ;
Step 4: If , then let and , stop;
Step 5: If , then let ;
If , then let
Step 6: If , then let , go to Step 3;
If , then let , go to Step 3;
Step 7: Let and , stop.
In the algorithm, we first solve the unconstrained problem with bounded variables (Step 1) to obtain . If the constraints are active, we apply the binary search procedure (Step 2 - 7) over interval to determine . If either or , the binary search procedure terminates. If is not binding, then the iterating process will end in Step 4 with . Therefore, we can get the optimal solution by solving problem . If the constraint is active, the so-
lution procedure will stop at Step 7 with . Step 5 derives
by solving problem with for the given . If , problem has no knapsack
constraint, and hence we have . If
, we can solve the problem recursively. Problem has the same structure as problem , and hence the algorithm can call itself recursively to solve the problem .
The algorithm is a recursive algorithm with M tiers of binary search loop. The computational complexity of M-tier binary search procedure is , where is the error target for the binary search. The computational complexity of the last recursive step is . Therefore, the proposed algorithm has the computational complexity , which is polynomial in the number of decision variables N.
4. Numerical Study
The solution method developed in this paper can be used for solving the continuous nonlinear multidimensional knapsack problems with general structure, so many application problems with different objective functions summarized in Zhang and Hua with multiple constraints can be used to show the application of our method .
In our numerical study, we first show the application of our method using two examples: quadratic multidimensional knapsack problem (QMK) and the production planning problem presented in Bretthauer and Shetty . Then we use the statistical study to show the efficiency of our method. All computational experiments are conducted on a laptop (dual processor 2.00 GHz, memory 2.96G) with Matlab R2011a.
4.1. The Illustrative Examples
The first illustrative example is a separable quadratic knapsack problem. We set the objective function as , . It has two resource constraints: C1 = 12,000 and C2 = 10,000. Table 2 gives the relevant information for this example. is the optimal solution obtained by applying our algorithm. To show the efficiency of our method, we plot the values of and in the iteration process for solving the example in Figure 1. Figure 1 shows our algorithm can solve the problem within very limited iterations.
In the second example, we solve the production planning problem in Bretthauer and Shetty . The objective function was set as
. There are three resource constraints: C1 = 200, C2 = 300, and C3 = 500. We use the same parameters used in Bretthauer and Shetty . The relevant
Table 2. Parameters and solution for the first example.
Figure 1. in the iteration process for solving the first example.
information for this example is listed in Table 3. is the optimal solution obtained by applying our algorithm.
4.2. The Statistical Results
In this subsection, we present two numerical experiments to show the effectiveness of our method for solving problems with different scale and objective functions. In the first experiment, parameters of the QMK problems are all randomly generated. We use the notation to denote that z is uniformly generated over . The parameters of QMK instances are generated as follows: , , , , and , for .
In this experiment, we set problems with different sizes, respectively with M = 4 and N = 10, M = 2 and N = 100, M = 3 and N = 100, M = 2 and N = 1000. For each problem size, 50 test instances are randomly generated. The statistical results on number of iterations and computation time (in seconds) are reported in Table 4.
In the Second experiment, we solve the production planning problem with randomly generated parameters. The parameters of the instances are generated as follows: , , , , and , for .
In this experiment, we set problems with different sizes, respectively with M = 4 and N = 10, M = 2 and N = 100, M = 3 and N = 100, M = 2 and N = 1000. For each problem size, we randomly generated 50 test instances. The statistical results on number of iterations and computation time (in seconds) are presented in Table 5.
From Table 4 and Table 5, we observe that the standard deviations of number of iterations and computation times are quite low. It implies that our method is quite effective with different objective functions. We also observe that the
Table 3. Parameters and solutions for the second example.
Table 4. Statistical results for randomly generated QMK problems.
Table 5. Statistical results for randomly generated production planning problems.
computation time is more sensitive to the number of the resource constraints rather than the number of variables. Since the application problems often have much more variables than knapsack constraints, our algorithm is useful in practice.
In this paper, we study a class of continuous separable nonlinear multidimensional knapsack problems. By analyzing the structural properties of the optimal solution, we develop a multi-tier binary solution method. The proposed method has following advantages. 1) It is applicable for solving the nonlinear multidimensional knapsack problems with general structure. 2) It has computational complexity of polynomial in the number of variables.
This research can be further extended in several ways. One is to study non-separable multidimensional knapsack problems using the similar idea. Another way is to develop exact solution methods or heuristics for solving the integer multidimensional knapsack problems based on our method. Finally, the idea used in this study can be extended for investigating other complex optimization problems with multiple constraints.
This work is supported by National Natural Science Foundation of China (Grants No. 71672199).
A.1 Proof of Proposition 2
It is defined that for all . The optimal solution to problem PR should satisfy Equation (1) and Equation (3). If , it means that the bound constraint is inactive. Therefore, we have . Since is increasing in , and , we have if . If , then if . Thus for any , we have , and . If , we have . It can be proved similar to the condition of .
A.2 Proof of Proposition 3
1) If , then we have , and , which implies . If , then we have , and hence , .
If , we have , which means , and . Therefore, we have
2) or implies
Because satisfies Equation (5) and Equation (6), will satisfy all KKT conditions. Therefore, if satisfies or , .
A.3 Proof of Proposition 4
1) or implies . Since satisfies Equation (5) and Equation (6), it will satisfy all KKT conditions. Therefore, if satisfies or .
2) KKT conditions for problem are
Notice that is a parameter-adjusted function of , with . These conditions in Equations (A2)-(A3) are the same as KKT conditions given in Equations (5)-(7) without . Since is the optimal solution of the KKT conditions in Equations (5)-(7) without , it must be the optimal solution to problem .
A.4 Proof of Proposition 5
Let . If , then we have . From Equation (5), we have
Since , from Equation (6), we know and . Thus, we have
Equation (A6) violates the slackness condition in Equation (7). Therefore, there must be .