A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem
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 adequ...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-06-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/6/182 |
| _version_ | 1797530709608366080 |
|---|---|
| author | Hiroshi Arai Harumi Haraguchi |
| author_facet | Hiroshi Arai Harumi Haraguchi |
| author_sort | Hiroshi Arai |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T10:33:50Z |
| format | Article |
| id | doaj.art-13b1260ff7ab495688a50be225e45449 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T10:33:50Z |
| publishDate | 2021-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-13b1260ff7ab495688a50be225e454492023-11-21T23:26:06ZengMDPI AGAlgorithms1999-48932021-06-0114618210.3390/a14060182A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock ProblemHiroshi Arai0Harumi Haraguchi1Graduate School of Science and Engineering, Ibaraki University, 2-1-1, Hitachi-shi 316-8511, JapanGraduate School of Science and Engineering, Ibaraki University, 2-1-1, Hitachi-shi 316-8511, JapanWe 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.https://www.mdpi.com/1999-4893/14/6/182Ising modelquantum annealerQUBOcutting stock problembin packing problemoptimization method |
| spellingShingle | Hiroshi Arai Harumi Haraguchi A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem Algorithms Ising model quantum annealer QUBO cutting stock problem bin packing problem optimization method |
| title | A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem |
| title_full | A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem |
| title_fullStr | A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem |
| title_full_unstemmed | A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem |
| title_short | A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem |
| title_sort | study of ising formulations for minimizing setup cost in the two dimensional cutting stock problem |
| topic | Ising model quantum annealer QUBO cutting stock problem bin packing problem optimization method |
| url | https://www.mdpi.com/1999-4893/14/6/182 |
| work_keys_str_mv | AT hiroshiarai astudyofisingformulationsforminimizingsetupcostinthetwodimensionalcuttingstockproblem AT harumiharaguchi astudyofisingformulationsforminimizingsetupcostinthetwodimensionalcuttingstockproblem AT hiroshiarai studyofisingformulationsforminimizingsetupcostinthetwodimensionalcuttingstockproblem AT harumiharaguchi studyofisingformulationsforminimizingsetupcostinthetwodimensionalcuttingstockproblem |