On the decomposition of test sets

We present the positive sum property of Graver test sets and present similar algorithms, based on a completion procedure, to compute these sets for the LP, IP, and MIP cases. Then we deal with Graver test sets for two- and multi-stage stochastic (mixed-integer) programs. Here, we use the block angular structure of the matrix to decompose not the problem itself but the corresponding test set instead. This leads to a finite set of building blocks from which for any number of scenarios all test set vectors can be constructed. We give an algorithm to compute these finitely many building blocks and show with and example that the resulting augmentation algorithm acts indeed fairly insensitive to an increasing number of scenarios. This decomposition approach is then generalized to arbitrary problem matrices. Moreover, a computer code, MLP, is presented that computes Graver and Hilbert bases.


Citation style:
Could not load citation form.


Use and reproduction:
All rights reserved