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.