American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Component allocation cost minimization for a multistate computer network subject to a reliability threshold using tabu search
  • JIMO Home
  • This Issue
  • Next Article
    A full-modified-Newton step infeasible interior-point algorithm for linear optimization
January  2016, 12(1): 117-140. doi: 10.3934/jimo.2016.12.117

A compaction scheme and generator for distribution networks

I-Lin Wang 1, and  Ju-Chun Lin 1,

1. 

Department of Industrial and Information Management, National Cheng Kung University, Tainan, 701, Taiwan

Received  March 2014 Revised  November 2014 Published  April 2015

In a distribution network, materials or products that go through a decomposition process can be considered as flows entering a specialized node, called D-node, which distributes each decomposed flow along an outgoing arc. Flows on each arc emanating from a D-node have to obey a pre-specified proportional relationship, in addition to the capacity constraints. The solution procedures for calculating optimal flows over distribution networks in literature often assumes D-nodes to be disjoint, whereas in reality D-nodes may often connect to each other and complicate the problem. In this paper, we propose a polynomial-time network compaction scheme that compresses a distribution network into an equivalent one of smaller size, which can then be directly solved by conventional solution methods in related literature. In order to provide test cases of distribution networks containing D-nodes for computational tests in related research, we implement a random network generator that produces a connected and acyclic distribution network in a compact form. Mathematical properties together with their proofs are also discussed to provide more insights in the design of our generator.
Keywords: compaction scheme, proportional flow constraint, Distribution network, network generator, network optimization..
Mathematics Subject Classification: Primary: 90B10, 05C85; Secondary: 05C2.
Citation: I-Lin Wang, Ju-Chun Lin. A compaction scheme and generator for distribution networks. Journal of Industrial and Management Optimization, 2016, 12 (1) : 117-140. doi: 10.3934/jimo.2016.12.117
References:
[1]

R. K. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, New Jersey, 1993.

[2]

R. J. Anderson and J. C. Setubal, Goldberg's algorithm for maximum flow in perspective: A computatioinal study, in Network flows and matching: First DIMACS implementation challenge (eds. D. S. Johnson and C. McGeoch), 12, American Mathematical Society, (1993), 1-17.

[3]

U. Bahceci and O. Feyzioglu, A network simplex based algorithm for the minimum cost proportional flow problem with disconnected subnetworks, Optimization Letters, 6 (2012), 1173-1184. doi: 10.1007/s11590-011-0356-5.

[4]

M. D. Chang, C. H. J. Chen and M. Engquist, An improved primal simplex variant for pure processing networks, ACM Transactions on Mathematical Software, 15 (1989), 64-78. doi: 10.1145/62038.62041.

[5]

C. H. J. Chen and M. Engquist, A primal simplex approach to pure processing networks, Management Science, 32 (1986), 1582-1598. doi: 10.1287/mnsc.32.12.1582.

[6]

B. V. Cherkassky and A. V. Goldberg, On implementing push-relabel method for the maximum flow problem, Algorithmica, 19 (1997), 390-410. doi: 10.1007/PL00009180.

[7]

B. T. Denton, J. Forrest and R. J. Milne, Ibm solves a mixed-integer program to optimize its semiconductor supplychain, Interfaces, 36 (2006), 386-399.

[8]

S. C. Fang and L. Qi, Manufacturing network flows: A generalized network flow model for manufacturingprocess modeling, Optimization Methods and Software, 18 (2003), 143-165. doi: 10.1080/1055678031000152079.

[9]

D. Goldfarb and M. D. Grigoriadis, A computational comparison of the dinic and network simplex methods formaximum flow, Annals of Operations Research, 13 (1988), 83-123. doi: 10.1007/BF02288321.

[10]

D. Klingman, A. Napier and J. Stutz, Netgen: A program for generating large scale capacitated assignment, transportation and minimum cost flow networks, Management Science, 20 (1974), 814-820.

[11]

J. Koene, Minimal Cost Flow in Processing Networks, a Primal Approach, PhD thesis, Eindhoven University of Technology, Eindhoven, The Netherlands, 1983.

[12]

L.-C. Kung and C.-C. Chern, Heuristic factory planning algorithm for advanced planning and scheduling, Computers and Operations Research, 36 (2009), 2513-2530. doi: 10.1016/j.cor.2008.09.013.

[13]

Y.-K. Lin, C.-T. Yeh and C.-F. Huang, Reliability evaluation of a stochastic-flow distribution network with delivery spoilage, Computers and Industrial Engineering, 66 (2013), 352-359. doi: 10.1016/j.cie.2013.06.019.

[14]

H. Lu, E. Yao and L. Qi, Some further results on minimum distribution cost flow problems, Journal of Combinatorial Optimization, 11 (2006), 351-371.

