Debugging a model¶

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 them 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 these 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 (that is to say that no constraint takes value 0 or Not A Number)

• 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 the 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 > 0 in the computation of the route distance then you will access distanceWarehouse[sequence[0]]. for each route, which implicitly requires that each list of the model is non-empty, otherwise this expression is undefined (out of bounds). Consequently the model will find feasible solutions, but it will have to use all trucks which can lead to unexpected behavior.

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

Infeasible solution:
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 output 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 undefined (NaN) with the method isUndefined (Hexaly Modeler, 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).

Take warnings into account¶

Warnings are a new feature introduced in version 13.5, in particular to assist users in the detection of modeling errors.

These warnings can take the following form:

Warning: A risk of "Not a Number" error on objective: truck_distance was identified.
Please make sure that this expression will always be well-defined.
The probable cause is expression at(sequence_1, 0).

The key concept is that, for a solution to be valid, all objectives and all constraints must take a well-defined value. For example, if an objective is the square root of a negative number, then the solution is invalid. It is also the case if this objective is a sum including such an undefined value. However, if this undefined square root has no impact on constraints and objectives, then the model remains perfectly valid. For instance, the following objective is perfectly legitimate:

minimize x >= ? sqrt(x) : sqrt(-x)

Indeed, in this case, the objective value always well-defined, even when one branch of the conditional statement is undefined.

Hexaly performs an in-depth analysis of the model to determine whether all objectives and constraints are guaranteed to be well-defined. Note that in order to keep this analysis as fast as possible, it is not exhaustive and false positive and false negative are possible. In other words, a warning can be issued although the “Not a number” error can never occur thanks to the intrication of several constraints or conditions (false positive). Conversely, the absence of warnings does not guarantee that the model is correct (false negative). However, checking the part of the model mentioned in the warning is highly recommended.

As mentioned above, the main possible causes of undefined values are forbidden arithmetic operations (0/0, sqrt(-1), log(0), etc.), and array overflows. It is important to understand that these mistakes will not throw errors during the resolution of the model, it will merely discard a (possibly large) part of the solution space.

Let us consider our CVRP example example again. In this model, we count the distances to the depot only when a tour is non empty:

(c > 0 ? (distanceDepot[sequence[0]] + distanceDepot[sequence[c - 1]]) : 0).

Without this guard, the only valid solutions would be solutions where all lists are non-empty. In practice, the model works well for many input instances with high demand because using all trucks is necessary to satisfy the demand. It is only for small demand inputs that it “surprisingly” uses all trucks while only a few would be sufficient. Thanks to this model analysis feature, a warning is now issued, and the user can easily identify the issue.

In this case, removing the condition c > 0 triggers the following warning, assuming that we have named the second objective Distance_Objective using the name attribute (or function setName in C++ and Java or SetName in C#) :

Warning: A risk of "Not a Number" error on objective: Total distance was identified.
Please make sure that this expression will always be well-defined.
The probable cause is expression at(list#0(31), 0).

This warning clearly identifies that at least one list has its index 0 accessed with a risk of overflow (that is to say without guarantee to be non-empty).