Analyse a model

[cprudhom]

Currently, when one models a problem, it is possible to print various statistics about the model.
In some specific cases, that is when warn user option is on, some warnings can also be printed to the console (like unposted constraints for instance).

I believe it would be more convenient to define an analyse method in the Model API to get all these insights, and may be more.
For instance, I imagine the following values:

• types of variables and views declared,
• number of occurrences of each type,
• number and types of constraints/propagator declared,
• are there any unconstrained variables,
• are there any unposted/unreified constraints,
• ...

There are certainly other insights that can be considered (constraint network density, ...).
Any ideas?

[jgFages]

I believe it is a good idea.

I often print the model to see variables / constraints and I believe a recap saying how many variables and how many constraints/propagators of each kind are present in the model may be useful.

Perhaps a method indicating how many are instantiated / entailed (or passive) would be useful too (this could be called before solving, after initial propagation, in the middle of the search, on solution using incomplete search...)

Printing the constraint network is also a nice feature.

I think it is already a very good start!

[ArthurGodet]

You are right @cprudhom, let's continue the discussion here.

I guess that deplacing the code into a new class, something like ModelAnalysis for example, makes totally sense, especially if we add new analysis functionnalities.

Currently, the existing code allows easily to list all types of variables, and for each type list instantiated, constants and unconstrained ones. I also found interesting to list variables by domain size, as it might give some precisou insights.
In a similar way, the existing code already lists all the constraints, and for each one, the propagators that are declared, as well as entailed, completely instantiated, passive and reified ones. Similarly, I found interested to list the propagators by arity.

As suggested by @jgFages, I made the code such that it can be called at any moment.

About exports, I think that JSON, with appropriate data structures, is the best format (most especially compared to CSV for example) as it allows for easy data manipulation otherwise. Does anyone have a structure in mind ? For now, I can think of listing all variables with their propagators, all propagators/constraints with their variables, and some properties (instantiated, reified, etc.) for each.

What functionalities should we add ? I have the following in mind for now:

• Allow for constraint network representation and analysis: variable-oriented graph (one node for each variable, two nodes being linked if variables are sharing a constraint) and constraint-oriented graph (one node for each constraint, two nodes being linked if constraints are sharing variables)
• Use weighted versions of the above graphs to improve the analysis ?

[jgFages]

The propagator arity is a good idea for n-ary constraints. Another approach would be to gather them by ranges (1, 2, 3, 4-100, 101-1000, >1000). It would be less accurate but more concise (if we have hundreds of sums with minor arity differences the exact arity approach may become hard to read - which can happen as constants are removed from the sums as preprocessing).
What would you prefer?

Regarding the format I am not so sure the method should return JSON.
Isn't there any usage of this output other than print?
Would it make sense to do some checks in Java ?
If so, a POJO that could then be directly serialized into json using jackson (or a pretty print) may be more convenient.

Whatever the format, remains the question of the structure. For instance we could have a flat list of <propagator, arity, quantity>
or index them by propagator, leading to a map<propagator, <arity, quantity>>. If we go for the arity range approach, we would probably prefer indexing by arity...

Regarding the graph, I think it should be done in a separate function returning graphviz format (dot format).
For the weighted version, I don't really know what would be the weight function, I suggest we see that in a second step after playing around with the first graph.

[ArthurGodet]

I guess that we could indeed gather variables' domain size by ranges instead of raw value. That would probably ease the readiness of the printing. I guess we could have both: the default version would be to gather them by ranges, and another one would gather them by raw values, allowing the user for different levels of details.

Similarly, I would suggest to have different versions between the pretty printing and the JSON export. For the pretty printing, I think of something like in PR #939, maybe with some refactoring or adding in case of needs.
On the contrary, the JSON format would be composed of a two lists: one of variables and one of propagators. Each one would have a unique ID, a list of, respectively, propagators or variables they are linked to, as well as some properties (instantiated, reified, etc.). Such an export would allow anyone to do some data exploring of their wish. It would be up to the user to gather them by arity or whatever if using the JSON export. What do you think ?

Yes, I was thinking of the graphviz format too. We might also think of given ready-to-use functions for analysing the graph. And, yes, of course, the weighted function would come later as we don't know for now how to do it usefully.

[cprudhom]

That sounds great.

Note that the Graphviz/Gephi convertos already exist (see Graphviz and Gephi).

Also, adding some higher level other informations (like how many constraints were transformed while posted) may require to add some counters in the code. In that case, I think a IMeasure-like pattern (or simpler) could be adopted. But, this could wait for a first POC.

[ArthurGodet]

I still need to work on the graph we talked about, but everything else is available in ModelAnalysis class, which you can look at in PR #939. To have an idea of the printing and JSON export, I invite you to add the following lines in the MarioKart example (most especially in the MarioKart.buildModel() function) and to run it:

ModelAnalyser modelAnalyser = model.getModelAnalyser();
modelAnalyser.analyse();
modelAnalyser.printAnalysis();
modelAnalyser.toJson("path/to/marioKartAnalysis.json");

[gadavidd]

This is a awesome idea!

Is there any forecast for implementing this function in any choco-solver realesed?

[cprudhom]

This is in my TODOs, I hope to do that before the end of January 🤞