Minimum-cost flow problems having arc-activation costs

Robert M. Curry, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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)
Pages (from-to)320-335
Number of pages16
JournalNaval Research Logistics
Volume69
Issue number2
DOIs
StatePublished - Mar 2022

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