Three-partition flow cover inequalities for constant capacity fixed-charge network flow problems

Alper Atamtürk*, Andrés Gómez, Simge Küçükyavuz

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Flow cover inequalities are among the most effective valid inequalities for capacitated fixed-charge network flow problems. These valid inequalities are based on implications for the flow quantity on the cut arcs of a two-partitioning of the network, depending on whether some of the cut arcs are open or closed. As the implications are only on the cut arcs, flow cover inequalities can be obtained by collapsing a subset of nodes into a single node. In this article, we derive new valid inequalities for the capacitated fixed-charge network flow problem by exploiting additional information from the network. In particular, the new inequalities are based on a three partitioning of the nodes. The new three-partition flow cover inequalities include the flow cover inequalities as a special case. We discuss the constant capacity case and give a polynomial separation algorithm for the inequalities. Finally, we report computational results with the new inequalities for networks with different characteristics.

Original languageEnglish (US)
Pages (from-to)299-315
Number of pages17
JournalNetworks
Volume67
Issue number4
DOIs
StatePublished - Jul 1 2016

Keywords

  • facets
  • fixed-charge network flow
  • integer programming
  • lifting
  • superadditivity
  • three-partition

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Three-partition flow cover inequalities for constant capacity fixed-charge network flow problems'. Together they form a unique fingerprint.

Cite this