1. 定式化におけるデバッグとは #

1.1. 説明 #

考えた通りの定式化をモデリング言語で記述できているか，もしくは期待する動作をしていないと疑われる場合に，正しく定式化をモデリング言語で記述できているかを調べることがある．これをプログラミング言語の用語を借用して，定式化におけるデバッグと称する．

モデリング言語を背景としたデバッグ手法には素朴なものから，数理最適化の専門的な知識を要するものまで様々にある．このうち素朴な手法について以下にまとめる．

1.1.1. プリントデバッグ #

モデリング言語の規格によって細かい部分の違いはあるが，一つの文で記述された数式を解釈していく各ステップが正しいかどうかの一時的な検証のために，プリントデバッグは有効である．

モデリング言語でのプリントデバッグとしては以下の事項を意識した出力を指定することが頻出する．

求解した結果，変数がある範囲に収まっている添字を確認したい．
求解した結果，変数がある範囲に収まっている添字について，式の値を確認したい．

条件付きで範囲を指定しないと膨大な量が出力されうる．具体例としては次がよくある．

バイナリ変数 \(x[i]\) が \(1\) をとる添字を確認したい．
バイナリ変数 \(x[i]\) が \(1\) をとる添字について式 \(E[i]\) の値を確認したい．

モデリング言語 SIMPLE で記述された変数や式は，条件を指定して出力可能である．以下は C/C++ 版と Python 版のそれぞれに関する出力記述例である．ある二つの添字についてのみ出力がなされるよう試験するためのサンプルコードである．

より詳細な出力記述方法についてはそれらモデリング言語のドキュメントに委ねる．

1.1.1.1. C++SIMPLE #

Set I = "1 .. 5";
Element i(set=I);
IntegerVariable x(type=binary, index=i);
sum(x[i], i) == 2;
Expression E(index=i);
E[i] = i * x[i];
Objective f(type=minimize);
f = sum(x[i], i);
options.outputMode = "silent";
solve();

(x[i].val, x[i].val == 1).print();
(E[i].val, x[i].val == 1).print();
simple_printf("i = %d\n", i, x[i].val == 1);
simple_printf("E[%d] = %f\n", i, E[i].val, x[i].val == 1);

上記を実行すると，以下のような出力が得られる．

x[4] = 1
x[5] = 1
E[4] = 4
E[5] = 5
i = 4
i = 5
E[4] = 4.000000
E[5] = 5.000000

1.1.1.2. PySIMPLE #

from pysimple import Problem, Element, BinaryVariable, Parameter, Sum

i = Element(value=range(1, 5))
x = BinaryVariable(index=i)
E = i*x[i]
prob = Problem(type=min)
prob += Sum(x[i], i) == 2
prob += Sum(x[i], i)
prob.solve(silent=True)

print(x[x[i].val == 1].val)
print(E[x[i].val == 1].val)

上記を実行すると，以下のような出力が得られる．

x[3].val=1
x[4].val=1
(i*x[i])[3].val=3
(i*x[i])[4].val=4

1.1.2. 定数値の定義域の検証 #

定式化で目的関数の係数はすべて非負であるなど，定数に対して一定の前提を伴うことがある．もしくは上下限制約を定めている上限値 \(U\) と下限値 \(L\) があったとき， \(U<L\) は明らかに不適切な定数値である．

こういった定数及び定数間の値の定義域が期待している範囲にない場合がある．モデルとして定式化自体は誤っていないものの，入力データに誤りがある場合である．

この場合を想定して，モデルの記述部分に，各定数があるべき範囲に収まっているかを記述したい場合には， assert 文に相当する文をモデル内に記述することになる．

モデルとデータを分離するという観点でいえば，議論が分かれるところであるが，モデリング言語はあくまでもモデルの記述に特化した言語であるため，このような処理には非効率であってもおかしくはない．こういった文は書かずに入力に近いフィルター部分の上位側での解決が望ましいだろう．

1.1.3. 目的関数の挙動 #

目的関数は制約条件が増えるほど，自由に最適化ができなくなっていくので，目的関数値は制約条件の追加前に比べて悪くなる傾向がある．このため制約条件を追加していって，逆に良くなっていく場合には記述のどこかに誤りがあると睨んでよいだろう．

定式化におけるデバッグとは

目次