A primal all-integer algorithm based on irreducible solutions (Q1424268)

A primal augmentation algorithm for linear integer programs is given. First it is shown how a feasible solution of the IP (or a basis of slack variables) is turned into a basic feasible solution of an appropriate simplex tableau. Then nonbasic columns of the tableau are replaced by other columns to obtain ``proper reformulations'' of the tableau, so that every feasible direction w.r.t the basic feasible solution can be represented by the new non-basic variables. The integral basis method then performs these reformulations until either optimality is proved or an improving direction (an augmentation vector) is found. It is proved that each reformulation step is finite and that the algorithm is finite. A variant of the algorithm that uses discrete relaxations of the integer program is given and its correctness shown. Three types of such relaxations are studied in more detail. These are irreducible solutions from Gomory cuts, from primitive partition identities, and from strengthened 0/1 knapsack relaxations. They differ in the tradeoff between the strength of the relaxation and the cost of computing the irreducible solutions. At the end of the paper notes on implementation of the integral basis method and computational results are mentioned.