Minimum cost capacity installation for multicommodity network flows

Daniel Bienstock*, Sunil Chopra, Oktay Günlük, Chih Yang Tsai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

135 Scopus citations


Consider a directed graph G = (V , A), and a set of traffic demands to be shipped between pairs of nodes in V. Capacity has to be installed on the edges of this graph (in integer multiples of a base unit) so that traffic can be routed. In this paper we consider the problem of minimum cost installation of capacity on the arcs to ensure that the required demands can be shipped simultaneously between node pairs. We study two different approaches for solving problems of this type. The first one is based on the idea of metric inequalities (see Onaga and Kakusho, On feasibility conditions of multicommodity flows in networks, IEEE Transactions on Circuit Theory, CT-18 (4) (1971) 425-429.), and uses a formulation with only |A| variables. The second uses un aggregated multicommodity flow formulation and has |V||A| variables. We first describe two classes of strong valid inequalities and use them to obtain a complete polyhedral description of the associated polyhedron for the complete graph on three nodes. Next we explain our solution methods for both of the approaches in detail and present computational results. Our computational experience shows that the two formulations are comparable and yield effective algorithms for solving real-life problems.

Original languageEnglish (US)
Pages (from-to)177-199
Number of pages23
JournalMathematical Programming, Series B
Issue number2
StatePublished - Apr 1 1998


  • Integer programming
  • Network design

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Minimum cost capacity installation for multicommodity network flows'. Together they form a unique fingerprint.

Cite this