Minimum-cost flow problems having arc-activation costs

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.