イジング計算機による3次元直方体パッキング問題の解法

摘要

近年，組合せ最適化問題を効率的に解く計算機として，さまざまなイジング計算機が研究されている．組合せ最適化問題の1つに3次元直方体パッキング問題がある．3次元直方体パッキング問題として，直方体の重なりを許さずに，全直方体を包括する3辺の和が最小となる直方体の配置を探索する問題を考える．3次元直方体パッキング問題は，トラックやコンテナに荷物を詰め込む問題や，近年では集積回路の3次元配置に応用される．本稿では，3次元直方体パッキング問題を定式化し，イジング計算機の入力形式であるQuadratic Unconstrained Binary Optimization （QUBO）モデルへマッピングする手法を提案する．また，実イジング計算機を利用し，計算機実験を行った結果，直方体数6までの問題で3次元直方体パッキング問題の準最適解を求めることができた．