論理パズルを題材とした整数計画法による数理モデル化
情報数理工学実験第二A・B／コンピュータサイエンス実験第二A・B (MICS実験第二)
2016年度後学期
第1ラウンド
岡本 吉央
概要
離散最適化の技法である「整数計画法」を用いて，諸問題をモデル化し，ソフトウェアを用いて解く，という一連の流れを体験する．問題として使うものは，数独のようなペンシルパズルを考えている．モデル化に用いる言語はCEDの標準環境で動くものならば何でもよいが，整数計画法を解くためのソルバとして IBM ILOG CPLEX SCIPを利用する．
キーワード：整数計画法，離散最適化，数理モデリング
レポート
- 締切：11月15日 (火) 13:00 (もちろん厳守)
- 形式：紙媒体のものと電子媒体のものの両方
- 提出先 (紙媒体)：西4号館4階事務室前のレポート提出箱「岡本」
- 提出先 (電子媒体)：岡本宛にメールで (メーリングリスト宛ではないので注意)，bzip2などで適当に圧縮するとよい
- 再提出が必要な場合，11月21日 (月) の16:00までに個人 (メーリングリストへ登録されているアドレス) 宛のメールで連絡する
スケジュール
- 10/6 (水) 整数計画法の説明，SCIPを使ってみる
- 10/12 (水) 魔方陣と数独
- 10/17 (月) ののぐらむ
- 10/19 (水) 美術館
- 10/24 (月) カックロ
- 10/26 (水) ナンバーリンク
- 10/31 (月) レポート作成
実験テキストの訂正表
見つけたら教えて下さい．
- 1ページ目，タイトル：モデリング → 数理モデル化
- 1ページ目，第3項目：モデリング → 数理モデル化
- 28ページ目，下から4行目：「LP形式では，右辺に変数を置いてはいけない」ということは正しいが，それを適用すべき場面は第1の制約ではなく，第5の制約 (を含めた他の制約) である．少なくとも，第1の制約に対してはそのままでよい．
- 37ページ目，下から2行目：ナンバーリンク → カックロ
ファイルの訂正履歴
見つけたら教えて下さい．
- (10/17) lightup/lu_N105_113_13_17x17.txt を修正．
- (10/17) nonogram/nn_il_223_18_50x40.txt に不具合．(後で修正予定) → 修正不可能なので，このファイルは無視して下さい．
- (10/17) kakuro/kk_pp110_5_12x10.txt に不具合．(後で修正予定)
- (10/19) kakuro/kk_pp110_5_12x10.txt を修正．
- (10/24) numberlink/nl_hayatoki244_36x20.txt を修正．
参考情報
整数計画法，数理最適化に関する情報源
ペンシルパズルに慣れるため (CEDではゲーム禁止なので，やってはいけない)
- 数独
- ののぐらむ (お絵かきロジック，ピクロス，...)
- 美術館
- カックロ
- ナンバーリンク
[Teaching Top]
[Top]
okamotoy@uec.ac.jp