January  2014, 10(1): 337-362. doi: 10.3934/jimo.2014.10.337

Towards an optimization theory for deforming dense granular materials: Minimum cost maximum flow solutions

1. 

Department of Mathematics and Statistics, Curtin University, GPO Box U1987 Perth, Western Australia 6845

2. 

Department of Mathematics and Statistics, University of Melbourne, Melbourne, Australia 3010, Australia

Received  February 2013 Revised  July 2013 Published  October 2013

We use concepts and techniques of network optimization theory to gain a better understanding of force transmission in dense granular materials. Specifically, we represent a deforming granular material over the different stages of a quasi-static biaxial compression test as a series of representative flow networks, and analyze force transmission through these networks. The forces in such a material are transmitted through the contacts between the constituent grains. As the sample deforms during the various stages of the biaxial test, these grains rearrange: while many contacts are preserved in this rearrangement process, some new contacts form and some old contacts break. We consider the maximum flow problem and the minimum cost maximum flow (MCMF) problem for the flow networks constructed from this evolving network of grain contacts. We identify the flow network bottleneck and establish the sufficient and necessary conditions for a minimum cut of the maximum flow problem to be unique. We also develop an algorithm to determine the MCMF pathway, i.e. a set of edges that always transmit non-zero flow in every solution of the MCMF problem. The bottlenecks of the flow networks develop in the locality of the persistent shear band, an intensively-studied phenomenon that has long been regarded as the signature failure microstructure for dense granular materials. The cooperative evolution of the most important structural building blocks for force transmission, i.e. the force chains and 3-cycles, is examined with respect to the MCMF pathways. We find that the majority of the particles in the major load-bearing columnar force chains and 3-cycles consistently participate in the MCMF pathways.
Citation: Qun Lin, Antoinette Tordesillas. Towards an optimization theory for deforming dense granular materials: Minimum cost maximum flow solutions. Journal of Industrial & Management Optimization, 2014, 10 (1) : 337-362. doi: 10.3934/jimo.2014.10.337
References:
[1]

R. Arévalo, I. Zuriguel and D. Maza, Topology of the force network in the jamming transition of an isotropically compressed granular packing,, Physical Review E, 81 (2010).   Google Scholar

[2]

D. P. Bertsekas, "Network Optimization: Continuous and Discrete Models (Optimization, Computation, and Control),", Athena Scientific, (1998).   Google Scholar

[3]

J. A. Bondy and U. S. R. Murty, "Graph Theory,", Graduate Texts in Mathematics, (2008).  doi: 10.1007/978-1-84628-970-5.  Google Scholar

[4]

I. Cavarretta and C. O'Sullivan, The mechanics of rigid irregular particles subject to uniaxial compression,, Géotechnique, 62 (2012), 681.   Google Scholar

[5]

J. Duran, "Sands, Powders, and Grains: An Introduction to the Physics of Granular Materials,", Springer-Verlag, (2000).   Google Scholar

[6]

J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problem,, Journal of the Association for Computing Machinery, 19 (1972), 248.   Google Scholar

[7]

A. Garg and R. Tamassia, A new minimum cost flow algorithm with applications to graph drawing,, Graph Drawing, 1190 (1997), 201.   Google Scholar

[8]

M. Gerdts and M. Kunkel, A nonsmooth Newton's method for discretized optimal control problems with state and control constraints,, Journal of Industrial and Management Optimization, 4 (2008), 247.  doi: 10.3934/jimo.2008.4.247.  Google Scholar

[9]

F. S. Hillier and G. J. Lieberman, "Introduction to Operations Research,", McGraw-Hill, (2005).   Google Scholar

[10]

D. Jungnickel, "Graphs, Networks and Algorithms,", Third edition. Algorithms and Computation in Mathematics, (2008).  doi: 10.1007/978-3-540-72780-4.  Google Scholar

[11]

Q. Lin and A. Tordesillas, Granular rheology: Fine tuned for optimal efficiency?, Proceedings of the 23rd International Congress of Theoretical and Applied Mechanics, (2012).   Google Scholar

[12]

