凹整数规划的分枝定界解法(英文)  

Computational Study of Branch-and-Bound Method for Concave Integer Programming

作　　者：钟培华[1] 孙小玲[1] 

机构地区：[1]上海大学数学系

出　　处：《运筹学学报》2005年第1期13-20,共8页Operations Research Transactions

基　　金：Research supported by and the National Natural Science Foundation of China under Grants 79970107 and 10271073.

摘　　要：凹整数规划是一类重要的非线性整数规划问题,也是在经济和管理中有着广泛应用的最优化问题.本文主要研究用分枝定界方法求解凹整数规划问题,这一方法的基本思想是对目标函数进行线性下逼近,然后用乘子搜索法求解连续松弛问题.数值结果表明,用这种分枝定界方法求解凹整数规划是有效的.Concave integer programming is an important class of nonlinear integer programming problems with applications in optimization models involving economies of scale. In this paper, we investigate branch-and-bound method for solving concave integer programming problems. The method is based on the linear underestimation of the objective function and continuous relaxation. The continuous subproblem at each node is solved by a special Lagrangian multiplier search procedure. Extensive computational experiment shows that the branch-and-bound method is efficient in solving concave integer programming problems.

关 键 词：分枝定界方法 求解 非线性整数规划 乘子 最优化问题 连续 逼近 经济 基本思想 管理 

分 类 号：O221[理学—运筹学与控制论] O224[理学—数学]