On the positive sums property and the computation of Graver test sets (Q1424269)

The paper addresses test set methods for LP, IP, and MIP problems. The positive sum property, which implies the universal test set property, is investigated. Two criteria are presented that characterize sets that have the positive sum property with respect to an integer lattice or with respect to ker\(_{\mathbb{R}^d}(A)\). An algorithm to complete a set of vectors with respect to the positive sum property is given. Based on these results, methods to compute Graver test sets for IP, LP, and MIP are developed. Finally, it is shown how to ensure termination of the augmentation algorithm to solve IP, LP, and MIP problems and how to use test sets to find a feasible solution to these problems.