[15]

P. Lyon, R. J. Milne, R. Orzell and R. Rice, Matching assets with demand in supply-chain management at ibm microelectronics, Interfaces, 31 (2001), 108-124. doi: 10.1287/inte.31.1.108.9693.

[16]

R. L. Sheu, M. J. Ting and I. L. Wang, Maximum flow problem in the distribution network, Journal of Industrial and Management Optimization, 2 (2006), 237-254. doi: 10.3934/jimo.2006.2.237.

[17]

J. Shu, M. Chou, Q. Liu, C.-P. Teo and I.-L. Wang, Models for effective deployment and redistribution of bicycles within public bicycle-sharing systems, Operations, 61 (2013), 1346-1359. doi: 10.1287/opre.2013.1215.

[18]

I. L. Wang and S. J. Lin, A network simplex algorithm for solving the minimum distribution cost problem, Journal of Industrial and Management Optimization, 5 (2009), 929-950. doi: 10.3934/jimo.2009.5.929.

[19]

I. L. Wang and Y. H. Yang, On solving the uncapacitated minimum cost flow problems in a distribution network, International Journal of Reliability and Quality Performance, 1 (2009), 53-63.

show all references

References:
[1]

R. K. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, New Jersey, 1993.

[2]

R. J. Anderson and J. C. Setubal, Goldberg's algorithm for maximum flow in perspective: A computatioinal study, in Network flows and matching: First DIMACS implementation challenge (eds. D. S. Johnson and C. McGeoch), 12, American Mathematical Society, (1993), 1-17.

[3]

U. Bahceci and O. Feyzioglu, A network simplex based algorithm for the minimum cost proportional flow problem with disconnected subnetworks, Optimization Letters, 6 (2012), 1173-1184. doi: 10.1007/s11590-011-0356-5.

[4]

M. D. Chang, C. H. J. Chen and M. Engquist, An improved primal simplex variant for pure processing networks, ACM Transactions on Mathematical Software, 15 (1989), 64-78. doi: 10.1145/62038.62041.

[5]

C. H. J. Chen and M. Engquist, A primal simplex approach to pure processing networks, Management Science, 32 (1986), 1582-1598. doi: 10.1287/mnsc.32.12.1582.

[6]

B. V. Cherkassky and A. V. Goldberg, On implementing push-relabel method for the maximum flow problem, Algorithmica, 19 (1997), 390-410. doi: 10.1007/PL00009180.

[7]

B. T. Denton, J. Forrest and R. J. Milne, Ibm solves a mixed-integer program to optimize its semiconductor supplychain, Interfaces, 36 (2006), 386-399.

[8]

S. C. Fang and L. Qi, Manufacturing network flows: A generalized network flow model for manufacturingprocess modeling, Optimization Methods and Software, 18 (2003), 143-165. doi: 10.1080/1055678031000152079.

[9]

D. Goldfarb and M. D. Grigoriadis, A computational comparison of the dinic and network simplex methods formaximum flow, Annals of Operations Research, 13 (1988), 83-123. doi: 10.1007/BF02288321.

[10]

D. Klingman, A. Napier and J. Stutz, Netgen: A program for generating large scale capacitated assignment, transportation and minimum cost flow networks, Management Science, 20 (1974), 814-820.

[11]

J. Koene, Minimal Cost Flow in Processing Networks, a Primal Approach, PhD thesis, Eindhoven University of Technology, Eindhoven, The Netherlands, 1983.

[12]

L.-C. Kung and C.-C. Chern, Heuristic factory planning algorithm for advanced planning and scheduling, Computers and Operations Research, 36 (2009), 2513-2530. doi: 10.1016/j.cor.2008.09.013.

[13]

Y.-K. Lin, C.-T. Yeh and C.-F. Huang, Reliability evaluation of a stochastic-flow distribution network with delivery spoilage, Computers and Industrial Engineering, 66 (2013), 352-359. doi: 10.1016/j.cie.2013.06.019.

[14]

H. Lu, E. Yao and L. Qi, Some further results on minimum distribution cost flow problems, Journal of Combinatorial Optimization, 11 (2006), 351-371.

[15]

P. Lyon, R. J. Milne, R. Orzell and R. Rice, Matching assets with demand in supply-chain management at ibm microelectronics, Interfaces, 31 (2001), 108-124. doi: 10.1287/inte.31.1.108.9693.

[16]

R. L. Sheu, M. J. Ting and I. L. Wang, Maximum flow problem in the distribution network, Journal of Industrial and Management Optimization, 2 (2006), 237-254. doi: 10.3934/jimo.2006.2.237.

[17]

