インスタンスのランダム生成を用いたデバッグ#
本ドキュメントでは、JijModeling で書かれた数理モデルのデバッグ手法として、 Problem.generate_random_instance を使った方法を紹介します。このデバッグ手法はあくまで「数理モデルの各要素（プレースホルダーや決定変数、それらの成す式）のバグを探す方法」であることに注意してください。
generate_random_instance とは#
Problem.generate_random_instance とは、数理モデルのプレースホルダーの定義に従ってインスタンスデータをランダムに生成し、その数理モデルとインスタンスデータをコンパイルして OMMX インスタンスを出力するメソッドです。詳しい利用方法は こちら を参照してください。
generate_random_instance を使ったデバッグ手法#
グラフ彩色問題を題材に、どのように数理モデルのデバッグが行えるかを見ていきましょう。グラフ彩色問題の定式化の方法は こちら を参照してください。まずは"良くない定式化"をしてみましょう。
import jijmodeling as jm
@jm.Problem.define("Graph Coloring Problem (Bad Modeling)")
def gcp_bad_modeling(problem: jm.DecoratedProblem):
V = problem.Natural(description="Number of vertices")
E = problem.Graph(description="Edges of the graph")
N = problem.Natural(description="Number of colors")
x = problem.BinaryVar(shape=(V, N), description="Binary variables for vertex-color assignment")
problem += problem.Constraint(
"one-color",
[jm.sum(x[v, n] for n in N) == 1 for v in V]
)
problem += jm.sum(x[e[0], n] * x[e[1], n] for n in N for e in E )
gcp_bad_modeling
\[\begin{array}{rl}
\text{Problem}\colon &\text{Graph Coloring Problem (Bad Modeling)}\\\displaystyle \min &\displaystyle \sum _{n=0}^{N-1}{\sum _{e\in E}{{x}_{{e}_{0},n}\cdot {x}_{{e}_{1},n}}}\\&\\\text{s.t.}&\\&\begin{aligned}
\text{one-color}&\quad \displaystyle \sum _{n=0}^{N-1}{{x}_{v,n}}=1\quad \forall v\;\text{s.t.}\;v\in \left\{0,\ldots ,V-1\right\}\end{aligned}
\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[V\times N;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\&&&\text{Binary variables for vertex-color assignment}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}E&\in \mathop{\mathrm{Array}}\left[(-);\mathbb{N}\times \mathbb{N}\right]&\quad &1\text{-dimensional array of placeholders with elements in }\mathbb{N}\times \mathbb{N}\\&&&\text{Edges of the graph}\\&&&\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\&&&\text{Number of colors}\\&&&\\V&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\&&&\text{Number of vertices}\\\end{alignedat}\end{array}
\]
この定式化の良くない部分はどこでしょうか。 \(\LaTeX\)表示の目的関数と制約条件を一見すると、グラフ彩色問題の定式化の通りになっているため、どこにもバグはないように思われます。
ここで、 以下のように Problem.generate_random_instance を複数回実行してみましょう。
try:
for _ in range(25):
_ = gcp_bad_modeling.generate_random_instance()
except jm.ModelingError as e:
print(e)
Traceback (most recent last):
while evaluating problem `Problem(name="Graph Coloring Problem (Bad Modeling)", sense=MINIMIZE, objective=sum(set(N.flat_map(lambda (n: natural): E.map(lambda (e: Tuple[natural, natural]): (n, e)))).map(lambda ((n, e): Tuple[natural, Tuple[natural, natural]]): x[e[0], n] * x[e[1], n])), constraints={one-color: [Constraint(name="one-color", , lambda v: sum(set(N).map(lambda (n: natural): x[v, n])) == 1, domain=set(V)),],})',
defined at File "/tmp/ipykernel_649/3783062234.py", line 1, col 2-60
while evaluating objective `sum(set(N.flat_map(lambda (n: natural): E.map(lambda (e: Tuple[natural, natural]): (n, e)))).map(lambda ((n, e): Tuple[natural, Tuple[natural, natural]]): x[e[0], n] * x[e[1], n]))',
defined at File "/tmp/ipykernel_649/3783062234.py", line 13, col 16-70
while evaluating expression `sum(set(N.flat_map(lambda (n: natural): E.map(lambda (e: Tuple[natural, natural]): (n, e)))).map(lambda ((n, e): Tuple[natural, Tuple[natural, natural]]): x[e[0], n] * x[e[1], n]))' as a function,
defined at File "/tmp/ipykernel_649/3783062234.py", line 13, col 16-70
while evaluating expression `sum(set(N.flat_map(lambda (n: natural): E.map(lambda (e: Tuple[natural, natural]): (n, e)))).map(lambda ((n, e): Tuple[natural, Tuple[natural, natural]]): x[e[0], n] * x[e[1], n]))' as type `float!`,
defined at File "/tmp/ipykernel_649/3783062234.py", line 13, col 16-70
while evaluating expression `sum(set(N.flat_map(lambda (n: natural): E.map(lambda (e: Tuple[natural, natural]): (n, e)))).map(lambda ((n, e): Tuple[natural, Tuple[natural, natural]]): x[e[0], n] * x[e[1], n]))',
defined at File "/tmp/ipykernel_649/3783062234.py", line 13, col 16-70
while evaluating expression `x[Tuple(Tuple([Constant(Integer(0)), Constant(Integer(2))]))[0], Constant(Integer(0))] * x[Tuple(Tuple([Constant(Integer(0)), Constant(Integer(2))]))[1], Constant(Integer(0))]',
defined at File "/tmp/ipykernel_649/3783062234.py", line 13, col 23-46
while evaluating expression `x[Tuple(Tuple([Constant(Integer(0)), Constant(Integer(2))]))[1], Constant(Integer(0))]',
defined at File "/tmp/ipykernel_649/3783062234.py", line 13, col 36-46
File "/tmp/ipykernel_649/3783062234.py", line 13, col 36-46:
13 | problem += jm.sum(x[e[0], n] * x[e[1], n] for n in N for e in E )
^^^^^^^^^^
2 is out of bound for axis 0, which is of size 1
すると、上記のように ModelingError が発生し、決定変数 \(x\) の添字の範囲 \(V \times N\) の外の値を指定してしまうケースがある事がわかります。なぜ、このようなケースが発生するのかというと、 \(e[0]\) あるいは \(e[1]\) の取り得る範囲が自然数全体 \(\mathbb{N}\) となってしまっているからです。
この数理モデルのバグ（良くない部分）を修正するには、\(e[0]\) および \(e[1]\) の取り得る範囲を自然数全体ではなく \(V\) に制限する必要があります。具体的には、以下のようなコードに変更することでバグを取り除くことができます。
@jm.Problem.define("Graph Coloring Problem (Good Modeling)")
def gcp_good_modeling(problem: jm.DecoratedProblem):
V = problem.Natural(description="Number of vertices")
# 修正点: dtype に V を指定することで取り得る範囲を明示的に制限する
E = problem.Graph(dtype=V, description="Edges of the graph")
N = problem.Natural(description="Number of colors")
x = problem.BinaryVar(shape=(V, N), description="Binary variables for vertex-color assignment")
problem += problem.Constraint(
"one-color",
[jm.sum(x[v, n] for n in N) == 1 for v in V]
)
problem += jm.sum(x[e[0], n] * x[e[1], n] for n in N for e in E )
gcp_good_modeling
\[\begin{array}{rl}
\text{Problem}\colon &\text{Graph Coloring Problem (Good Modeling)}\\\displaystyle \min &\displaystyle \sum _{n=0}^{N-1}{\sum _{e\in E}{{x}_{{e}_{0},n}\cdot {x}_{{e}_{1},n}}}\\&\\\text{s.t.}&\\&\begin{aligned}
\text{one-color}&\quad \displaystyle \sum _{n=0}^{N-1}{{x}_{v,n}}=1\quad \forall v\;\text{s.t.}\;v\in \left\{0,\ldots ,V-1\right\}\end{aligned}
\\&\\\text{where}&\\&\text{Decision Variables:}\\&\qquad \begin{alignedat}{2}x&\in \mathop{\mathrm{Array}}\left[V\times N;\left\{0, 1\right\}\right]&\quad &2\text{-dim binary variable}\\&&&\text{Binary variables for vertex-color assignment}\\\end{alignedat}\\&\\&\text{Placeholders:}\\&\qquad \begin{alignedat}{2}E&\in \mathop{\mathrm{Array}}\left[(-);V\times V\right]&\quad &1\text{-dimensional array of placeholders with elements in }V\times V\\&&&\text{Edges of the graph}\\&&&\\N&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\&&&\text{Number of colors}\\&&&\\V&\in \mathbb{N}&\quad &\text{A scalar placeholder in }\mathbb{N}\\&&&\text{Number of vertices}\\\end{alignedat}\end{array}
\]
では、この修正によりバグが取り除かれたかをどうかを改めて確認してみましょう。
for _ in range(25):
_ = gcp_good_modeling.generate_random_instance()
エラーなく Problem.generate_random_instance を通すことが出来ました。この結果は、プレースホルダーの定義に従っているインスタンスデータをランダムに入れてもエラーが発生し難くなったこと、すなわち、数理モデルの定義のバグが少なくなったことを示しています。
このように Problem.generate_random_instance を使えば、数理モデルの定義のバグを取ることができ、その数理モデルの質を高めることができるのです。
注意点#
JijModeling の表現力は発展途上にあります。そのため、必ずしも数理モデルの変更だけで Problem.generate_random_instance が通るようになるわけではありません。そのような場合には、 Problem.generate_random_instance の生成するプレースホルダーの値の範囲を こちら に従って調整してみることをおすすめします。
お悩みの方へ
JijModeling による数理モデルの定式化やデバッグでお悩みの方は、ぜひ、Discordコミュニティをご活用ください。