読者です 読者をやめる 読者になる 読者になる

いものやま。

雑多な知識の寄せ集め

最適化問題とGLPK。(その2)

数学 最適化 GLPK

昨日の続き。

今日は、昨日の自己言及パズルを数式に落とし込んでみる。

自己言及パズル(再掲)

ということで、とりあえずは昨日の問題の再掲から。

次の枠内に
数字がいくつずつあるかを
括弧内に数字で記入しなさい。
+--------------------+
| 2015/07/15         |
| 0 (  )      5 (  ) |
| 1 (  )      6 (  ) |
| 2 (  )      7 (  ) |
| 3 (  )      8 (  ) |
| 4 (  )      9 (  ) |
+--------------------+

解けただろうか・・・?

数式へ落とし込む

GLPKを使って問題を解けるようにするためには、まず数式に落とし込んでやらないといけない。
問題は、この自己言及パズルをどのように数式に落とし込むのか、という話だ。

このときにポイントとなるのが、変数の置き方。
単純に考えると、0の個数を x_0、1の個数を x_1、・・・としてしまいそうだけど、そう考えてしまうとなかなか解けない。
というのも、そのような変数の置き方をすると、その変数の中身の情報にアクセス出来ないからだ。
例えば、 x_0が3のとき、「 x_0の3の個数は1個」という情報が欲しいわけだけれども、その情報を取得する(線形の)関数を考えようとすると、非常に頭が痛い。

じゃあ、どうするのかというと、発想を逆にする。
数の中身の情報を変数として用意しておいて、そこから逆に数を構築するようにする。

具体的には、以下。

まず、「 kの個数の数字の n桁目は iか?」という変数を  x_{k, i, n} \in \{0, 1\} とする。
なお、1なら真と解釈して、0なら偽と解釈する。
このように、真か偽かを表す0-1変数のことを、バイナリ変数と呼んだりもする。

例えば、0の個数の数字が3だとすれば、  x_{0,3,1} = 1 かつ  x_{0, i, 1} = 0 \; (i = 0, 1, 2, 4, 5, \cdots , 9) となる。
逆に、  x_{0, 3, 1} = 1 かつ  x_{0, i, 1} = 0 \; (i = 0, 1, 2, 4, 5, \cdots 9) なら、0の個数の数字は3だと確定する(※0の個数の数字が1桁だと仮定した場合)。

こうしてやると、 kの個数の数字というのは、次のような数式で表せることになる。( Nは最大の桁数)

 {\displaystyle
(k\mbox{の個数の数字}) = \sum_{n=1}^N \sum_{i=0}^9 10^{n-1} \: i \: x_{k, i, n}
}

そして、枠内にある kの個数というのは、最初から枠内にある kの数( a_kとする)と、 x_{j, k, n}が1になっているものの数の合計なので、次のような数式で表せる。

 {\displaystyle
(\mbox{枠内の}k\mbox{の個数}) = a_k + \sum_{n=1}^N \sum_{j=0}^9 x_{j, k, n}
}

あとは、これらが一致すればいいので、次のような条件として書けることになる。

 {\displaystyle
\sum_{n=1}^N \sum_{i=0}^9 10^{n-1} \: i \: x_{k, i, n}
= a_k + \sum_{n=1}^N \sum_{j=0}^9 x_{j, k, n} \; \; \left(\forall k \in \{0, 1, ... , 9\}\right)
}

一番重要な条件はこれでOKなんだけど、他にもちょこちょこと細かい条件が必要。

具体的には、以下のとおり。

  •  kの各桁に入る数字は高々1つ
  •  k n桁目に数字が入っていないなら、 (n+1)桁目にも数字が入っていない
  •  kの数字が入っている桁で一番大きい桁の数字は0でない
  •  k N桁目には数字が入っていない(※一つ上の条件を書くときに必要になる)
  •  kの1桁目には数字が絶対入っている

これらの条件を書くためには、「 kの個数の数字の n桁目は空か?」という変数を  x_{k, -1, n} \in \{0, 1\} として用意してあげるといい。

そうすると、それぞれの条件は以下のようになる。

 kの各桁に入る数字は高々1つ

 {\displaystyle
\sum_{i=-1}^9 x_{k, i, n} = 1 \; \; \left(\forall k \in \{0, 1, ... , 9\}, \; \forall n \in \{1, ... , N\} \right)
}

 k n桁目に数字が入っていないなら、 (n+1)桁目にも数字が入っていない

 {\displaystyle
x_{k, -1, n+1} \ge x_{k, -1, n} \; \; \left(\forall k \in \{0, 1, ... , 9\}, \; \forall n \in \{1, ... , N-1\} \right)
}

 kの数字が入っている桁で一番大きい桁の数字は0でない

 {\displaystyle
x_{k, -1, n+1} \le x_{k, -1, n} + \sum_{i=1}^9 x_{k, i, n} \; \; \left(\forall k \in \{0, 1, ... , 9\}, \; \forall n \in \{1, ... , N-1\} \right)
}

 k N桁目には数字が入っていない

 {\displaystyle
x_{k, -1, N} = 1 \; \; \left(\forall k \in \{0, 1, ... , 9\} \right)
}

 kの1桁目には数字が絶対入っている

 {\displaystyle
x_{k, -1, 1} = 0 \; \; \left(\forall k \in \{0, 1, ... , 9\} \right)
}

ちょっと数式を読み解くのは大変かもだけど、別に難しいことをやっているわけではないので、根気よく読めば分かるはず・・・

あらためて書くと、重要なのは、バイナリ変数を使うというところ。
バイナリ変数を使うというのは最適化問題(特に組合せ最適化問題)の定式化にはよく出てくるので、覚えておきたい。

何にせよ、これで問題が数式に落とし込めたことになる。
この問題は、条件が(変数に関して)すべて一次式になっていて、変数が0か1の整数となっているので、整数計画問題(IP)という問題に分類される。

あとは、これをモデル記述言語で記述して、GLPKに解かせるだけ。

今日はここまで!