Optimal packing of convex polytopes using quasi-phi-functions

Authors

  • A. V. Pankratov A. N. Podgorny Institute of Problems of Mechanical Engineering NAS, Ukraine
  • T. E. Romanova A. N. Podgorny Institute of Problems of Mechanical Engineering NAS, Ukraine
  • A. M. Chugay A. N. Podgorny Institute of Problems of Mechanical Engineering NAS, Ukraine

Keywords:

packing, polytopes, continuous rotations, non-overlapping, allowable distances, quasi-phi-functions, mathematical model, non-linear optimization

Abstract

We study a packing problem of a given collection of convex polytopes into a rectangular container of minimal volume. Continuous rotations and translations of polytopes are allowed. In addition a given minimal allowable distances between polytopes are taking into account. We employ radical free quasi-phi-functions and adjusted quasi-phi-functions to describe placement constraints. The use of quasi-phi-functions, instead of phi-functions, allows us to simplify non-overlapping, as well as, to describe distance constraints, but there is a price to pay: now the optimization has to be performed over a larger set of parameters, including the extra variables used by our new functions. We provide an exact mathematical model of the problem as a nonlinear programming problem. We also develop an efficient solution algorithm which involves a starting point algorithm, using homothetic trasformations of geometric objects and efficient local optimization procedure, which allows us to runtime and memory). We present here a number of examples to demonstrate the efficiency of our methodology.

Author Biographies

A. V. Pankratov, A. N. Podgorny Institute of Problems of Mechanical Engineering NAS

Doctor of Engineering Science

T. E. Romanova, A. N. Podgorny Institute of Problems of Mechanical Engineering NAS

Doctor of Engineering Science

A. M. Chugay, A. N. Podgorny Institute of Problems of Mechanical Engineering NAS

PhD

References

Wаscher, G., Hauner, H., Schumann, H. (2007).”An improved typology of cutting and packing problems”. Eur. J. Oper. Res. 183(3,16): 1109–1130.

Chazelle, B., Edelsbrunner, H., Guibas, L.J. (1989). “The complexity of cutting complexes.” Discr. & Comput. Geom. 4(2): 139–81.

Aladahalli, C., Cagan, J., Shimada, K. (2007). “Objective function effect based pattern search – theoretical framework inspired by 3D component layout.” J. Mech. Design. 129: 243–254.

Cagan, J., Shimada, K., Yin, S. (2002). “A survey of computational approaches to three-dimensional layout problems.” Comp.-Aided Des. 34: 597–611.

Egeblad, J. (2008). “Heuristics for multidimensional packing problems.” PhD Thesis.

Egeblad, J., Nielsen, B.K., Odgaard, A. (2007). “Fast neighborhood search for two- and three-dimensional nesting problems.” Eur. J. Oper. Res. 183(3):1249–1266.

Fasano, G. (2008). “MIP-based heuristic for non-standard 3D-packing problems.” 4OR: Quart. J. Belgian, French and Italian Oper. Res. Soc. 6(3): 291–310.

Gan, M., Gopinathan, N., Jia, X., Williams, R.A. (2004). “Predicting Packing Characteristics of Particles of Arbitrary Shapes.” KONA, 22: 82–93.

Jia, X., Gan, M., Williams, R.A., Rhodes, D. (2007). “Validation of a digital packing algorithm in predicting powder packing densities.” Powder Tech. 174: 10–13.

Korte, A.C.J, Brouwers H.J.H. (2013). “Random packing of digitized particles.” Powder Techn. 233: 319–324.

Li, S.X., Zhao, J. (2009). “Sphere assembly model and relaxation algorithm for packing of non-spherical particles.” Chin. J. Comp. Phys. 26(3): 167–173.

Li, S.X., Zhao, J., Lu, P., Xie, Y. (2010). “Maximum packing densities of basic 3D objects.” Chin. Scien. Bull. 55(2): 114–119.

Sriramya, P., Varthini, P.B. (2012). “A State-of-the -Art Review of Bin Packing Techniques.” Eur. J. Scien. Res. 86(3): 360–364.

Birgin, E.G., Martinez, J.M., Nishihara, F.H., Ronconi, D.P. (2006). “Orthogonal packing of rectagular items within arbitrary convex regions by nonlinear optimization.” Comput. Oper. Res. 33: 3535–3548.

Birgin, E., Martínez, J., Ronconi, D. (2005). “Optimizing the packing of cylinders into a rectangular container: A nonlinear approach.” Eur. J. of Oper. Res. 160 (1): 19–33.

Egeblad, J., Nielsen, B.K., Brazil, M. (2009). “Translational packing of arbitrary polytopes.” http://www.sciencedirect.com/science/journal/09257721">Comp. Geom.http://www.sciencedirect.com/science/journal/09257721/42/4"> 42(4): 269–288.

Fasano, G. A. (2013). “Global Optimization point of view for non-standard packing problems.” J. Glob. Optim. 55(2): 279–299.

Petrov, M.S., Gaidukov, V.V., Kadushnikov, R.M. (2004). ”Numerical method for modelling the microstructure of granular materials.” Powder Metall. and Metal Ceram. 43 (7-8): 330–335.

Torquato, S., Jiao, Y. (2009). “Dense polyhedral packings: Platonic and Archimedean solids.” Phys. Rev. 80: 041104.

Y. Stoyan, N. Gil, G. Scheithauer, A. Pankratov, I. Magdalina (2005). “Packing of convex polytopes into a parallelepiped.” Optimization. 54(2): 215 – 235.

Chernov, N., Stoyan, Y., Romanova, T. (2010). “Mathematical model and efficient algorithms for object packing problem”. Comput. Geom.: Theory and Appl. 43(5): 535–553.

Stoyan, Y., Chugay, А. (2012). “Mathematical modeling of the interaction of non-oriented convex polytopes”. Cyber. and Syst. Anal. 48 (6): 837–845.

StoyanYu., Chugay A. (2011). “Construction of radical free phi-functions for spheres and non-oriented polytopes.” Rep. of NAS of Ukraine. №12: 35-40.

Stoyan Yu,. Pankratov А., Romanova Т., Chernov N. (2014). “Quasi-phi-function for mathematical modelling of geometric objects interactions.” Rep. of NAS of Ukraine 9: 53–57.

Wachter, A., Biegler, L.T. (2006). “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming.” Math. Program. 106 (1): 25–57.

Stoyan, Y., Yaskov, G. (2012). “Packing congruent hyperspheres into a hypersphere” Journal of Global Optimization, 52(4): 855–868 .

Chernov, N., Stoyan, Y., Pankratov, A., Romanova, T. (2014). “Quasi-phi-functions and optimal packing of ellipses.” Subm. to J. of Glob. Optim.

Downloads

Published

2015-07-14

Issue

Vol. 18 No. 2 (2015)

Section

Applied mathematics

License

Copyright (c) 2015 A. V. Pankratov, T. E. Romanova, A. M. Chugay

Creative Commons License

This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

All authors agree with the following conditions:

  • The authors reserve the right to claim authorship of their work and transfer to the journal the right of first publication of the work under the license agreement (the agreement).
  • Authors have a right to conclude independently additional agreement on non-exclusive spreading the work in the form in which it was published by the jpurnal (for example, to place the work in institution repository or to publish as a part of a monograph), providing a link to the first publication of the work in this journal.
  • Journal policy allows authors to place the manuscript in the Internet (for example, in the institution repository or on a personal web sites) both before its submission to the editorial board and during its editorial processing, as this ensures the productive scientific discussion and impact positively on the efficiency and dynamics of citation of published work (see The Effect of Open Access).