Models and algorithms for maximum flow problems having semicontinuous path flow constraints

ABSTRACT

This article considers a variation of the node- and arc-capacitated maximum flow problem having semicontinuous flow restrictions. A semicontinuous variable must either take a value of zero or belong in the interval [ℓ, u] for some 0 < ℓ ⩽ u. Of particular interest are problems in which the variables correspond to the amount of flow sent along an entire origin–destination path. We examine both static and dynamic variations of this problem. As opposed to solving a Mixed-Integer Programming (MIP) model, we propose a branch-and-price algorithm for the static version of this problem, including a specialized branching strategy that leverages the existence of cut-sets in a non-feasible solution. For the dynamic version of the problem, we present an exact MIP formulation along with a set of symmetry-breaking and subtour-elimination constraints to improve its solvability. We demonstrate the efficacy of our algorithms on a set of randomly generated test instances.

KEYWORDS:

• Network optimization
• maximum flow problem
• semicontinuous variables
• branch and price

Acknowledgements

The authors are grateful for the remarks of two anonymous referees and an associate editor, whose comments helped improve the motivation and presentation of the article.

Funding

Funding for this study was provided by the Air Force Office of Scientific Research (FA9550-12-1-0353) and the Office of Naval Research (N000141310036, N000141712421).

Additional information

Notes on contributors

Robert M. Curry

Robert M. Curry is currently a Ph.D. candidate in the Department of Industrial Engineering at Clemson University. His research concentrates on methodology and algorithmic approaches in network optimization, combinatorial optimization, and integer programming. In particular, he studies exact algorithms for solving large-scale network flow optimization problems having applications in energy systems, transportation and logistics systems, evacuation planning, and humanitarian logistics. He received a B.S. in Industrial Engineering from the University of Arkansas (2013) and an M.S. in Industrial and Systems Engineering from the University of Florida (2014).

J. Cole Smith

J. Cole Smith is Professor and Chair of the Industrial Engineering Department at Clemson University. His research has been supported by the NSF, DARPA, AFOSR, DTRA, and the ONR, and he has spent one summer as a Distinguished Visiting Professor in the National Security Agency’s summer program in operations research technology. His research regards mathematical optimization models and algorithms, especially those arising in combinatorial optimization. His awards include the Young Investigator Award from the ONR, the Hamid K. Elden Outstanding Young Industrial Engineer in Education Award, the Operations Research Division Teaching Award, the 2014 Glover-Klingman prize for best paper in Networks, and the best paper award from IIE Transactions in 2007.