J. Shu, M. Chou, Q. Liu, C.-P. Teo and I.-L. Wang, Models for effective deployment and redistribution of bicycles within public bicycle-sharing systems, Operations, 61 (2013), 1346-1359. doi: 10.1287/opre.2013.1215.

[18]

I. L. Wang and S. J. Lin, A network simplex algorithm for solving the minimum distribution cost problem, Journal of Industrial and Management Optimization, 5 (2009), 929-950. doi: 10.3934/jimo.2009.5.929.

[19]

I. L. Wang and Y. H. Yang, On solving the uncapacitated minimum cost flow problems in a distribution network, International Journal of Reliability and Quality Performance, 1 (2009), 53-63.

[1]

R.L. Sheu, M.J. Ting, I.L. Wang. Maximum flow problem in the distribution network. Journal of Industrial and Management Optimization, 2006, 2 (3) : 237-254. doi: 10.3934/jimo.2006.2.237
[2]

Yunan Wu, Guangya Chen, T. C. Edwin Cheng. A vector network equilibrium problem with a unilateral constraint. Journal of Industrial and Management Optimization, 2010, 6 (3) : 453-464. doi: 10.3934/jimo.2010.6.453
[3]

Jia Shu, Jie Sun. Designing the distribution network for an integrated supply chain. Journal of Industrial and Management Optimization, 2006, 2 (3) : 339-349. doi: 10.3934/jimo.2006.2.339
[4]

Qiong Liu, Ahmad Reza Rezaei, Kuan Yew Wong, Mohammad Mahdi Azami. Integrated modeling and optimization of material flow and financial flow of supply chain network considering financial ratios. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 113-132. doi: 10.3934/naco.2019009
[5]

Roberto Civino, Riccardo Longo. Formal security proof for a scheme on a topological network. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021009
[6]

Alberto Bressan, Khai T. Nguyen. Conservation law models for traffic flow on a network of roads. Networks and Heterogeneous Media, 2015, 10 (2) : 255-293. doi: 10.3934/nhm.2015.10.255
[7]

Chun Zong, Gen Qi Xu. Observability and controllability analysis of blood flow network. Mathematical Control and Related Fields, 2014, 4 (4) : 521-554. doi: 10.3934/mcrf.2014.4.521
[8]

Ángela Jiménez-Casas, Aníbal Rodríguez-Bernal. Linear model of traffic flow in an isolated network. Conference Publications, 2015, 2015 (special) : 670-677. doi: 10.3934/proc.2015.0670
[9]

King Hann Lim, Hong Hui Tan, Hendra G. Harno. Approximate greatest descent in neural network optimization. Numerical Algebra, Control and Optimization, 2018, 8 (3) : 327-336. doi: 10.3934/naco.2018021
[10]

I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929
[11]

Huai-Che Hong, Bertrand M. T. Lin. A note on network repair crew scheduling and routing for emergency relief distribution problem. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1729-1731. doi: 10.3934/jimo.2018119
[12]

Andrey Kovtanyuk, Alexander Chebotarev, Nikolai Botkin, Varvara Turova, Irina Sidorenko, Renée Lampe. Modeling the pressure distribution in a spatially averaged cerebral capillary network. Mathematical Control and Related Fields, 2021, 11 (3) : 643-652. doi: 10.3934/mcrf.2021016
[13]

Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial and Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251
[14]

Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial and Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71
[15]

Gunhild A. Reigstad. Numerical network models and entropy principles for isothermal junction flow. Networks and Heterogeneous Media, 2014, 9 (1) : 65-95. doi: 10.3934/nhm.2014.9.65
[16]

Hari Nandan Nath, Urmila Pyakurel, Tanka Nath Dhamala, Stephan Dempe. Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2943-2970. doi: 10.3934/jimo.2020102
[17]

Linhe Zhu, Wenshan Liu. Spatial dynamics and optimization method for a network propagation model in a shifting environment. Discrete and Continuous Dynamical Systems, 2021, 41 (4) : 1843-1874. doi: 10.3934/dcds.2020342
[18]

Li Gang. An optimization detection algorithm for complex intrusion interference signal in mobile wireless network. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1371-1384. doi: 10.3934/dcdss.2019094
[19]

Yi-Kuei Lin, Cheng-Ta Yeh. Reliability optimization of component assignment problem for a multistate network in terms of minimal cuts. Journal of Industrial and Management Optimization, 2011, 7 (1) : 211-227. doi: 10.3934/jimo.2011.7.211
[20]

Konstantin Avrachenkov, Giovanni Neglia, Vikas Vikram Singh. Network formation games with teams. Journal of Dynamics and Games, 2016, 3 (4) : 303-318. doi: 10.3934/jdg.2016016

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (73)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy