Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem i...Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.展开更多
This paper aims at providing an uncertain bilevel knapsack problem (UBKP) model, which is a type of BKPs involving uncertain variables. And then an uncertain solution for the UBKP is proposed by defining PE Nash equil...This paper aims at providing an uncertain bilevel knapsack problem (UBKP) model, which is a type of BKPs involving uncertain variables. And then an uncertain solution for the UBKP is proposed by defining PE Nash equilibrium and PE Stackelberg Nash equilibrium. In order to improve the computational efficiency of the uncertain solution, several operators (binary coding distance, inversion operator, explosion operator and binary back learning operator) are applied to the basic fireworks algorithm to design the binary backward fireworks algorithm (BBFWA), which has a good performance in solving the BKP. As an illustration, a case study of the UBKP model and the P-E uncertain solution is applied to an armaments transportation problem.展开更多
Knapsack problem is one kind of NP-Complete problem. Unbounded knapsack problems are more complex and harder than general knapsack problem. In this paper,we apply QGAs (Quantum Genetic Algorithms) to solve unbounded k...Knapsack problem is one kind of NP-Complete problem. Unbounded knapsack problems are more complex and harder than general knapsack problem. In this paper,we apply QGAs (Quantum Genetic Algorithms) to solve unbounded knapsack problem and then follow other procedures. First,present the problem into the mode of QGAs and figure out the corresponding genes types and their fitness functions. Then,find the perfect combination of limitation and largest benefit. Finally,the best solution will be found. Primary experiment indicates that our method has well results.展开更多
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...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.展开更多
This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover i...This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover inequalities are valid. Polynomial time algorithms are created to find merged cover inequalities. A computational study demonstrates that merged inequalities improve the solution times for benchmark multiple knapsack instances by about 9% on average over CPLEX with default settings.展开更多
文摘Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.
基金supported by the National Natural Science Foundation of China(7160118361502522)
文摘This paper aims at providing an uncertain bilevel knapsack problem (UBKP) model, which is a type of BKPs involving uncertain variables. And then an uncertain solution for the UBKP is proposed by defining PE Nash equilibrium and PE Stackelberg Nash equilibrium. In order to improve the computational efficiency of the uncertain solution, several operators (binary coding distance, inversion operator, explosion operator and binary back learning operator) are applied to the basic fireworks algorithm to design the binary backward fireworks algorithm (BBFWA), which has a good performance in solving the BKP. As an illustration, a case study of the UBKP model and the P-E uncertain solution is applied to an armaments transportation problem.
文摘Knapsack problem is one kind of NP-Complete problem. Unbounded knapsack problems are more complex and harder than general knapsack problem. In this paper,we apply QGAs (Quantum Genetic Algorithms) to solve unbounded knapsack problem and then follow other procedures. First,present the problem into the mode of QGAs and figure out the corresponding genes types and their fitness functions. Then,find the perfect combination of limitation and largest benefit. Finally,the best solution will be found. Primary experiment indicates that our method has well results.
文摘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.
文摘This paper describes methods to merge two cover inequalities and also simultaneously merge multiple cover inequalities in a multiple knapsack instance. Theoretical results provide conditions under which merged cover inequalities are valid. Polynomial time algorithms are created to find merged cover inequalities. A computational study demonstrates that merged inequalities improve the solution times for benchmark multiple knapsack instances by about 9% on average over CPLEX with default settings.
