Facets of the stochastic network flow problem

ALEXANDER S. ESTES, MICHAEL O. BALL

Research output: Contribution to journalArticlepeer-review

Abstract

We study a type of network ow problem that we call the minimum-cost F-graph flow problem. This problem generalizes the typical minimum-cost network flow problem by allowing the underlying network to be a directed hypergraph rather than a directed graph. This new problem is pertinent because it can be used to model network ow problems that occur in a dynamic, stochastic environment. We formulate this problem as an integer program, and we study specifically the case where every node has at least one outgoing edge with no capacity constraint. We show that even with this restriction, the problem of finding an integral solution is NP-hard. However, we can show that all of the inequality constraints of our formulation are either facet-defining or redundant.

Original languageEnglish (US)
Pages (from-to)2355-2378
Number of pages24
JournalSIAM Journal on Optimization
Volume30
Issue number3
DOIs
StatePublished - 2020

Keywords

  • Directed hypergraphs
  • F-graphs
  • Facet-defining inequalities
  • Network ow
  • Stochastic integer programming

Fingerprint Dive into the research topics of 'Facets of the stochastic network flow problem'. Together they form a unique fingerprint.

Cite this