整数线性规划的改进分支定界算法

作者：于战科; 倪明放; 汪泽焱; 武欣嵘

来源：计算机应用, 2011, S2: 36-38.

• 分支定界算法
• 整数线性规划
• 伪费用分支
• 深度优先搜索策略 Branch-and-Bound(B&amp
• B) algorithm
• Integer Linear Programming(ILP)
• pseudocost branching
• Depth-First-Search(DFS)strategy

分支定界(B&B)算法是求解整数线性规划(ILP)问题的一种最常用的方法,如何划分问题(分支)和按何种策略选择子问题进行扩展是影响算法效率的两个重要因素。提出了一种改进的分支定界算法,采用伪费用分支策略划分问题,采用深度优先搜索(DFS)策略选择子问题进行扩展,并在Matlab中编程实现。数值实验表明,改进的算法能够有效提高求解效率,当问题规模较大时,改进效果尤其明显。

• 单位
  中国人民解放军陆军工程大学