マイナリズム - 鉛筆パズルの整数計画法による解法定式化集

鉛筆パズルの整数計画法による解法定式化集７５．
マイナリズム
http://indi.s58.xrea.com/minarism/より
例題（連続発破保管庫マイナリズム編 No.00）
＞
＞
4 ＞3 ＞2 ＞1
② ①
3
1
2 4
1
2
3
1
3
4
4
2
＞
＞＞
② ①
解答
ルール
すべてのマスに、１から列数（＝行数）までの数字を入れる。
①各行、各列で数字が重複してはいけない。
②数字の大きさは盤面の不等号に従う。
③丸付き数字のあるところでは、その両側にある二つの数字の差
(大きいほうから小さいほうを引いたもの)が、丸の数字と等しくならなければいけない。
Excelで扱うと、罫線の上に配置された不等号、○入り数字とその座標を読み取るのが面倒であるが、
整数計画法の定式化は楽である。
マスと罫線の行番号Ｉ、列番号Ｊを下記の通りとする。
J→
0 1
1
I 0
↓ 1
2
線番号
3 . . .
Nc
マス番号
2 3 4 . . .
Nc
1
2
マ3
ス .
番 .
.
号
2
.
線 .
番 .
号
Nr
Nr
変数
C(I,J,K) = 1
= 0
zD(I,J) = 1
= 0
zR(I,J) = 1
= 0
マス(I,J)に数字Ｋが入るとき
〃入らないとき
マス(I,J)の下のマスの数字との差の絶対値計算のための補助変数
マス(I,J)の右のマスの数字との差の絶対値計算のための補助変数
F(I,J)：
マス(I,J)に入る数字
D(I,J)：
マス(I,J)の下のマスの数字との差の絶対値
R(I,J)：
マス(I,J)の右のマスの数字との差の絶対値
目的関数
minimize
（ダミー）
x
制約式
subject to
１.マスには１∼Ncまでのどれかの数字が入る
Nc
C(I,J,K)＝1
Σ
K=1
(I=1,2.......Nr)
(J=1,2.......Nc)
２.C(I,J,K)=1のときマスに入る数字、F(I,J)=Kとする
Nc
{K*C(I,J,K)}＝F(I,J)
Σ
K=1
(I=1,2.......Nr)
(J=1,2.......Nc)
３.同じ列に同じ数字は来ない
Nr
C(I,J,K)＝1
Σ
I=1
(J=1,2.......Nc)
(K=1,2.......Nc)
４.同じ行に同じ数字は来ない
Nc
C(I,J,K)＝1
Σ
J=1
(I=1,2.......Nr)
(K=1,2.......Nc)
５.盤面不等号指定
"＞"の線番号がJ、マス番号がIのとき
F(I,J)≧F(I,J+1)
"
＞
＜
"＜"の線番号がJ、マス番号がIのとき
F(I,J)≦F(I,J+1)
" "の線番号がI、マス番号がJのとき
F(I,J)≧F(I+1,J)
"の線番号がI、マス番号がJのとき
F(I,J)≦F(I+1,J)
６.マス(I,J)の下のマスとの数値差の絶対値 D(I,J)
"○"の線番号がI、マス番号がJのとき
(L=1,2.......Nf)
F(I,J)-F(I+1,J)≦D(I,J)
Nfは○の総数
F(I,J)-F(I+1,J)+bigM*zD(I,J)≧D(I,J)
F(I+1,J)-F(I,J)≦D(I,J)
F(I+1,J)-F(I,J)+bigM*{1-zD(I,J)}≧D(I,J)
７.マス(I,J)の右のマスとの数値差の絶対値 R(I,J)
"○"の線番号がJ、マス番号がIのとき
(L=1,2.......Nf)
F(I,J)-F(I,J+1)≦R(I,J)
F(I,J)-F(I,J+1)+bigM*zR(I,J)≧R(I,J)
F(I,J+1)-F(I,J)≦R(I,J)
F(I,J+1)-F(I,J)+bigM*{1-zR(I,J)}≧R(I,J)
８．数字差D(I,J)とR(I,J)を指定値に合わせる
"○"の線番号がI、マス番号がJのとき
(L=1,2.......Nf)
D(I,J)＝○内数値
"○"の線番号がJ、マス番号がIのとき
R(I,J)＝○内数値
上下界
bounds
変数型
binary
C(I,J,K)
(I=1,2….…Nr)
(J=1,2….…Nc)
(K=1,2….…Nc)
zD(I,J) zR(I,J)
general
F(I,J)
(I=1,2….…Nr)
(J=1,2….…Nc)
D(I,J) R(I,J)
終端
end
(L=1,2….…Nf)
(I,J)はL番目の○の座標
(L=1,2….…Nf)
(I,J)はL番目の○の座標

Download Report