A Study of Ising Formulations for Minimizing Setup Cost in the Two-Dimensional Cutting Stock Problem
Open Access
- 9 June 2021
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 14 (6), 182
- https://doi.org/10.3390/a14060182
Abstract
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.Keywords
This publication has 8 references indexed in Scilit:
- A Crow Search-Based Genetic Algorithm for Solving Two-Dimensional Bin Packing ProblemPublished by Springer Science and Business Media LLC ,2019
- A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packingComputers & Operations Research, 2009
- An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problemEuropean Journal of Operational Research, 2001
- A hybrid grouping genetic algorithm for bin packingJournal of Heuristics, 1996
- Bin-packing by simulated annealingComputers & Mathematics with Applications, 1994
- The Bottomn-Left Bin-Packing Heuristic: An Efficient ImplementationInternational Conference on Acoustics, Speech, and Signal Processing (ICASSP), 1983
- Orthogonal Packings in Two DimensionsSIAM Journal on Computing, 1980
- Performance Bounds for Level-Oriented Two-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1980