search
LoginSignup
0

More than 3 years have passed since last update.

posted at

updated at

Organization

wildqat(QUBOシミュレータ)でビンパッキングを解いてみる(前半)

はじめに

昨日突然降ってきた(というか私がすっかり忘れていただけなのですが)最適化問題の案件の資料を読んでいて「ビンパッキング」がでてきたので、お勉強がてら「ビンパッキング」をwildqat(QUBOシミュレータ)で解いてみようと思います。
この記事は前半の立式までです!

「ビンパッキング」とは

色々な大きさのアイテムと、大きさが固定のビン(入れ物)が与えられています。アイテムをビンに詰めていくのですが、使うビンの個数をなるべく少なくするような詰め込み方(割り当て)を決めていくという問題です。
荷物の箱詰めでできるだけ箱を少なくしたり、トラックによる配送でできるだけトラックを少なくしたりするのに使えそうです!
box_danbo-ru_open.png

wildqatとは

MDR社のQUBOシミュレータであり、シミュレーテッドアニーリング (SA) またはシミュレーテッド量子アニーリング(SQA)と呼ばれるアルゴリズムを普通のPC上でシミュレートすることができます。オープンソースで、githubからダウンロードできます。
https://github.com/mdrft/Wildqat

ビンパッキングの例題

例として小さい問題を考えます。4つのアイテムがあり、そのサイズを1、1、2、3とします。箱も4つあり、箱には合計でサイズ4まで詰め込めることにします。
ナップザック問題と似ていますが、入れるものが1つでないところが多少やっかいです。また、QUBOで不等式を扱うには少し変わった式を立てる必要があります。

立式

<変数>
アイテム$i$を箱$j$に詰めるかどうかを変数$x_{ij}$とします。

x_{ij}=
 \begin{cases}
  1 & (アイテムiを箱jに入れる) \\ 
  0 & (アイテムiを箱jに入れない)
 \end{cases}

箱jに入れるサイズの合計がkであるときに1となる変数を$y_{jk}$とします。不等式のままだとQUBOにするのに不都合なため、箱に入れるサイズの合計が1、2、3、4を別々の4つの変数としています。

y_{jk}=
 \begin{cases}
  1 & (箱jに入れるアイテムの合計サイズがkである) \\ 
  0 & (箱jに入れる合計サイズはkではない)
 \end{cases} \\
ただし k=1~4

<制約条件1>
まずは「箱に入れるアイテムのサイズの上限は4である」を立式します。
QUBOシミュレータは問題を最小値問題に置き換える必要があります。そこで、制約条件を最小値問題に置き換えます。例えば箱1については、制約条件は
$$1x_{11}+1x_{21}+2x_{31}+3x_{41} \leq 4 $$
ですが、上述の不等式の問題のために箱1に関する変数が4つあるのと、と最小値問題に置き換えるという2つがあるためちょっと複雑です。例えば「箱1に入れるアイテムの合計サイズがちょうどkになるときに最小になる」式を考えると
$$ \lbrace (1y_{11}+2y_{12}+3y_{13}+4y_{14}) - (1x_{11}+1x_{21}+2x_{31}+3x_{41})\rbrace^2 $$ 
となるはずです。例えば合計サイズ4を入れるとき、左側の括弧の中は、y_{14}のみが1なのでちょうど4、右側のカッコの中も4になるので、全体の括弧の中の式はちょうど0で最小、それ以外の場合は0より大きくなるはずです。
この式を箱について一般化すると
$$ \lbrace (1y_{j1}+2y_{j2}+3y_{j3}+4y_{j4}) - (1x_{1j}+1x_{2j}+2x_{3j}+3x_{4j})\rbrace^2 $$ 
となります。

<制約条件2>
アイテムは必ずどれか1つの箱にはいる、という制約条件を最小値問題に置き換えます。
例えばアイテム1についての式は以下のようになります。
$$\lbrace 1 - (x_{11}+x_{12}+x_{13}+x_{14})\rbrace^2 $$ 
アイテム1がどれか1つの箱に入っているとき、右側の和の式が1になりますので、上の式は0となり最小、それ以外の場合0より大きくなります。すべてのアイテムについて一般化すると
$$\lbrace 1 - (x_{i1}+x_{i2}+x_{i3}+x_{i4})\rbrace^2 $$ 

<目的関数>
使う箱の数を最小にするという問題なので、(雑ですが)
$$ \sum_{jk}y_{jk} $$ 

こんな感じでできるのではと思います!

QUBO作成

あとは式展開してQUBOを作成します。
ただ、途中で気づいたのですが、アイテム4つでも結構式が多くて途中までコードを書いたのですが、力尽きました。。。
karou_businesswoman.png

時間があれば年内に続きを書きます!

それではみなさん良いクリスマスを~!

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0