Application of hybrid classical-quantum annealing technology to the 3D Bin-Packing Problem
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909299126566912 |
|---|---|
| author | Rahmani, Mohsen Umang, Nitish Christensen, Mason |
| author_facet | Rahmani, Mohsen Umang, Nitish Christensen, Mason |
| contents | In this paper, we study the use of hybrid classical-quantum annealing technology to solve a critical business optimization problem that is a form of multiproduct multi-bin packing in three dimensions with support constraints and case orientations along all three axes. We developed an exact mathematical model based on mixed-integer programming (MIP) to solve the problem, using fewer variables than previously existing models. Furthermore, to ensure the stability of the cases within bins, the model employs a novel formulation to represent the support constraints. We then compared and analyzed the solution performance of the classical solver Gurobi and D-Wave's constrained quadratic model (CQM) solver on the MIP model, both with and without support constraints. Results from the computational studies offer valuable insights into how the hybrid classical-quantum solver compares against widely used purely classical solvers on computationally hard problems, such as the problem of interest. This comparison examines aspects such as the optimality gap and volume utilization across different computational time limits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_15365 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Application of hybrid classical-quantum annealing technology to the 3D Bin-Packing Problem Rahmani, Mohsen Umang, Nitish Christensen, Mason Optimization and Control In this paper, we study the use of hybrid classical-quantum annealing technology to solve a critical business optimization problem that is a form of multiproduct multi-bin packing in three dimensions with support constraints and case orientations along all three axes. We developed an exact mathematical model based on mixed-integer programming (MIP) to solve the problem, using fewer variables than previously existing models. Furthermore, to ensure the stability of the cases within bins, the model employs a novel formulation to represent the support constraints. We then compared and analyzed the solution performance of the classical solver Gurobi and D-Wave's constrained quadratic model (CQM) solver on the MIP model, both with and without support constraints. Results from the computational studies offer valuable insights into how the hybrid classical-quantum solver compares against widely used purely classical solvers on computationally hard problems, such as the problem of interest. This comparison examines aspects such as the optimality gap and volume utilization across different computational time limits. |
| title | Application of hybrid classical-quantum annealing technology to the 3D Bin-Packing Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2408.15365 |