On a Group Theoretic Approach to Linear Integer Programming

摘要

The paper extends some results of Gomory on a group theoretic approach to linear integer programming. An algorithm for solving integer programming problems is presented, and the relation of this work to cuts and appropriate geometric interpretations are given. The theoretical basis for the algorithm establishes a characterization of integer solutions to linear programs by considering the Gomory column group associated with the optimal linear programming basis. It is shown that if an optimal integer solution exists, it can be obtained by finding the rth optimal solution to an optimization problem over elements in this Gomory group, for some finite r. A dynamic programming procedure for finding this rth optimal solution is given, and shown to be equivalent to finding an rth shortest route through a specially constructed network. A particular class of cutting planes is discussed. These cuts are shown to be parallel to a subset of Gomory cuts and at least as strong as the Gomory cuts. Specially structured integer programs are discussed with a view toward speeding computation. Included in this discussion is a specialization to zero-one variables. Some computational results are given. It is seen that computational efficiency depends crucially on the size of the absolute value of the determinant of the optimal linear programming basis. In general, the smaller this absolute value, the more efficient the algorithm. (Author)