Visualize the score and the constraints

Mon 13 March 2017

Geoffrey De Smet

OptaPlanner lead

So we solved the planning problem and found a best solution which has a score of 0hard/-123soft. Why -123soft? Where does that penalty come from? Which constraints are broken? Let’s see how we can break down the score and visualize the pain points in a UI.

Let’s approach this problem from two sides on the course scheduling example:

Break down score per constraint type

In the top-down approach, we split up the score per constraint type (so per score rule):

Constraint type Score impact

Constraint type	Score impact
Room capacity	`-100soft`
Room stability	`-40soft`
Curriculum compactness	`-3soft`
Total	`-123soft`

Room capacity

-100soft

Room stability

-40soft

Curriculum compactness

-3soft

Total

-123soft

The room capacity constraint is broken the most: it causes for 81% (100/123) of the score loss. Maybe the school should invest in more classrooms?

Heat map with score impact per planning entity

In the bottom-up approach, we visualize the score impact per lecture:

Red lectures impact hard constraints.
Orange lectures impact only soft constraints. The higher the impact, the heavier the color.
White lectures don’t impact the score.

Solution Normal view Indictment heat map Score

Solution	Normal view	Indictment heat map	Score
Initialized			`-4hard/-18soft`
Feasible			`0hard/-68soft`
Near optimal			`0hard/-1soft` (*)
Optimal			`0hard/0soft`

Initialized

-4hard/-18soft

Feasible

0hard/-68soft

Near optimal

0hard/-1soft (*)

Optimal

0hard/0soft

As OptaPlanner finds better and better solutions, there is less and less orange on the heat map. Looks like the history courses are particularly hard to schedule. Maybe the school should look for an additional history teacher?

(*) Notice that -1soft is shared by multiple lectures: 3 lectures break the room stability constraint together because two of them use a different room than the other one.

Show me the API

OptaPlanner 7 provides this information out of the box through the ConstraintMatch API:

First build a ScoreDirector with Solver.getScoreDirectorFactory() and then:

Break down the score per constraint type with ScoreDirector.getConstraintMatchTotals(). Each ConstraintMatchTotal represents one score rule and has its total score.
Determine the score impact per planning entity with ScoreDirector.getIndictmentMap(). Each Indictment holds the total score impact of one planning entity. Use that score to create the heat map in your UI.

Try it out

Download OptaPlanner 7.0.0.CR1 or higher.
Run an example and load a dataset.
Click on the button at the bottom left.
Click the solve button.

Conclusion

Help the user make sense of the resulting score. Visualize which constraints and planning entities cause most harm.

Comments Permalink