Balanced Assignment

This example is the Balanced Assignment challenge, in which we need to create groups that are as diverse as possible.

Balanced Assignment

Given several employee categories (title, location, department, male/female, …) and a specified number of groups, assign every employee to a project group so that the groups are the same size, and they are as diverse as possible.

Together with this specification, we are given a list of 210 people and their information.

This challenge is an interesting optimization challenge. As always, we start by filling out the glossary. We create a type to represent the people, and types for every information type we have. Then, we also need a type which will represent a number of persons, and a type which will just represent a large integer.

Note here that because our list has 210 entries, it would be nearly impossible to add all of these into the Values column of the glossary. We opt here to not define the values, but instead we will point the glossary to our data table, which will tell the solver that every value in the data table is a possible value.

Name Type Values
Person String See Data Table Person
Group Int [0..12]
Department string See Data Table Person
Location string See Data Table Person
Gender string See Data Table Person
Title string See Data Table Person
BoundNumber int [0, 1000000]
NbPersons int [16..19]

Next up, we introduce a function for every parameter, which will assign every person to their info. We will also need a function which maps every group on a number, representing the number of people in that group.

Name Type
department of Person Department
location of Person Location
gender of Person Gender
title of Person Title
group of Person Nat
number of Group NbPersons

To finish our glossary, we introduce a constant Score which will keep track of the score of a solution.

Name Type
Score BoundNumber

With our glossary finished, we can move on to the next step. We need a way to calculate the Score value for a solution. To do this, we will check for every two people that if they have something in common, that they are in a different group. If this is the case, then we add 1 to our score.

Calculate Score
C+ Person called p1 Person called p2 department of p1 location of p1 gender of p1 title of p1 group of p1 Score
1 - - = department of p2 - - - not(group of p2) 1
2 - - - = location of p2 - - not(group of p2) 1
3 - - - - = gender of p2 - not(group of p2) 1
4 - - - - - = title of p2 not(group of p2) 1

Now, we want to count the number of people per group. Again, we can do this in a simple table. Number in group of Person is a combination of Number in Group and group of Person. This allows us to count the amount of people per group. Now, because the type NbPersons is defined in our glossary as [16, 19], this automatically creates the constrain that every group needs to have between 16 and 19 people.

All that rests now is creating a Goal table in order to maximize the score!

Maximize Score

And that’s it! Sadly, the cDMN solver currently is unable to completely solve this challenge, as it is quite large. However, the cDMN notation is capable of fully modelling the problem, which is the main point.