An Efficient Algorithm for Computing Robust Minimum Capacity s-t Cuts
Doug Altner (daltnergatech.edu)
Abstract: The Minimum Capacity s-t Cut Problem (Min Cut) is an intensively studied problem in combinatorial optimization. In this paper, we study Min Cut when arc capacities are uncertain but known to exist in pre-specified intervals. This framework can be used to model many real-world applications of Min Cut under data uncertainty such as in open-pit mining or scheduling jobs on two processors. In this paper, we present an efficient algorithm for computing minimum capacity s-t cuts under a polyhedral model of robustness. Our algorithm builds on the idea of the general algorithm of Bertsimas and Sim for solving robust combinatorial optimization problems (RobuCOPs). We demonstrate that our algorithm is fast when compared to a naive algorithm that uses a black-box maximum flow solver as a subroutine. Specifically, we demonstrate that our implementation can solve instances of the robust minimum s-t cut problem in seconds whereas an implementation using a black-box maximum flow solver would take hours.
Keywords: Minimum Capacity Cut, Robust Optimization, Maximum Flow Reoptimization
Category 1: Network Optimization
Category 2: Robust Optimization
Citation: H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Technical Report March, 2008.
Entry Submitted: 03/20/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|