最適化問題とGLPK。（その2）

昨日の続き。

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

自己言及パズル（再掲）

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

次の枠内に
数字がいくつずつあるかを
括弧内に数字で記入しなさい。
+--------------------+
| 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桁だと仮定した場合）。