Hemmecke, Raymond

On the decomposition of test sets

building blocks, connection sets, and algorithms

Über die Dekomposition von Testmengen
Bausteine, Verbindungsmengen und Algorithmen

Thesis

Filetyp: PDF (.pdf)
Size: Kb

Schlüsselwörter:

Graver test sets, stochastic programming, primal methods, integer programming

Sachgruppe der DNB
27 Mathematik
Mathematics Subject Classification (MSC)
90C10, 90C15, 13P10


Doctoral Dissertation accepted by: University of Duisburg , Department of Mathematics/Computer Science, 2001-09-24

Abstract

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

Betreuer Prof. Dr. Rüdiger Schultz
Gutachter Prof. Dr. Rüdiger Schultz
Gutachter Prof. Dr. Rekha R. Thomas (Univ. of Washington)

Upload: 2001-09-28
URL of Theses: http://duepublico.uni-duisburg-essen.de/servlets/DerivateServlet/Derivate-5141/diss_hemmecke.pdf

University of Duisburg , Library
Lotharstr.65 , 47048 Duisburg, Germany