Decomposition of test sets in stochastic integer programming

Abstract

Graver test sets for linear two-stage stochastic integer programs are studied. It is shown that test sets can be decomposed into finitely many building blocks whose number is independent of the number of scenarios of the sochastic program. A finite algorithm to compute the building blocks directly, without prior knowledge of test set vectors, is presented. Once computed, building blocks can be employed to solve the stochastic program by a simple augmentation scheme, again without explicit knowledge of test set vectors. Preliminary computational experience is reported.