Minimum Cost Flow Problem on Dynamic Multi Generative Network flows

Authors

  • Seyed Ahmad Hosseini
  • Hassan Salehi Fathabadi School of Mathematics and Computer Science, College of Science, University of Tehran, Iran

Keywords:

Network flows, LP problems, Dynamic flows, Time-commodity expanded network, Decomposition methods

Abstract

This paper consists of studies of constructing and modeling Dynamic Multi Generative Network Flows in which the flow commodities is dynamically generated at source nodes and dynamically consumed at sink nodes. It is assumed that the source nodes produce the flow commodities according to k time generative functions and the sink nodes absorb the flow commodities according to k time consumption functions. The minimum cost dynamic flow problem in such networks, that extend the classical optimal flow problems on static networks, for a pre-specified time horizon T is defined and mathematically formulated and it's showed that the dynamic problem on these networks can be formulated as a linear program whose special structure permits efficient computations of its solution and can be solved by one minimum cost static flow computation on an auxiliary time-commodity expanded network. Moreover, using flow decomposition theorem, we elaborate a different model of the problem in order to reduce its complexity. We consider the problem in the general case when cost and capacity functions depend on time and commodity.

Author Biography

Seyed Ahmad Hosseini

Mathematics and Computer Sciences

Downloads

Published

2010-04-14

How to Cite

Hosseini, S. A., & Fathabadi, H. S. (2010). Minimum Cost Flow Problem on Dynamic Multi Generative Network flows. Algorithmic Operations Research, 5(1), Pages 39 – 48. Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/12411

Issue

Vol. 5 No. 1 (2010)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.