计算机应用 ›› 2010, Vol. 30 ›› Issue (4): 1019-1021.

• 人工智能 • 上一篇    下一篇

高效求解整数线性规划问题的分支算法

高培旺   

  1. 广西财经学院
  • 收稿日期:2009-09-09 修回日期:2009-12-22 发布日期:2010-04-15 出版日期:2010-04-01
  • 通讯作者: 高培旺
  • 基金资助:
    广西自然科学基金

Effective branch algorithm for integer linear programming problems

  • Received:2009-09-09 Revised:2009-12-22 Online:2010-04-15 Published:2010-04-01
  • Supported by:
    Guangxi Natural Science Foundation of China

摘要: 为了提高求解一般整数线性规划问题的效率,提出了一种基于目标函数超平面移动的分支算法。对于给定的目标函数整数值,首先利用线性规划松弛问题的最优单纯形表确定变量的上、下界,然后将变量的上、下界条件加入约束条件中对相应的目标函数超平面进行切割,最后应用分支定界算法中的分支方法来搜寻目标函数超平面上的可行解。通过对一些经典的数值例子的求解计算并与经典的分支定界算法进行比较,结果表明,该算法减少了分支数和单纯形迭代数,具有较大的实用价值。

关键词: 线性规划, 整数规划, 目标函数超平面, 单纯形算法, 分支算法

Abstract: In order to improve the computational efficiency, a branch algorithm for general integer linear programming problems on the objective function hyperplane shifts was presented. First, for a given integer value of the objective function, the lower and upper bounds of the variables were determined by the optimum simplex tableau of the linear programming relaxation problem. Then the conditions on the bounds were added to the constraints as cuts to the associated objective function hyperplane. Finally, a branch procedure of the branch-and-bound algorithm was applied to finding a feasible solution on the objective function hyperplane. The computational test on some classical numerical examples shows that, compared with the classical branch-and-bound principle, the algorithm greatly decreases the number of branches and the number of iterations in computation, and therefore, is of practical value.

Key words: Linear Programming (LP), Integer programming, Objective function hyperplane, Simplex method, Branch algorithm