Minimum-cost flow problems having arc-activation costs

Robert M. Curry, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
JournalNaval Research Logistics
DOIs
StateAccepted/In press - 2021

Keywords

  • consecutive flows
  • fixed-charge network flow problems
  • integer programming
  • minimum-cost flow problems
  • network flow optimization

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Minimum-cost flow problems having arc-activation costs'. Together they form a unique fingerprint.

Cite this