# American Institute of Mathematical Sciences

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). [2] D. P. Bertsekas, "Network Optimization: Continuous and Discrete Models (Optimization, Computation, and Control),", Athena Scientific, (1998). [3] J. A. Bondy and U. S. R. Murty, "Graph Theory,", Graduate Texts in Mathematics, (2008). doi: 10.1007/978-1-84628-970-5. [4] I. Cavarretta and C. O'Sullivan, The mechanics of rigid irregular particles subject to uniaxial compression,, Géotechnique, 62 (2012), 681. [5] J. Duran, "Sands, Powders, and Grains: An Introduction to the Physics of Granular Materials,", Springer-Verlag, (2000). [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. [7] A. Garg and R. Tamassia, A new minimum cost flow algorithm with applications to graph drawing,, Graph Drawing, 1190 (1997), 201. [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. [9] F. S. Hillier and G. J. Lieberman, "Introduction to Operations Research,", McGraw-Hill, (2005). [10] D. Jungnickel, "Graphs, Networks and Algorithms,", Third edition. Algorithms and Computation in Mathematics, (2008). doi: 10.1007/978-3-540-72780-4. [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). [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. [13] H. B. Mühlhaus and I. Vardoulakis, The thickness of shear bands in granular materials,, Géotechnique, 37 (1987), 271. [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. [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. [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. [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. [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). [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. [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. [21] A. Tordesillas, Force chain buckling, unjamming transitions and shear banding in dense granular assemblies,, Philosophical Magazine, 87 (2007), 4987. [22] A. Tordesillas, A. Cramer and D. M. Walker, Minimum cut and shear bands,, Powders & Grains AIP Conference Proceedings 1542 (2013), 1542 (2013), 507. [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. [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). [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). [26] A. Tordesillas, D. M. Walker and Q. Lin, Force cycles and force chains,, Physical Review E, 81 (2010). [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. [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. [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.

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). [2] D. P. Bertsekas, "Network Optimization: Continuous and Discrete Models (Optimization, Computation, and Control),", Athena Scientific, (1998). [3] J. A. Bondy and U. S. R. Murty, "Graph Theory,", Graduate Texts in Mathematics, (2008). doi: 10.1007/978-1-84628-970-5. [4] I. Cavarretta and C. O'Sullivan, The mechanics of rigid irregular particles subject to uniaxial compression,, Géotechnique, 62 (2012), 681. [5] J. Duran, "Sands, Powders, and Grains: An Introduction to the Physics of Granular Materials,", Springer-Verlag, (2000). [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. [7] A. Garg and R. Tamassia, A new minimum cost flow algorithm with applications to graph drawing,, Graph Drawing, 1190 (1997), 201. [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. [9] F. S. Hillier and G. J. Lieberman, "Introduction to Operations Research,", McGraw-Hill, (2005). [10] D. Jungnickel, "Graphs, Networks and Algorithms,", Third edition. Algorithms and Computation in Mathematics, (2008). doi: 10.1007/978-3-540-72780-4. [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). [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. [13] H. B. Mühlhaus and I. Vardoulakis, The thickness of shear bands in granular materials,, Géotechnique, 37 (1987), 271. [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. [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. [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. [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. [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). [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. [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. [21] A. Tordesillas, Force chain buckling, unjamming transitions and shear banding in dense granular assemblies,, Philosophical Magazine, 87 (2007), 4987. [22] A. Tordesillas, A. Cramer and D. M. Walker, Minimum cut and shear bands,, Powders & Grains AIP Conference Proceedings 1542 (2013), 1542 (2013), 507. [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. [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). [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). [26] A. Tordesillas, D. M. Walker and Q. Lin, Force cycles and force chains,, Physical Review E, 81 (2010). [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. [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. [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.
 [1] I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929 [2] K. A. Ariyawansa, Leonid Berlyand, Alexander Panchenko. A network model of geometrically constrained deformations of granular materials. Networks & Heterogeneous Media, 2008, 3 (1) : 125-148. doi: 10.3934/nhm.2008.3.125 [3] Dušan M. Stipanović, Claire J. Tomlin, George Leitmann. A note on monotone approximations of minimum and maximum functions and multi-objective problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 487-493. doi: 10.3934/naco.2011.1.487 [4] José Joaquín Bernal, Diana H. Bueno-Carreño, Juan Jacobo Simón. Cyclic and BCH codes whose minimum distance equals their maximum BCH bound. Advances in Mathematics of Communications, 2016, 10 (2) : 459-474. doi: 10.3934/amc.2016018 [5] R.L. Sheu, M.J. Ting, I.L. Wang. Maximum flow problem in the distribution network. Journal of Industrial & Management Optimization, 2006, 2 (3) : 237-254. doi: 10.3934/jimo.2006.2.237 [6] Cristian Enache. Maximum and minimum principles for a class of Monge-Ampère equations in the plane, with applications to surfaces of constant Gauss curvature. Communications on Pure & Applied Analysis, 2014, 13 (3) : 1347-1359. doi: 10.3934/cpaa.2014.13.1347 [7] David Auger, Irène Charon, Iiro Honkala, Olivier Hudry, Antoine Lobstein. Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs. Advances in Mathematics of Communications, 2009, 3 (1) : 97-114. doi: 10.3934/amc.2009.3.97 [8] Rafael G. L. D'Oliveira, Marcelo Firer. Minimum dimensional Hamming embeddings. Advances in Mathematics of Communications, 2017, 11 (2) : 359-366. doi: 10.3934/amc.2017029 [9] Fei Meng, Xiao-Ping Yang. Elastic limit and vanishing external force for granular systems. Kinetic & Related Models, 2019, 12 (1) : 159-176. doi: 10.3934/krm.2019007 [10] Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195 [11] Victor Berdichevsky. Distribution of minimum values of stochastic functionals. Networks & Heterogeneous Media, 2008, 3 (3) : 437-460. doi: 10.3934/nhm.2008.3.437 [12] Giovanni Colombo, Khai T. Nguyen. On the minimum time function around the origin. Mathematical Control & Related Fields, 2013, 3 (1) : 51-82. doi: 10.3934/mcrf.2013.3.51 [13] Christopher Bose, Rua Murray. Minimum 'energy' approximations of invariant measures for nonsingular transformations. Discrete & Continuous Dynamical Systems - A, 2006, 14 (3) : 597-615. doi: 10.3934/dcds.2006.14.597 [14] Uwe Helmke, Michael Schönlein. Minimum sensitivity realizations of networks of linear systems. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 241-262. doi: 10.3934/naco.2016010 [15] Chuang Peng. Minimum degrees of polynomial models on time series. Conference Publications, 2005, 2005 (Special) : 720-729. doi: 10.3934/proc.2005.2005.720 [16] Monica Motta. Minimum time problem with impulsive and ordinary controls. Discrete & Continuous Dynamical Systems - A, 2018, 38 (11) : 5781-5809. doi: 10.3934/dcds.2018252 [17] 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 & Optimization, 2019, 9 (2) : 113-132. doi: 10.3934/naco.2019009 [18] Ugo Boscain, Thomas Chambrion, Grégoire Charlot. Nonisotropic 3-level quantum systems: complete solutions for minimum time and minimum energy. Discrete & Continuous Dynamical Systems - B, 2005, 5 (4) : 957-990. doi: 10.3934/dcdsb.2005.5.957 [19] Daniele Bartoli, Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. The minimum order of complete caps in $PG(4,4)$. Advances in Mathematics of Communications, 2011, 5 (1) : 37-40. doi: 10.3934/amc.2011.5.37 [20] Carlos Munuera, Fernando Torres. A note on the order bound on the minimum distance of AG codes and acute semigroups. Advances in Mathematics of Communications, 2008, 2 (2) : 175-181. doi: 10.3934/amc.2008.2.175

2017 Impact Factor: 0.994