 |
||||||||
| Volume 4, Number 1, January 2008, pp. 63-73 | ||||||||
| Xiaoling Sun, Shanshan Kong and Duan Li | ||||||||
| Key words: | ||||||||
| nonlinear knapsack problem, surrogate dual, Lagrangian dual, branch-and-bound method | ||||||||
| Mathematices Subject Classification: 90C10, 90C46 | ||||||||
|
||||||||
| Volume 4, Number 1, January 2008, pp. 63-73 | ||||||||
| Xiaoling Sun, Shanshan Kong and Duan Li | ||||||||
| Key words: | ||||||||
| nonlinear knapsack problem, surrogate dual, Lagrangian dual, branch-and-bound method | ||||||||
| Mathematices Subject Classification: 90C10, 90C46 | ||||||||
|
||||||||||||||||||||||||||||||||||||||||
| Abstract: | |||
| Multi-dimensional nonlinear knapsack problems are often encountered in real-world applications such as in resource allocation, industrial planning and reliability networks. In this paper, we propose a new exact method for solving this class of problems . The method is based on surrogate dual search and domain cut technique. The optimal surrogate multipliers are computed by the cutting plane method, where the surrogate relaxation problem is solved by the 0-1 linearization method in convex cases. Numerical results are reported for medium-size multi-dimensional nonlinear convex knapsack problems. | |||
| Computational study of surrogate dual method for multi-dimensional nonlinear knapsack problems | ||