Debugging a model

Several kind of errors can occur when developing an optimization model:

  1. your program may not compile

  2. you may see error messages when building the model

  3. 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 > 0 in the computation of the route distance then you will access distanceWarehouse[sequence[0]]. for each route, which implicitely 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 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 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).