Scarf’s procedure for integer programming and a dual simplex algorithm
Abstract
Scarf has recently introduced an algorithm for integer programs based on the combinatorial concept of a primitive set. We show that as the decision variables of the integer program become continuous and the integer program reduces to a linear program, the Scarf algorithm converges to a dual simplex algorithm for the limit linear programming problem.