A network simplex based algorithm for the minimum cost proportional flow problem with disconnected subnetworks


BAHÇECİ U. , FEYZİOĞLU O.

OPTIMIZATION LETTERS, cilt.6, ss.1173-1184, 2012 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 6 Konu: 6
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1007/s11590-011-0356-5
  • Dergi Adı: OPTIMIZATION LETTERS
  • Sayfa Sayıları: ss.1173-1184

Özet

In this study, we present a variant of the minimum cost network flow problem where the associated graph contains several disconnected subgraphs and it is required that the flows on arcs belonging to same arc subsets to be proportional. This type of network is mostly observed in large supply chains of assemble-to-order products. It is shown that any feasible solution of a reformulation of this problem has a special characteristic. By taking into account this fact, a network simplex based primal simplex algorithm is developed and its details are provided.