{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T06:31:55Z","timestamp":1791354715932,"version":"4.3.1"},"reference-count":20,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We proposed the method that translates the two-dimensional CSP for minimizing the number of cuts to the Ising model. After that, we conducted computer experiments of the proposed model using the benchmark problem. From the above, the following results are obtained. (1) The proposed Ising model adequately represents the target problem. (2) Acceptance rates were as low as 0.2% to 9.8% and from 21.8% to 49.4%. (3) Error rates from optimal solution were as broad as 0% to 25.9%. For future work, we propose the following changes: (1) Improve the Hamiltonian for constraints. (2) Improve the proposed model to adjust more complex two-dimensional CSP and reduce the number of spins when it deals with large materials and components. (3) Conduct experiments using a quantum annealer.<\/jats:p>","DOI":"10.3390\/a14060182","type":"journal-article","created":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T14:16:04Z","timestamp":1623248164000},"page":"182","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem"],"prefix":"10.3390","volume":"14","author":[{"given":"Hiroshi","family":"Arai","sequence":"first","affiliation":[{"name":"Graduate School of Science and Engineering, Ibaraki University, 2-1-1, Hitachi-shi 316-8511, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0879-6528","authenticated-orcid":false,"given":"Harumi","family":"Haraguchi","sequence":"additional","affiliation":[{"name":"Graduate School of Science and Engineering, Ibaraki University, 2-1-1, Hitachi-shi 316-8511, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,6,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1137\/0209062","article-title":"Performance bounds for level oriented two-dimensional packing algorithms","volume":"9","author":"Coffman","year":"1980","journal-title":"SIAM J. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Mumford-Valenzuela, C.L., Vick, J., and Wang, P.Y. (2003). Heuristic for Large Strip Packing Problems with Guillotine Patterns: An Empirical Study. Proceedings of 4th Metaheuristics: Computer Decision-Making, Applied Optimization, Springer.","DOI":"10.1007\/978-1-4757-4137-7_24"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Voss, S., Martello, S., Osman, I.H., and Roucairol, C. (1998). Neighborhood Search Algorithm for the Guillotine Non-Oriented Two-Dimensional Bin Packing Problem. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-5775-3"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1137\/0209064","article-title":"Orthogonal packing in two dimensions","volume":"9","author":"Baker","year":"1980","journal-title":"SIAM J. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1109\/TC.1983.1676307","article-title":"The bottom-left bin-packing heuristic: An efficient implementation","volume":"c-32","author":"Chazelle","year":"1983","journal-title":"IEEE Trans. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"2295","DOI":"10.1016\/j.cor.2008.09.004","article-title":"A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Coloring and Bin Packing","volume":"36","author":"Lewi","year":"2009","journal-title":"Comput. Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0898-1221(94)90077-9","article-title":"Bin-packing by simulated annealing","volume":"27","author":"Rao","year":"1994","journal-title":"Comput. Math. Appl."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF00226291","article-title":"A hybrid grouping genetic algorithm for bin packing","volume":"2","author":"Falkenauer","year":"1996","journal-title":"J. Heuristics"},{"key":"ref_9","first-page":"253","article-title":"Application of Genetic Algorithm for the Bin Packing Problem with a New Representation Scheme","volume":"4","author":"Mohamadi","year":"2010","journal-title":"Math. Sci."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Laabadi, S., Naimi, M., El Amri, H., and Achchab, B. (2019). A Crow Search-Based Genetic Algorithm for Solving Two-Dimensional Bin Packing Problem. Joint German\/Austrian Conference on Artificial Intelligence, Springer.","DOI":"10.1007\/978-3-030-30179-8_17"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/S0377-2217(99)00357-4","article-title":"An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem","volume":"128","author":"Hopper","year":"2001","journal-title":"Eur. J. Oper. Res."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0377-2217(94)90212-7","article-title":"Value considerations in three-dimensional packing\u2014A heuristic procedure using the fractional knapsack problem","volume":"74","author":"Bidhu","year":"1994","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","unstructured":"Umetani, S. (1999). Formulation and Approximate Solution for the Cutting Stock Problem Considering the Minimization of the Number of Setup Changes, Research Institute for Mathematical Sciences (RIMS) Kokyuroku."},{"key":"ref_14","unstructured":"Arai, H., and Haraguchi, H. (2020, January 20). Solution approaches for the two-dimensional cutting stock problem. Proceedings of the 64th System Control Information Society Research, Online."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Terada, K., Oku, D., Kanamaru, S., Tanaka, S., Hayashi, M., Yamaoka, M., Yanagisawa, M., and Togawa, N. (2018, January 16\u201319). An Ising model mapping to solve rectangle packing problem. Proceedings of the 2018 International Symposium on VLSI Design, Automation and Test (VLSI-DAT), Hsinchu, Taiwan.","DOI":"10.1109\/VLSI-DAT.2018.8373233"},{"key":"ref_16","first-page":"12","article-title":"Application of Ising machine to optimize glass-plate cutting patterns with guillotine-cut constraint","volume":"70","author":"Kida","year":"2020","journal-title":"AGC Res. Rep."},{"key":"ref_17","unstructured":"Arai, H., and Haraguchi, H. (2021). Ising formulations for the two-dimensional cutting stock problem with setup cost. arXiv."},{"key":"ref_18","unstructured":"(2021, January 29). Available online: http:\/\/or.dei.unibo.it\/library\/two-dimensional-bin-packing-problem."},{"key":"ref_19","unstructured":"(2021, February 26). Available online: https:\/\/developers.google.com\/optimization."},{"key":"ref_20","unstructured":"(2021, February 26). Available online: https:\/\/github.com\/dwavesystems\/dwave-ocean-sdk."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/182\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:12:33Z","timestamp":1760163153000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/6\/182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":20,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2021,6]]}},"alternative-id":["a14060182"],"URL":"https:\/\/doi.org\/10.3390\/a14060182","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,9]]}}}