R. C. Loxton, K. L. Teo, V. Rehbock and K. F. C. Yiu, Optimal control problems with a continuous inequality constraint on the state and the control,, Automatica J. IFAC, 45 (2009), 2250.  doi: 10.1016/j.automatica.2009.05.029.  Google Scholar

[13]

H. B. Mühlhaus and I. Vardoulakis, The thickness of shear bands in granular materials,, Géotechnique, 37 (1987), 271.   Google Scholar

[14]

M. Oda and H. Kazama, Microstructure of shear bands and its relation to the mechanisms of dilatancy and failure of dense granular soils,, Géotechnique, 48 (1998), 465.   Google Scholar

[15]

M. Oda, J. Konishi and S. Nemat-Nasser, Experimental micromechanical evaluation of strength of granular materials: Effects of particle rolling,, Mechanics of Materials, 1 (1982), 269.   Google Scholar

[16]

A. Ord and B. E. Hobbs, Fracture pattern formation in frictional, cohesive, granular material,, Philosophical Transactions of the Royal Society A, 368 (2010), 95.   Google Scholar

[17]

J. Paavilainen and J. Tuhkuri, Pressure distributions and force chains during simulated ice rubbling against sloped structures,, Cold Regions Science and Technology, 85 (2013), 157.   Google Scholar

[18]

J. M. Padbidri, C. M. Hansen, S. D. Mesarovic and B. Muhunthan, Length scale for transmission of rotations in dense granular materials,, Journal of Applied Mechanics, 79 (2012).   Google Scholar

[19]

F. Radjai, D. E. Wolf, M. Jean and J. J. Moreau, Bimodal character of stress transmission in granular packings,, Physical Review Letters, 80 (1998), 61.   Google Scholar

[20]

A. L. Rechenmacher, S. Abedi, O. Chupin and A. D. Orlando, Characterization of mesoscale instabilities in localized granular shear using digital image correlation,, Acta Geotechnica, 6 (2011), 205.   Google Scholar

[21]

A. Tordesillas, Force chain buckling, unjamming transitions and shear banding in dense granular assemblies,, Philosophical Magazine, 87 (2007), 4987.   Google Scholar

[22]

A. Tordesillas, A. Cramer and D. M. Walker, Minimum cut and shear bands,, Powders & Grains AIP Conference Proceedings 1542 (2013), 1542 (2013), 507.   Google Scholar

[23]

A. Tordesillas, Q. Lin, J. Zhang, R. P. Behringer and J. Shi, Structural stability and jamming of self-organized cluster conformations in dense granular materials,, Journal of the Mechanics and Physics of Solids, 59 (2011), 265.   Google Scholar

[24]

A. Tordesillas, D. M. Walker, E. Andò and G. Viggiani, Revisiting localised deformation in sand with complex systems,, Proceedings of the Royal Society of London Series A, (2013).   Google Scholar

[25]

A. Tordesillas, D. M. Walker, G. Froyland, J. Zhang and R. P. Behringer, Transition dynamics and magic-number-like behavior of frictional granular clusters,, Physical Review E, 86 (2012).   Google Scholar

[26]

A. Tordesillas, D. M. Walker and Q. Lin, Force cycles and force chains,, Physical Review E, 81 (2010).   Google Scholar

[27]

D. M. Walker, A. Tordesillas, S. Pucilowski, Q. Lin, A. L. Rechenmacher and S. Abedi, Analysis of grain-scale measurements of sand using kinematical complex networks,, International Journal of Bifurcation and Chaos, 22 (2012).  doi: 10.1142/S021812741230042X.  Google Scholar

[28]

L. Y. Wang, W. H. Gui, K. L. Teo, R. Loxton and C. H. Yang, Time delayed optimal control problems with multiple characteristic time points: Computation and industrial applications,, Journal of Industrial and Management Optimization, 5 (2009), 705.  doi: 10.3934/jimo.2009.5.705.  Google Scholar

[29]

Y. Zhao and M. A. Stadtherr, Rigorous global optimization for dynamic systems subject to inequality path constraints,, Industrial and Engineering Chemistry Research, 50 (2011), 12678.   Google Scholar

