.png){kind=icon}
返回
QUBO Formulation Using Sequence Pair With Search Space Restriction for Rectangle Packing Problem
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2024.3485675.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The development of quantum annealing has stimulated interest in solving NP-hard problems, including various industrial problems, such as quadratic unconstrained binary optimization (QUBO), with specialized solvers. This study focuses on the rectangle packing problem (RPP), which is an NP-hard problem applicable to industrial applications. The objective of this problem is to place given items in a minimum area without overlap. Naive QUBO representations, such as a direct binary encoding of locations, could require a large number of bits, which limits the problem size, hindering the acquisition of the optimal solution. To circumvent this difficulty, we employ the concept of sequence pairs to efficiently represent the locations of items. We also propose a strategy that uses multiple sampling solutions obtained with a QUBO solver, where we employ new constraints on the number of the rectangles contributing to the placement area for restricting the search space to smoothly bridge the QUBO formulation of the sequence pair and the minimization of area of rectangle placement. We estimate an approximate curve for the optimum number of rectangles contributing to the placement area. Then, we add the penalty term concerning the deviation from the estimated optimal value on the objective function. In numerical experiments with instances with 4 to 10 rectangles, we demonstrate that the proposed sampling-based strategy can efficiently find feasible solutions. This strategy would be useful for dealing with more complex problems, such as rectangle orientation and three-dimensional problems, with a relatively small number of bits using sequence pairs.
Keyword:
Encoding
Minimization
Optimization
NP-hard problem
Quantum annealing
Annealing
Linear programming
Costs
Strips
Solids
Rectangle packing problem
sequence pair
quadratic unconstrained binary optimization
期刊
IF:
3.6
论文数:
9.8W
被引数:
29.4W
机构
引用论文
Hydrocarbon chain trans-gauche isomerization in phospholipid bilayer gel assemblies.png)
Biochemistry
BiochemistryIF0
PREAI
分享收藏Hybrid approach for solving real-world bin packing problem instances using quantum annealersSCIENTIFIC REPORTS
OAAI
SCIENTIFIC REPORTSIF3.9
OAAI分享收藏TopiQAL: Topic-aware Question Answering using Scalable Domain-specific SupercomputersTopiQAL：基于可扩展领域专用超级计算机的主题感知问答OAAI
OAAI分享收藏Sediment accumulation, stratigraphic order, and the extent of time-averaging in lagoonal sediments: a comparison of 210Pb and 14C/amino acid racemization chronologiesCoral ReefsOAAI
Coral ReefsIF0
OAAI分享收藏Ley de Subvención Escolar Preferencial (SEP): algunos resultados preliminares de su implementación
PREAI
分享收藏
查看更多内容