Premium
Three‐partition flow cover inequalities for constant capacity fixed‐charge network flow problems
Author(s) -
Atamtürk Alper,
Gómez Andrés,
Küçükyavuz Simge
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21677
Subject(s) - flow (mathematics) , partition (number theory) , cover (algebra) , constant (computer programming) , flow network , mathematics , inequality , node (physics) , mathematical optimization , computer science , combinatorics , mathematical analysis , geometry , engineering , mechanical engineering , programming language , structural engineering
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. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 67(4), 299–315 2016