Feasiblity Study by sudoku

 アイデアの有効性を数独で検証しました。数独問題を解くのではなくて、数独の構造を有する割り当てを求める問題です。

この解は、数学的には、どのサイズでも必ず存在することが分かっています。 ラテン方格（Latin squares）とグレコラテン方格（Graeco‑Latin squares） の理論によって解を持つことは保証されています。一般化数独（n×n ブロックを持つ巨大数独）の 完成形（解） が、任意の n に対して存在することは、Herzberg & Murty (2007), Berend (2018) などの構成法で証明済みです。

なので、特殊解は、数学的方法で求めることが出来る筈です。それに対して、特殊解以外を含めて解の探索を行う一般的なアルゴリズムで、求めることは、結構難しく、MIPソルバで、5x5位まで(実測したことはありません。⇒9年前のRAMP講演でありました。）SATソルバで、10x10位ではないでしょうか？

今回の方法では、以下のような結果となりました。

Kissatの最新版を用いても、やはり10x10までしか求めることが出来ませんが、今回の方法では、12x12まで求めることが出来ました。このとき、変数数は、(12*12)^3=2985974です。もしかすると、SATソルバによる方法の世界記録かもしれません。これを、ナーススケジューリング問題にあてはめると、

■シフト数144　スタッフ1人/1日あたりのシフト数は1

■Day数144日　スタッフ144人の各シフト値の総和が1　144x144個の行制約がある

■Cover制約　各日に対して各シフト144について総和が1　144x144個の列制約がある

という問題の解が求まった。ということになります。上記評価結果を、ナーススケジューリング問題に言い換えると、今までは、シフト数100程度が限界だったのが、シフト数144まで求められるようになった、ということになります。自分で言うのもなんですが凄まじいです。

ちなみに、

■instance24の規模は、スタッフ数150人、Day数365日で、この点では、上の規模を上回っています。

■ローカルソルバで、どうなるかはやっていませんが、期待は持てないと思っています。

確か、昔は、6程度のサイズでも数秒かかっていたと思うので、(上表では、0.1秒もかかっていない）、ソルバとPCの両輪、ソフトウェアとハードウェアの掛け算で、性能向上を成し遂げてきたと思います。隔世の感がします。

instance24攻略に向けて、期待が持てる結果となりました。