• 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

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.
Citation: I-Lin Wang, Ju-Chun Lin. A compaction scheme and generator for distribution networks. Journal of Industrial & 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, (1993).   Google Scholar

[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), (1993), 1.   Google Scholar

[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.  doi: 10.1007/s11590-011-0356-5.  Google Scholar

[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.  doi: 10.1145/62038.62041.  Google Scholar

[5]

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

[6]

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

[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.   Google Scholar

[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.  doi: 10.1080/1055678031000152079.  Google Scholar

[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.  doi: 10.1007/BF02288321.  Google Scholar

[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.   Google Scholar

[11]

J. Koene, Minimal Cost Flow in Processing Networks, a Primal Approach,, PhD thesis, (1983).   Google Scholar

[12]

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

[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.  doi: 10.1016/j.cie.2013.06.019.  Google Scholar

[14]

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

[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.  doi: 10.1287/inte.31.1.108.9693.  Google Scholar

[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.  doi: 10.3934/jimo.2006.2.237.  Google Scholar

[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.  doi: 10.1287/opre.2013.1215.  Google Scholar

[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.  doi: 10.3934/jimo.2009.5.929.  Google Scholar

[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.   Google Scholar

show all references

References:
[1]

R. K. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms and Applications,, Prentice Hall, (1993).   Google Scholar

[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), (1993), 1.   Google Scholar

[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.  doi: 10.1007/s11590-011-0356-5.  Google Scholar

[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.  doi: 10.1145/62038.62041.  Google Scholar

[5]

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

[6]

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

[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.   Google Scholar

[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.  doi: 10.1080/1055678031000152079.  Google Scholar

[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.  doi: 10.1007/BF02288321.  Google Scholar

[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.   Google Scholar

[11]

J. Koene, Minimal Cost Flow in Processing Networks, a Primal Approach,, PhD thesis, (1983).   Google Scholar

[12]

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

[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.  doi: 10.1016/j.cie.2013.06.019.  Google Scholar

[14]

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

[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.  doi: 10.1287/inte.31.1.108.9693.  Google Scholar

[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.  doi: 10.3934/jimo.2006.2.237.  Google Scholar

[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.  doi: 10.1287/opre.2013.1215.  Google Scholar

[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.  doi: 10.3934/jimo.2009.5.929.  Google Scholar

[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.   Google Scholar

[1]

Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011

[2]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

[3]

Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021002

[4]

Rajendra K C Khatri, Brendan J Caseria, Yifei Lou, Guanghua Xiao, Yan Cao. Automatic extraction of cell nuclei using dilated convolutional network. Inverse Problems & Imaging, 2021, 15 (1) : 27-40. doi: 10.3934/ipi.2020049

[5]

Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060

[6]

Yu-Jhe Huang, Zhong-Fu Huang, Jonq Juang, Yu-Hao Liang. Flocking of non-identical Cucker-Smale models on general coupling network. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1111-1127. doi: 10.3934/dcdsb.2020155

[7]

Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077

[8]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020391

[9]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013

[10]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[11]

Imam Wijaya, Hirofumi Notsu. Stability estimates and a Lagrange-Galerkin scheme for a Navier-Stokes type model of flow in non-homogeneous porous media. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1197-1212. doi: 10.3934/dcdss.2020234

[12]

Kalikinkar Mandal, Guang Gong. On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125

[13]

Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071

[14]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004

[15]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1

[16]

Shuxing Chen, Jianzhong Min, Yongqian Zhang. Weak shock solution in supersonic flow past a wedge. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 115-132. doi: 10.3934/dcds.2009.23.115

[17]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465

[18]

François Dubois. Third order equivalent equation of lattice Boltzmann scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 221-248. doi: 10.3934/dcds.2009.23.221

[19]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[20]

Caterina Balzotti, Simone Göttlich. A two-dimensional multi-class traffic flow model. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020034

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]