A Hybrid Dynamic Programming Method for Concave Resource Allocation Problems  

作　　者：姜计荣 孙小玲 

机构地区：[1]Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P.R. China [2]Department

出　　处：《Journal of Shanghai University(English Edition)》2005年第2期95-98,共4页上海大学学报（英文版）

基　　金：Project supported by the National Natural Science Foundation oChina (Grant os.79970107 and 10271073)

摘　　要：Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.

关 键 词：nonlinear integer programming resource allocation linear underestimation 0-1linearization dynamic programming. 

分 类 号：TB11[理学—数学]