Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

In this talk we present a novel approach for solving linear 2-stage stochastic integer programs. Instead of decomposing the problem itself, we decompose its asscoiated Graver test set into finitely many building blocks whose number is independent on the number of scenarios of the stochastic 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 (the full, huge) test set. Finally, this decomposition idea is employed to solve prolems with arbitrary rational problem matrix and to solve linear mixed-integer programs via test set methods.