Debugging Methods Using Random Instance Generation

Debugging Methods Using Random Instance Generation#

In this document, we introduce a debugging method for mathematical models written in JijModeling using Problem.generate_random_instance. Note that this method is specifically intended to find bugs in each element of a mathematical model (placeholders, decision variables, and the expressions composed of them).

What is `generate_random_instance`?#

Problem.generate_random_instance is a method that randomly generates instance data according to the placeholder definitions in a mathematical model, compiles the model together with the generated data, and outputs an OMMX instance. For detailed usage, see here.

Debugging Method Using `generate_random_instance`#

Let us see how to debug a mathematical model using the graph coloring problem as an example. For the formulation of the graph coloring problem, see here. First, let us intentionally create a “bad formulation”.

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} \]

What is wrong with this formulation? At first glance, the objective function and constraints in the \(\LaTeX\) display look exactly as shown in the graph coloring formulation, so it may seem that there is no bug. Now, let us run Problem.generate_random_instance multiple times as follows.

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(5)), Constant(Integer(2))]))[0], Constant(Integer(0))] * x[Tuple(Tuple([Constant(Integer(5)), 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(5)), Constant(Integer(2))]))[0], Constant(Integer(0))]',
        defined at File "/tmp/ipykernel_649/3783062234.py", line 13, col 23-33

File "/tmp/ipykernel_649/3783062234.py", line 13, col 23-33:

    13  |      problem += jm.sum(x[e[0], n] * x[e[1], n] for n in N for e in E )
                                 ^^^^^^^^^^

5 is out of bound for axis 0, which is of size 4

As shown above, a ModelingError occurs, revealing that there are cases where values outside the index range \(V \times N\) of decision variable \(x\) are specified. Why does this happen? Because the possible range of \(e[0]\) or \(e[1]\) becomes the entire set of natural numbers \(\mathbb{N}\). To fix this bug (the problematic part) in the mathematical model, you need to restrict the possible values of \(e[0]\) and \(e[1]\) to \(V\) instead of all natural numbers. Specifically, you can remove this bug by changing the code as follows.

@jm.Problem.define("Graph Coloring Problem (Good Modeling)")
def gcp_good_modeling(problem: jm.DecoratedProblem):
    V = problem.Natural(description="Number of vertices")
    # Fix: specify dtype=V to explicitly restrict the possible value range
    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} \]

Now, let us verify again whether this fix has removed the bug.

for _ in range(25):
    _ = gcp_good_modeling.generate_random_instance()

This runs Problem.generate_random_instance without errors. This result indicates that errors are less likely to occur even when randomly injecting instance data that follows the placeholder definitions, in other words, that there are fewer bugs in the model definition.

In this way, by using Problem.generate_random_instance, you can remove bugs in model definitions and improve the quality of your mathematical models.

Notes#

JijModeling’s expressive power is still evolving. Therefore, it is not always possible to make Problem.generate_random_instance pass only by changing the mathematical model. In such cases, we recommend adjusting the range of placeholder values generated by Problem.generate_random_instance according to the documentation here.

For Those Who Need Help

If you are struggling with formulation or debugging of mathematical models in JijModeling, please make use of our Discord community.

Debugging Methods Using Random Instance Generation

Contents

Debugging Methods Using Random Instance Generation#

What is generate_random_instance?#

Debugging Method Using generate_random_instance#

Notes#

What is `generate_random_instance`?#

Debugging Method Using `generate_random_instance`#