Debugging a model¶
Several kind of errors can occur when developing an optimization model:
your program may not compile
you may see error messages when building the model
you may suspect a design error in your model
This page covers the third kind of problem. That is to say that your program compiles without problem, the model is sucessfully created and the search starts, but the results obtained look abnormal either because not solution is found, or on the contrary because the objective function is too good to be correct, or because some variables remain stuck to 0 while much larger values would be expected.
Introduce constraints and objectives one by one¶
If your model involves many constraints or a complex objective function, then a first step to get a better understanding of what is happening is to remove almost all components of your model and to re-introduce then one by one.
For instance, if you cannot find feasible solutions whereas trivial feasible solutions should be found quickly on your problem, then reintroducing constraints one by one should help you detect the very family of constraints responsible for the infeasibility of your problem. Often, checking carefully the implementation of this constraints is sufficient to find the error.
If you discover that satisfying all the constraints is not a problem but that the problem becomes infeasible when you add a component of the objective function, then you are probably facing an implicit constraint, that is to say a constraint induced by an expression involved in the objective function. Indeed a solution is feasible if and only if two conditions are met:
all constraints are satisfied
the values of all objective functions are valid
For example if the objective function contains a term
sqrt(x+y), then it
implicitly requires that x+y is positive. Similarly a term
a[x] can be
undefined if x is out of the bounds of array
a. Such implicit requirements
can make the problem infeasible or can dramatically restrict the set of feasible
solutions. For instance in our CVRP example, if you
forget the test
c > ?̀ in the computation of the route distance then you will
distanceWarehouse[sequence]. for each route, what implicity requires
that each list of the model is non-empty : otherwise
sequence is -1 and
distanceWarehouse[-1] is undefined (out of bounds). Consequently the model
will find feasible solutions but it will have to use all trucks what can lead to
Inject a feasible solution as initial solution¶
A good way to identify what is leading to infeasible or poor solutions is to inject in your model a simple solution that should be feasible. In our above vehicle routing example it can be any solution where some trucks are unused.
Having set this initial solution, you can solve the problem with a time limit of 0 second. Typically, you may observe that the solution you injected is considered infeasible by your model, in which case you will see in the output the main violated constraints displayed at the end of the trace:
0 iterations performed in 0 seconds
No feasible solution found (infeas = 4)
Main violated expressions:
objective sum(sum(range(1, sum#21 + 1),......) is NaN
... because of at(array(35, 78, 76, 98, 55), at(list#3(5), count(list#3(5)) + -1))
In this output NaN codes for “Not a Number” that is to say that the given
objective is undefined. And the “because of” line gives the origin of this NaN.
Usually this display is sufficient to identify the cause of the infeasibility of
this solution but to make it even clearer you can set names to some of
your expressions using the
name attribute (or function
setName in C++
and Java or
SetName in C#). Here is the same ouput after having named some
of the expressions:
... because of at(DistanceToWarehouse, at(Tour3, count(Tour3) + -1))
Now we see clearly that the problem is that the DistanceToWarehouse array is
accessed at position count(Tour3)-1, that is to say at position -1 since Tour3 is
empty. In case of doubt you can also observe after this 0-second resolution the
value of any expression in the model or check if some expressions are underfined
(NaN) with method
isUndefined in LSP, C++ or Java,
is_undefined in Python and
IsUndefined in C#).
If no constraint is violated but the objective value is not what is expected, then you need to retrieve the values of intermediate expressions to track mistakes in the definition of this objective function (or in input data reading).