KIT | KIT-Bibliothek | Impressum | Datenschutz

Two-stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms

Rebennack, Steffen; Prokopyev, Oleg A.; Singh, Bismark

Abstract:
We introduce the two‐stage stochastic minimum s − t cut problem. Based on a classical linear 0‐1 programming model for the deterministic minimum s − t cut problem, we provide a mathematical programming formulation for the proposed stochastic extension. We show that its constraint matrix loses the total unimodularity property, however, preserves it if the considered graph is a tree. This fact turns out to be not surprising as we prove that the considered problem is NP-hard in general, but admits a linear time solution algorithm when the graph is a tree. We exploit the special structure of the problem and propose a tailored Benders decomposition algorithm. We evaluate the computational efficiency of this algorithm by solving the Benders dual subproblems as max-flow problems. For many tested instances, we outperform a standard Benders decomposition by two orders of magnitude with the Benders decomposition exploiting the max-flow structure of the subproblems.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000104762
Veröffentlicht am 13.01.2020
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Operations Research (IOR)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2019
Sprache Englisch
Identifikator ISSN: 0028-3045, 1097-0037
KITopen-ID: 1000104762
Erschienen in Networks
Band 75
Heft 3
Seiten 235-258
Vorab online veröffentlicht am 29.11.2019
Schlagwörter Benders decomposition, combinatorial optimization, complexity, minimum s-t cut problem, total unimodularity, two-stage stochastic programming
Nachgewiesen in Scopus
Web of Science
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page