整数可分离凹规划问题的一个线性规划松弛定界算法  

A Linear Programming Relaxed Bound Algorithm for Solving Integer Separable Concave Programming Problems

作　　者：任子晖[1] 高岳林[2] 

机构地区：[1]宁夏大学数学与计算机学院,宁夏银川750021 [2]西北第二民族学院信息与计算科学系,宁夏银川750021

出　　处：《宁夏师范学院学报》2007年第3期18-22,共5页Journal of Ningxia Normal University

基　　金：宁夏自然科学基金(No.NZ0676);宁夏高等学校科研项目(2005).

摘　　要：给出了整数可分离凹规划问题的一个线性规划松弛定界算法,该算法中的分枝过程是简单的整矩形二剖分过程,定上界是简单的启发式方法,而定下界过程需要解一个线性规划松弛问题来确定的,数值实验表明所提出的算法是有效的,它可以求解中等规模的问题.In the paper, we give a linear programming relaxed bound algorithm for solving integer separable concave progtamming problems, in which partitioning procedure is simple integer rectangle two -partitioning one and upper -bounding procedure is simple heuristic one but lower-bounding procedure need to solve a linear programming relax approximation. It is shown with numerical test that the proposed algorithm is efficient and can solve the middle scale problems.

关 键 词：整数规划 可分离凹规划 分枝定界方法 线性规划松弛 

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