Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja R.K., Magnanti T.L., Orlin J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs (1993)
Ahuja R.K., Orlin J.B., Sechi G.M., Zuddas P.: Algorithms for the simple equal flow problem. Manag. Sci. 45(10), 1440–1455 (1999)
Ali A.I., Kennington J., Shetty B.: The equal flow problem. Eur. J. Oper. Res. 36(1), 107–115 (1988)
Bahçeci, U., Feyziog͂lu, O.: Inventory allocation in multi-period multi-echelon logistics network of modular products. In: Proceedings of the 8th ENIM IFAC International Conference of Modeling and Simulation, vol. 3, pp. 1021–1030. Hammamet, Tunisia (2010)
Calvete H.I.: Network simplex algorithm for the general equal flow problem. Eur. J. Oper. Res. 150(3), 585–600 (2003)
Du D.Z., Pardalos P.M.: Network Optimization Problems: Algorithms, Applications and complexity. Applied Mathematics. World Scientific, Singapore (1993)
Eksioglu S.D. : Inventory Management in Supply Chains. In: Floudas, C.A., Pardalos, P.M. (eds) Encyclopedia of Optimization, vol. 2., pp. 1766–1770. Springer, Berlin (2009)
Fang S.C., Qi L.Q.: Manufacturing network flows: a generalized network flow model for manufacturing process modelling. Optim. Methods Softw. 18(2), 143–165 (2003)
Helgason R.V., Kennington J.L.: Primal simplex algorithms for minimum cost network flows. In: Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds) Handbooks in Operations Research and Management Sciences: Network Models, vol. 8., pp. 85–133. Elsevier, Amsterdam (1995)
Kennington J.L., Helgason R.V.: Algorithms for Network Programming. Wiley, New York (1980)
Lu H., Yao E., Qi L.: Some further results on minimum distribution cost flow problems. J. Combin. Optim. 11(4), 351–371 (2006)
Lu H.Y., Yao E.Y., Zhang B.W.: A note on a generalized network flow model for manufacturing process. Acta Math. Appl. Sin. Engl. Ser. 25(1), 51–60 (2009)
Mo J., Qi L., Wei Z.: A manufacturing supply chain optimization model for distilling process. Appl. Math. Comput. 171(1), 464–485 (2005)
Mo J., Qi L., Wei Z.: A network simplex algorithm for simple manufacturing network model. J. Ind. Manag. Optim. 1(2), 251–273 (2005)
Pardalos P.M., Hearn D.W., Hager W.W.: Network Optimization, Lecture Notes in Economics and Mathematical Systems, vol. 450. Springer, Berlin (1997)
Venkateshan P., Mathur K., Ballou R.H.: An efficient generalized network-simplex-based algorithm for manufacturing network flows. J. Combin. Optim. 15(4), 315–341 (2008)
Wang I.L., Lin S.J.: A network simplex algorithm for solving the minimum distribution cost problem. J. Ind. Manag. Optim. 5(4), 929–950 (2009)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bahçeci, U., Feyziog͂lu, O. A network simplex based algorithm for the minimum cost proportional flow problem with disconnected subnetworks. Optim Lett 6, 1173–1184 (2012). https://doi.org/10.1007/s11590-011-0356-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0356-5