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, sa.6, ss.1173-1184, 2012 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 6 Sayı: 6
  • Basım Tarihi: 2012
  • Doi Numarası: 10.1007/s11590-011-0356-5
  • Dergi Adı: OPTIMIZATION LETTERS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1173-1184
  • Anahtar Kelimeler: Minimum cost network flow, Proportional flow, Disconnected subnetworks, Network simplex algorithm, MANUFACTURING PROCESS, MODEL
  • Galatasaray Üniversitesi Adresli: Evet

Ö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.