Title :
A New Cutting Plane Algorithm for Integer Linear Programming
Author :
Chen, Ke-dong ; Wu, Zhong ; Xia, Zhi-jie
Author_Institution :
Sch. of Manage., Shanghai Univ. of Eng. Sci., Shanghai, China
Abstract :
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.
Keywords :
integer programming; iterative methods; linear programming; numerical stability; AICP algorithm; all-integer ILP system; all-integer cutting plane algorithm; degeneracy; integer linear programming; iterative system; nonbasis variables; numerical stability; optimal solution; Algorithm design and analysis; Educational institutions; Equations; Linear programming; Optimization; Programming; Roundoff errors; Integer programming; all-integer cutting plane; cutting plane algorithm;
Conference_Titel :
Computer Science & Service System (CSSS), 2012 International Conference on
Conference_Location :
Nanjing
Print_ISBN :
978-1-4673-0721-5
DOI :
10.1109/CSSS.2012.398