摘要
分支定界(B&B)算法是求解整数线性规划(ILP)问题的一种最常用的方法,如何划分问题(分支)和按何种策略选择子问题进行扩展是影响算法效率的两个重要因素。提出了一种改进的分支定界算法,采用伪费用分支策略划分问题,采用深度优先搜索(DFS)策略选择子问题进行扩展,并在Matlab中编程实现。数值实验表明,改进的算法能够有效提高求解效率,当问题规模较大时,改进效果尤其明显。
The Branch-and-Bound（BB） algorithm is the most general method to solve Integer Linear Programming（ILP） problems.There are two important factors affecting efficiency in BB algorithm,how to split a problem（branching） and which subproblem to select next.The authors proposed a revised BB algorithm that adopted pseudocost branching strategies to split a problem and adopted Depth-First-Search（DFS） strategies to select next problem,finally realized the revised BB algorithm on Matlab.The numerical results show that the efficiency of the revised BB algorithm is improved.when the problem size is larger,the improvement is particularly effective.
出处
《计算机应用》
CSCD
北大核心
2011年第A02期36-38,共3页
journal of Computer Applications
基金
国家自然科学基金资助项目(70971136)
关键词
分支定界算法
整数线性规划
伪费用分支
深度优先搜索策略
Branch-and-Bound（B＆B） algorithm
Integer Linear Programming（ILP）
pseudocost branching
Depth-First-Search（DFS）strategy
