The mixed cutting plane algorithm for all-integer programming (Q1092815): Difference between revisions

This paper presents a cutting plane algorithm for the solution of the linear integer programming problem (IP). An all-integer simplex algorithm [cf. \textit{J. C. Crown}, Solution of linear algebraic systems using all- integer tableaux, presented at the AMS-meeting Cincinnati, Ohio (1982)] is used to solve the LP-relaxation of (IP). Two types of Gomory fractional cuts: (i) one that results in the greatest decrease in the current objective function value, (ii) one that results in the greatest decrease in \(D^*\), the order of the Abelian group associated with the current basis, are applied until \(D^*=1\), i.e. an all-integer tableau is obtained. If the associated solution is primal feasible, (IP) is solved. If this is not the case, the algorithm continues with dual all-integer cuts until a solution of (IP) is obtained. Detailed computational results (based upon 85 test problems) are reported.