show all references

References:
[1]

R. Arévalo, I. Zuriguel and D. Maza, Topology of the force network in the jamming transition of an isotropically compressed granular packing,, Physical Review E, 81 (2010).   Google Scholar

[2]

D. P. Bertsekas, "Network Optimization: Continuous and Discrete Models (Optimization, Computation, and Control),", Athena Scientific, (1998).   Google Scholar

[3]

J. A. Bondy and U. S. R. Murty, "Graph Theory,", Graduate Texts in Mathematics, (2008).  doi: 10.1007/978-1-84628-970-5.  Google Scholar

[4]

I. Cavarretta and C. O'Sullivan, The mechanics of rigid irregular particles subject to uniaxial compression,, Géotechnique, 62 (2012), 681.   Google Scholar

[5]

J. Duran, "Sands, Powders, and Grains: An Introduction to the Physics of Granular Materials,", Springer-Verlag, (2000).   Google Scholar

[6]

J. Edmonds and R. M. Karp, Theoretical improvements in algorithmic efficiency for network flow problem,, Journal of the Association for Computing Machinery, 19 (1972), 248.   Google Scholar

[7]

A. Garg and R. Tamassia, A new minimum cost flow algorithm with applications to graph drawing,, Graph Drawing, 1190 (1997), 201.   Google Scholar

[8]

M. Gerdts and M. Kunkel, A nonsmooth Newton's method for discretized optimal control problems with state and control constraints,, Journal of Industrial and Management Optimization, 4 (2008), 247.  doi: 10.3934/jimo.2008.4.247.  Google Scholar

[9]

F. S. Hillier and G. J. Lieberman, "Introduction to Operations Research,", McGraw-Hill, (2005).   Google Scholar

[10]

D. Jungnickel, "Graphs, Networks and Algorithms,", Third edition. Algorithms and Computation in Mathematics, (2008).  doi: 10.1007/978-3-540-72780-4.  Google Scholar

[11]

Q. Lin and A. Tordesillas, Granular rheology: Fine tuned for optimal efficiency?, Proceedings of the 23rd International Congress of Theoretical and Applied Mechanics, (2012).   Google Scholar

[12]

R. C. Loxton, K. L. Teo, V. Rehbock and K. F. C. Yiu, Optimal control problems with a continuous inequality constraint on the state and the control,, Automatica J. IFAC, 45 (2009), 2250.  doi: 10.1016/j.automatica.2009.05.029.  Google Scholar

[13]

H. B. Mühlhaus and I. Vardoulakis, The thickness of shear bands in granular materials,, Géotechnique, 37 (1987), 271.   Google Scholar

[14]

M. Oda and H. Kazama, Microstructure of shear bands and its relation to the mechanisms of dilatancy and failure of dense granular soils,, Géotechnique, 48 (1998), 465.   Google Scholar

[15]

M. Oda, J. Konishi and S. Nemat-Nasser, Experimental micromechanical evaluation of strength of granular materials: Effects of particle rolling,, Mechanics of Materials, 1 (1982), 269.   Google Scholar

[16]

A. Ord and B. E. Hobbs, Fracture pattern formation in frictional, cohesive, granular material,, Philosophical Transactions of the Royal Society A, 368 (2010), 95.   Google Scholar

[17]

J. Paavilainen and J. Tuhkuri, Pressure distributions and force chains during simulated ice rubbling against sloped structures,, Cold Regions Science and Technology, 85 (2013), 157.   Google Scholar

[18]

J. M. Padbidri, C. M. Hansen, S. D. Mesarovic and B. Muhunthan, Length scale for transmission of rotations in dense granular materials,, Journal of Applied Mechanics, 79 (2012).   Google Scholar

[19]

F. Radjai, D. E. Wolf, M. Jean and J. J. Moreau, Bimodal character of stress transmission in granular packings,, Physical Review Letters, 80 (1998), 61.   Google Scholar

[20]

