About the Complexity of Two-Stage Stochastic IPs

Wir betrachten so genannte 2-stufige stochastische Integerprogramme (IPs) und ihre verallgemeinerte Form mehrstufiger stochastischer IPs. Ein 2-stufiges stochastisches IP ist ein ganzzahliges Programm der Form, in der die Constraint Matrix grob aus n Wiederholungen einer Blockmatrix auf der vertikalen Linie und n Wiederholungen einer Matrix auf der Diagonalen besteht. In dieser Arbeit verbessern wir ein algorithmisches Ergebnis von Hemmecke und Schultz aus dem Jahr 2003 [16], um 2-stufige stochastische IPs zu lösen. Der Algorithmus basiert auf dem Graver Augmentationsrahmen, in dem unser Hauptbeitrag darin besteht, eine explizite doppelte exponentielle Grenze hinsichtlich der Größe der Augmentationsschritte zu geben. Die vorherige Grenze für die Größe der Augmentationsschritte beruhte auf nicht konstruktiven Endlichkeitsargumenten aus der kommutativen Algebra und daher war nur eine implizite Grenze bekannt, die von den Parametern r, s, t und wo der größte Eintrag der Beschränkungsrix ist, ein neuartiges Ergebnis der IPs im neuen Intergorithmus ist, in dem wir eine zweistufige Funktion erhalten.