Exact Algorithm for Concave Knapsack Problems: Linear Underestimation and Partition Method |
| |
Authors: | X?L?Sun F?L?Wang Email author" target="_blank">D?LiEmail author |
| |
Institution: | (1) Department of Mathematics, Shanghai University, 99 Shangda Road, Baoshan, Shanghai, 200444, P. R. China;(2) Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N. T, Hong Kong |
| |
Abstract: | Integer programming problems with a concave cost function are often encountered in optimization models involving economics
of scale. In this paper, we propose an efficient exact algorithm for solving concave knapsack problems. The algorithm consists
of an iterative process between finding lower and upper bounds by linearly underestimating the objective function and performing
domain cut and partition by exploring the special structure of the problem. The lower bound is improved iteratively via cutting
and partitioning the domain. This iteration process converges to the optimality in a finite number of steps. Promising computational
results are reported for large-scale concave knapsack problems with up to 1200 integer variables. Comparison results with
other existing methods in the literature are also presented.
*Research supported by the National Natural Science Foundation of China under Grants 79970107 and 10271073,and the Research
Grants Council of Hong Kong under Grant CUHK 4214/01E. |
| |
Keywords: | concave knapsack problem domain cut domain partition linear underestimation nonlinear integer programming |
本文献已被 SpringerLink 等数据库收录! |
|