A. L. Rechenmacher, S. Abedi, O. Chupin and A. D. Orlando, Characterization of mesoscale instabilities in localized granular shear using digital image correlation,, Acta Geotechnica, 6 (2011), 205.   Google Scholar

[21]

A. Tordesillas, Force chain buckling, unjamming transitions and shear banding in dense granular assemblies,, Philosophical Magazine, 87 (2007), 4987.   Google Scholar

[22]

A. Tordesillas, A. Cramer and D. M. Walker, Minimum cut and shear bands,, Powders & Grains AIP Conference Proceedings 1542 (2013), 1542 (2013), 507.   Google Scholar

[23]

A. Tordesillas, Q. Lin, J. Zhang, R. P. Behringer and J. Shi, Structural stability and jamming of self-organized cluster conformations in dense granular materials,, Journal of the Mechanics and Physics of Solids, 59 (2011), 265.   Google Scholar

[24]

A. Tordesillas, D. M. Walker, E. Andò and G. Viggiani, Revisiting localised deformation in sand with complex systems,, Proceedings of the Royal Society of London Series A, (2013).   Google Scholar

[25]

A. Tordesillas, D. M. Walker, G. Froyland, J. Zhang and R. P. Behringer, Transition dynamics and magic-number-like behavior of frictional granular clusters,, Physical Review E, 86 (2012).   Google Scholar

[26]

A. Tordesillas, D. M. Walker and Q. Lin, Force cycles and force chains,, Physical Review E, 81 (2010).   Google Scholar

[27]

D. M. Walker, A. Tordesillas, S. Pucilowski, Q. Lin, A. L. Rechenmacher and S. Abedi, Analysis of grain-scale measurements of sand using kinematical complex networks,, International Journal of Bifurcation and Chaos, 22 (2012).  doi: 10.1142/S021812741230042X.  Google Scholar

[28]

L. Y. Wang, W. H. Gui, K. L. Teo, R. Loxton and C. H. Yang, Time delayed optimal control problems with multiple characteristic time points: Computation and industrial applications,, Journal of Industrial and Management Optimization, 5 (2009), 705.  doi: 10.3934/jimo.2009.5.705.  Google Scholar

[29]

Y. Zhao and M. A. Stadtherr, Rigorous global optimization for dynamic systems subject to inequality path constraints,, Industrial and Engineering Chemistry Research, 50 (2011), 12678.   Google Scholar

[1]

Sihem Guerarra. Maximum and minimum ranks and inertias of the Hermitian parts of the least rank solution of the matrix equation AXB = C. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 75-86. doi: 10.3934/naco.2020016

[2]

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

[3]

Bernard Bonnard, Jérémy Rouot. Geometric optimal techniques to control the muscular force response to functional electrical stimulation using a non-isometric force-fatigue model. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020032

[4]

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

[5]

Giuseppina Guatteri, Federica Masiero. Stochastic maximum principle for problems with delay with dependence on the past through general measures. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020048

[6]

Tien-Yu Lin, Bhaba R. Sarker, Chien-Jui Lin. An optimal setup cost reduction and lot size for economic production quantity model with imperfect quality and quantity discounts. Journal of Industrial & Management Optimization, 2021, 17 (1) : 467-484. doi: 10.3934/jimo.2020043

[7]

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

[8]

Stefan Doboszczak, Manil T. Mohan, Sivaguru S. Sritharan. Pontryagin maximum principle for the optimal control of linearized compressible navier-stokes equations with state constraints. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020110

[9]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158

[10]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[11]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[12]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098

[13]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[14]

Yi An, Bo Li, Lei Wang, Chao Zhang, Xiaoli Zhou. Calibration of a 3D laser rangefinder and a camera based on optimization solution. Journal of Industrial & Management Optimization, 2021, 17 (1) : 427-445. doi: 10.3934/jimo.2019119

[15]

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

[16]

Ripeng Huang, Shaojian Qu, Xiaoguang Yang, Zhimin Liu. Multi-stage distributionally robust optimization with risk aversion. Journal of Industrial & Management Optimization, 2021, 17 (1) : 233-259. doi: 10.3934/jimo.2019109

[17]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[18]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[19]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[20]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (33)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]