{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:41:06Z","timestamp":1760060466625,"version":"build-2065373602"},"reference-count":32,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T00:00:00Z","timestamp":1756857600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>Typically, dimension stones, commonly called stone blocks, are cut into multiple small cuboid stones so that multiple sculptures can be produced. To use the stone block as efficiently as possible, it is essential to pack these small cuboids in each stone block as efficiently as possible while satisfying the limitations of the machining. This paper describes methods for packing and cutting stone blocks using nonlinear programming that generate sets of trees, which are also called forests, that decide the packing layout of the small cuboids inside the block. The containers and elements have their own prices and values, respectively. The elements can be translated to the corners of the containers or to the corners of the elements that are already in the containers, if the elements are not outside the containers after the translation. Then, the problem can be interpreted as finding the best forest that packs the elements as efficiently as possible at the lowest total price of containers, which is a subset of all containers. The formula for the score that defines the compactness of the packing is in this paper. The user can define the number of forests so that parallel computing methods can be applied. Each forest is generated randomly. Two different packing methods are introduced: simple packing and slab packing. Simple packing is based on a non-guillotine cutting method and slab packing is a guillotine cutting method for realistic scenarios, such as scenarios with machining limitations. By using this method, it is possible to plan the cutting in a digital environment, which is not possible when using the traditional method with physical templates. Furthermore, by restricting the rotation of the elements, it is possible to make the elements follow the horizontal vein direction of the stone blocks, which is a common vein direction in travertine.<\/jats:p>","DOI":"10.3390\/computation13090211","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T08:04:15Z","timestamp":1756886655000},"page":"211","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Packing and Cutting Stone Blocks Based on the Nonlinear Programming of Tree Cases"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3816-7714","authenticated-orcid":false,"given":"Taeyong","family":"Kim","sequence":"first","affiliation":[{"name":"Quarra Stone Company LLC, Madison, WI 53714, USA"}]}],"member":"1968","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"ref_1","first-page":"1879","article-title":"Black dimensional stones: Geology, technical properties and deposit characterization of the dolerites from Uruguay","volume":"63","author":"Stein","year":"2010","journal-title":"Environ. Earth Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1911","DOI":"10.1007\/s12665-010-0825-7","article-title":"Optimized extraction of dimension stone blocks","volume":"63","author":"Mosch","year":"2010","journal-title":"Environ. Earth Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Jalalian, M.H., Bagherpour, R., and Khoshouei, M. (2021). Wastes production in dimension stones industry: Resources, factors, and solutions to reduce them. Environ. Earth Sci., 80.","DOI":"10.1007\/s12665-021-09890-2"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.ejor.2006.03.011","article-title":"Complete and robust no-fit polygon generation for the irregular stock cutting problem","volume":"179","author":"Burke","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Luo, Q., and Rao, Y. (2022). Improved Sliding Algorithm for Generating No-Fit Polygon in the 2D Irregular Packing Problem. Mathematics, 10.","DOI":"10.3390\/math10162941"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1109\/56.2083","article-title":"A fast procedure for computing the distance between complex objects in three-dimensional space","volume":"4","author":"Gilbert","year":"1988","journal-title":"IEEE J. Robot. Autom."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Gao, W. (2024, January 14\u201318). Efficient Incremental Penetration Depth Estimation between Convex Geometries. Proceedings of the 2024 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), Abu Dhabi, United Arab Emirates.","DOI":"10.1109\/IROS58592.2024.10801965"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"242","DOI":"10.14733\/cadaps.2021.242-257","article-title":"2D Irregular Optimization Nesting Method based on Adaptive Probabilistic Genetic Simulated Annealing Algorithm","volume":"18","author":"Qin","year":"2020","journal-title":"Comput.-Aided Des. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/j.disopt.2009.04.002","article-title":"An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem","volume":"6","author":"Imamichi","year":"2009","journal-title":"Discret. Optim."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"168781401665208","DOI":"10.1177\/1687814016652080","article-title":"Visual nesting system for irregular cutting-stock problem based on rubber band packing algorithm","volume":"8","author":"Liao","year":"2016","journal-title":"Adv. Mech. Eng."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ibaraki, T., Imahori, S., and Yagiura, M. (2008). Hybrid Metaheuristics for Packing Problems. Studies in Computational Intelligence, Springer.","DOI":"10.1007\/978-3-540-78295-7_7"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Amaro Junior, B., Santos, M.C., de Carvalho, G.N., de Ara\u00fajo, L.J.P., and Pinheiro, P.R. (2021). Metaheuristics for the Minimum Time Cut Path Problem with Different Cutting and Sliding Speeds. Algorithms, 14.","DOI":"10.3390\/a14110305"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1016\/j.ifacol.2015.06.131","article-title":"Two-Phase Approach to the Nesting problem with continuous rotations","volume":"48","author":"Rocha","year":"2015","journal-title":"IFAC-PapersOnLine"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/j.cor.2011.03.011","article-title":"Algorithms for 3D guillotine cutting problems: Unbounded knapsack, cutting stock and strip packing","volume":"39","author":"Miyazawa","year":"2012","journal-title":"Comput. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"114257","DOI":"10.1016\/j.eswa.2020.114257","article-title":"Three-dimensional guillotine cutting problems with constrained patterns: MILP formulations and a bottom-up algorithm","volume":"168","author":"Martin","year":"2020","journal-title":"Expert Syst. Appl."},{"key":"ref_16","unstructured":"Imamichi, T. (2009). Nonlinear Programming Based Algorithms to Cutting and Packing Problems. [Ph.D. Thesis, Kyoto University]."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1287\/ijoc.1110.0478","article-title":"A New Graph-Theoretical Model for the Guillotine-Cutting Problem","volume":"25","author":"Clautiaux","year":"2013","journal-title":"INFORMS J. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"1999","DOI":"10.1016\/j.cor.2010.01.017","article-title":"Multi-dimensional bin packing problems with guillotine constraints","volume":"37","author":"Amossen","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1080\/14786445708642275","article-title":"XXVIII. On the theory of the analytical forms called trees","volume":"13","author":"Esq","year":"1857","journal-title":"Lond. Edinb. Dublin Philos. Mag. J. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Cayley, A. (2009). A theorem on trees. The Collected Mathematical Papers, Cambridge University Press.","DOI":"10.1017\/CBO9780511703768"},{"key":"ref_21","first-page":"73","article-title":"Tree-based Machine Learning Methods for Survey Research","volume":"13","author":"Kern","year":"2019","journal-title":"DOAJ Dir. Open Access J."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Koller, D., Megiddo, N., and von Stengel, B. (1994, January 23\u201325). Fast algorithms for finding randomized strategies in game trees. Proceedings of the 26th ACM Symposium on the Theory of Computing, Montreal, QC, Canada.","DOI":"10.1145\/195058.195451"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s10107-020-01614-x","article-title":"Electrical flows over spanning trees","volume":"196","author":"Gupta","year":"2021","journal-title":"Math. Program."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Shasha, D., Wang, J.T.L., and Giugno, R. (2002, January 3\u20135). Algorithmics and applications of tree and graph searching. Proceedings of the Twenty-First ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems\u2014PODS\u201902, Madison, WI, USA.","DOI":"10.1145\/543619.543620"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1287\/opre.25.1.30","article-title":"An Algorithm for Two-Dimensional Cutting Problems","volume":"25","author":"Christofides","year":"1977","journal-title":"Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1147\/rd.165.0462","article-title":"Recursive Computational Procedure for Two-dimensional Stock Cutting","volume":"16","author":"Herz","year":"1972","journal-title":"IBM J. Res. Dev."},{"key":"ref_27","first-page":"1","article-title":"Fast oriented bounding box optimization on the rotation group SO (3,R)","volume":"30","author":"Chang","year":"2011","journal-title":"ACM Trans. Graph."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1130\/G33286.1","article-title":"How travertine veins grow from top to bottom and lift the rocks above them: The effect of crystallization force","volume":"40","author":"Gratier","year":"2012","journal-title":"Geology"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.marpetgeo.2017.03.014","article-title":"Facies character and depositional architecture of hydrothermal travertine slope aprons (Pleistocene, Acquasanta Terme, Central Italy)","volume":"87","author":"Capezzuoli","year":"2017","journal-title":"Mar. Pet. Geol."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.sedgeo.2013.05.018","article-title":"Comparison of the Quaternary travertine sites in the Denizli extensional basin based on their depositional and geochemical data","volume":"294","author":"Kele","year":"2013","journal-title":"Sediment. Geol."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"684","DOI":"10.1016\/j.jclepro.2019.03.309","article-title":"Life Cycle Inventory of techniques for stone quarrying, cutting and finishing: Contribution to fill data gaps","volume":"225","author":"Bianco","year":"2019","journal-title":"J. Clean. Prod."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"516","DOI":"10.3390\/mining3030029","article-title":"A Review of Dimension Stone Extraction Methods","volume":"3","author":"Samarakoon","year":"2023","journal-title":"Mining"}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/9\/211\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:38:22Z","timestamp":1760035102000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/13\/9\/211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,3]]},"references-count":32,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2025,9]]}},"alternative-id":["computation13090211"],"URL":"https:\/\/doi.org\/10.3390\/computation13090211","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2025,9,3]]}}}