DocumentCode :
584478
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
fYear :
2012
fDate :
11-13 Aug. 2012
Firstpage :
1591
Lastpage :
1594
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Science & Service System (CSSS), 2012 International Conference on
Conference_Location :
Nanjing
Print_ISBN :
978-1-4673-0721-5
Type :
conf
DOI :
10.1109/CSSS.2012.398
Filename :
6394637
Link To Document :
بازگشت