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 & 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]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[2]

Ziteng Wang, Shu-Cherng Fang, Wenxun Xing. On constraint qualifications: Motivation, design and inter-relations. Journal of Industrial & Management Optimization, 2013, 9 (4) : 983-1001. doi: 10.3934/jimo.2013.9.983
[3]

Shu-Yu Hsu. Existence and properties of ancient solutions of the Yamabe flow. Discrete & Continuous Dynamical Systems - A, 2018, 38 (1) : 91-129. doi: 10.3934/dcds.2018005
[4]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[5]

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
[6]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[7]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[8]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[9]

Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20.

[10]

Wolf-Jüergen Beyn, Janosch Rieger. The implicit Euler scheme for one-sided Lipschitz differential inclusions. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 409-428. doi: 10.3934/dcdsb.2010.14.409
[11]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009
[12]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[13]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1
[14]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044
[15]

Chih-Chiang Fang. Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020127

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences