はじめに
昨日突然降ってきた（というか私がすっかり忘れていただけなのですが）最適化問題の案件の資料を読んでいて「ビンパッキング」がでてきたので、お勉強がてら「ビンパッキング」をwildqat（QUBOシミュレータ）で解いてみようと思います。
この記事は前半の立式までです！
「ビンパッキング」とは
色々な大きさのアイテムと、大きさが固定のビン（入れ物）が与えられています。アイテムをビンに詰めていくのですが、使うビンの個数をなるべく少なくするような詰め込み方（割り当て）を決めていくという問題です。
荷物の箱詰めでできるだけ箱を少なくしたり、トラックによる配送でできるだけトラックを少なくしたりするのに使えそうです！
wildqatとは
MDR社のQUBOシミュレータであり、シミュレーテッドアニーリング (SA) またはシミュレーテッド量子アニーリング(SQA)と呼ばれるアルゴリズムを普通のPC上でシミュレートすることができます。オープンソースで、githubからダウンロードできます。
https://github.com/mdrft/Wildqat
ビンパッキングの例題
例として小さい問題を考えます。４つのアイテムがあり、そのサイズを１、１、２、３とします。箱も４つあり、箱には合計でサイズ４まで詰め込めることにします。
ナップザック問題と似ていますが、入れるものが１つでないところが多少やっかいです。また、QUBOで不等式を扱うには少し変わった式を立てる必要があります。
立式
＜変数＞
アイテム$i$を箱$j$に詰めるかどうかを変数$x_{ij}$とします。
x_{ij}=
\begin{cases}
1 & (アイテムiを箱jに入れる) \\
0 & (アイテムiを箱jに入れない)
\end{cases}
箱jに入れるサイズの合計がkであるときに１となる変数を$y_{jk}$とします。不等式のままだとQUBOにするのに不都合なため、箱に入れるサイズの合計が1、２、３、４を別々の４つの変数としています。
y_{jk}=
\begin{cases}
1 & (箱jに入れるアイテムの合計サイズがkである) \\
0 & (箱jに入れる合計サイズはkではない)
\end{cases} \\
ただし k=1～4
＜制約条件１＞
まずは「箱に入れるアイテムのサイズの上限は４である」を立式します。
QUBOシミュレータは問題を最小値問題に置き換える必要があります。そこで、制約条件を最小値問題に置き換えます。例えば箱１については、制約条件は
$$1x_{11}+1x_{21}+2x_{31}+3x_{41} \leq 4 $$
ですが、上述の不等式の問題のために箱１に関する変数が４つあるのと、と最小値問題に置き換えるという２つがあるためちょっと複雑です。例えば「箱１に入れるアイテムの合計サイズがちょうどkになるときに最小になる」式を考えると
$$ \lbrace (1y_{11}+2y_{12}+3y_{13}+4y_{14}) - (1x_{11}+1x_{21}+2x_{31}+3x_{41})\rbrace^2 $$
となるはずです。例えば合計サイズ4を入れるとき、左側の括弧の中は、y_{14}のみが1なのでちょうど４、右側のカッコの中も４になるので、全体の括弧の中の式はちょうど０で最小、それ以外の場合は０より大きくなるはずです。
この式を箱について一般化すると
$$ \lbrace (1y_{j1}+2y_{j2}+3y_{j3}+4y_{j4}) - (1x_{1j}+1x_{2j}+2x_{3j}+3x_{4j})\rbrace^2 $$
となります。
＜制約条件２＞
アイテムは必ずどれか1つの箱にはいる、という制約条件を最小値問題に置き換えます。
例えばアイテム１についての式は以下のようになります。
$$\lbrace 1 - (x_{11}+x_{12}+x_{13}+x_{14})\rbrace^2 $$
アイテム１がどれか1つの箱に入っているとき、右側の和の式が１になりますので、上の式は０となり最小、それ以外の場合０より大きくなります。すべてのアイテムについて一般化すると
$$\lbrace 1 - (x_{i1}+x_{i2}+x_{i3}+x_{i4})\rbrace^2 $$
＜目的関数＞
使う箱の数を最小にするという問題なので、（雑ですが）
$$ \sum_{jk}y_{jk} $$
こんな感じでできるのではと思います！
QUBO作成
あとは式展開してQUBOを作成します。
ただ、途中で気づいたのですが、アイテム４つでも結構式が多くて途中までコードを書いたのですが、力尽きました。。。
時間があれば年内に続きを書きます！
それではみなさん良いクリスマスを~！