論理パズルを題材とした整数計画法による数理モデル化

情報数理工学実験第二A・B／コンピュータサイエンス実験第二A・B (MICS実験第二)
2017年度後学期
第1ラウンド

岡本吉央

概要

離散最適化の技法である「整数計画法」を用いて，数独のようなペンシルパズルをモデル化し，ソフトウェアを用いて解く，という一連の流れを体験する．

キーワード：整数計画法，離散最適化，数理モデリング

見つけたら教えて下さい．

29ページ：「この第 5 の制約と先に登場した第 1 の制約，第 3 の制約から『第 i 横行の第 k クラスタの左端が左からj マス目にあるならば，その横行の左から j マス目と j +R[i,k]－1 マス目まではすべて黒マスとなる』ということが導かれる」と書かれているが，これは正しくない．
つまり，定式化も不完全である．しかし，実際のパズルはうまく解けてしまっている．この点について，余力のある人は，課題3.3の追加として，上で「導かれる」と書かれている制約を陽に定式化して，組み入れてみよ．

見つけたら教えて下さい．

整数計画法，数理最適化に関する情報源

ペンシルパズルに慣れるため (CEDではゲーム禁止なので，やってはいけない)