A New Cutting Plane Algorithm for Integer Linear Programming
作者
Kedong Chen,Zhong Cheng Wu,Zhi-Jie Xia
出处
期刊:International Conference on Computer Science and Service System日期:2012-08-01卷期号:c1998: 1591-1594被引量:3
标识
DOI:10.1109/csss.2012.398
摘要
A novel cutting plane algorithm for integer linear programming (ILP) is proposed in this paper. It restarts with an all-integer ILP system at each iteration by adding an all-integer cut, which is the function of the non-basis variables of the original system, to original system. Compared with fractional cutting plane (FCP) algorithm, this algorithm shows favorable numerical stability. Compared with all-integer cutting plane (AICP) algorithm, this algorithm decreases greatly the cases of degeneracy. Furthermore, it only needs few cuts to reach the optimal solution. Some ILP examples demonstrate the new algorithm can resolve many examples which the other two algorithms cannot.