Algorithms for an Integer Multicommodity Network Flow Problem with Node Reliability Considerations

Bita Tadayon, J. Cole Smith

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

In this paper, we consider the problem of sending a set of multiple commodities from their origin to destination nodes via intermediate hubs. Each hub node is associated with a reliability function, which depends on the total flow that crosses that hub. The probability that each commodity is successfully relayed from its origin to its destination is given by the product of hub reliabilities on the commodity’s path. The problem we consider seeks to find minimum-cost commodity paths such that each commodity reaches its destination with a sufficiently large probability. We first formulate the problem as a nonlinear multicommodity network-flow problem and prove that it is strongly NP-hard. We then present two linearization techniques for this formulation, and propose a pair of lower- and upper-bounding formulations, which can then be used within an exact cutting-plane algorithm to solve the problem. Finally, we analyze the computational effectiveness of our proposed strategies on a set of randomly generated instances.

Original languageEnglish (US)
Pages (from-to)506-532
Number of pages27
JournalJournal of Optimization Theory and Applications
Volume161
Issue number2
DOIs
StatePublished - May 1 2014
Externally publishedYes

Keywords

  • Congestion
  • Cutting planes
  • Integer programming
  • Multicommodity flow
  • Node reliabilities

ASJC Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Algorithms for an Integer Multicommodity Network Flow Problem with Node Reliability Considerations'. Together they form a unique fingerprint.

  • Cite this