Minimum‐cost flow problems having arc‐activation costs
Abstract
Time‐dependent network applications, such as wireless sensor network and infrastructure optimization settings, may require dynamic flows to be transmitted according to a nonsimultaneous schedule of path‐flows. We study a dynamic network flow optimization problem considering the presence of activation costs required to begin transmitting flow on an arc. This problem can be modeled as a dynamic version of the minimum‐cost flow problem having arc‐activation costs (MCFA). The MCFA is related but not equivalent to the fixed‐charge network flow problem. We first discuss the relationship between these two problems, and show how MCFA is unique in the network flow literature. We present a mixed‐integer programming (MIP) model along with a series of symmetry‐breaking inequalities for solving the MCFA. As an alternative, we employ a relaxation‐based algorithm that iteratively obtains upper and lower bounds via the solution of a series of smaller, more tractable MIPs. We show that this algorithm finitely terminates with an optimal MCFA solution. Finally, computational results demonstrate the efficacy of our approach compared to solving a MIP using a state‐of‐the‐art commercial solver.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 14, 2021
- Source ID
- 10.1002/nav.22006
Entities
People
- J. Cole Smith
- Robert M. Curry
Organizations
- Office of Naval Research
- Syracuse University
- United States Naval Academy