A Simplified Primal (All-Integer) Integer Programming Algorithm

Publisher Website
Google Scholar
Abstract
This paper describes a primal, all-integer algorithm for solving a bounded and solvable pure integer programming problem. The method is a primal analogue to the Gomory All-Integer Algorithm, and is a variant of the simplex method in sense that the Gomory algorithm is a variant of the dual method. The simplified primal algorithm makes these major amendments to the simplex method: (i) a special row, indexed by L, is adjoined to the tableau and is periodically revised by a well-defined procedure; (ii) in most cycles of the algorithm the pivot column, AJ, is selected so that aLJ > 0 and (1/aLJ)AJ is lexicographically smaller than (1/aLj)Aj for all nonbasic columns Aj that have aLj > 0; (iii) in all cycles of the algorithm a Gomory cut is adjoined after selection of the pivot column, and the cut is selected so that it will have a unit coefficient in the pivot column and it will qualify (in order to be used) as the pivot row. With comparatively minor restrictions on the selection of the row used to generate the Gomory cut the simplified primal algorithm is shown to be finite.

This publication has 0 references indexed in Scilit: