Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms. Issue 3 (29th November 2019)

• Record Type: Journal Article
• Authors: Rebennack, Steffen; Prokopyev, Oleg A.; Singh, Bismark
• Is Part Of: Networks. Volume 75:Issue 3(2020)
• Page Start: 235
• Page End: 258
• Publication Date: 2019-11-29
• Subjects: Benders decomposition -- combinatorial optimization -- complexity -- minimum s − t cut problem -- total unimodularity -- two‐stage stochastic programming; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21922
• Languages: English
• ISSNs: 0028-3045

Abstract

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.