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.
| Type | ||
|---|---|---|
| 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 |
| 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.
| Function | |
|---|---|
| Name | Type |
| department of Person | Department |
| location of Person | Location |
| gender of Person | Gender |
| title of Person | Title |
| group of Person | Group |
| number of Group | Int |
To finish our glossary, we introduce a constant Score which will keep track of the score of a solution.
| Constant | |
|---|---|
| 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.
| Count the number of people in a group | ||||
|---|---|---|---|---|
| C+ | Person | Group | group of Person | number in Group |
| 1 | - | - | Group | 1 |
Finally, we need to create the constraint that each group contains between 16 and 19 people. This is fairly straightforward using a constraint table:
| Set group sizes | ||
|---|---|---|
| E* | Group | number in Group |
| 1 | - | [16, 19] |
To let the cDMN solver know that we want to find the solution with the highest score, we introduce a Goal table to maximize.
| Goal |
|---|
| Maximize Score |
And that’s it! We can now run the solver to find the optimal solution. It takes about four minutes, but eventually it finds the following optimal solution: Quite cool!
Model 1
==========
department_of_Person := {BIW->NNE, KRS->WSW, TLR->NNW, VAA->NNW, JRT->NNE, AMR->SSE, MES->NNE, JAD->NNE, MJR->NNE, JRS->NNE, HCN->SSE, DAN->NNE, CWT->NNE, DCN->NNE, SWR->WSW, TBG->NNE, LVO->NNE, ECA->NNE, MAI->NNE, JCO->SSE, DWO->SSE, AJH->NNE, CAE->SSE, MRL->WSW, FTR->NNE, SJO->NNE, DHY->NNE, DHE->NNE, CWU->NNW, EAZ->NNE, RFS->NNE, JWS->WSW, RVY->NNE, PMO->SSE, RGR->NNE, LLR->NNE, FEE->NNW, ADS->NNE, CFS->NNW, DBN->SSE, PSN->NNE, REN->NNE, FWI->NNW, MPO->SSE, JDS->NNW, GCY->NNE, WMS->NNE, JMS->NNE, SWS->NNW, PMY->NNE, WAD->NNE, TAR->NNE, RPR->NNE, PWS->NNE, EJD->WSW, CPR->NNE, AVI->NNE, MTH->NNE, CGH->NNE, MKN->WSW, HFE->NNW, SCS->NNE, DGR->NNE, IGN->NNE, CAR->NNW, JAE->NNE, OGZ->NNE, RLN->SSE, AGI->SSE, ACI->NNE, CAH->SSE, LVN->NNE, DLT->SSE, RCR->NNE, CTS->NNE, AJS->SSE, NHI->NNE, RHA->NNW, RMN->NNE, RHD->SSE, SBM->NNW, PSO->NNE, RDL->NNW, DET->NNE, KWR->NNE, PSL->SSE, TEN->NNW, SME->NNE, WLB->NNE, RHE->NNE, RJY->SSE, SJH->NNE, DHR->SSE, HJO->NNE, RLS->NNE, KLN->WSW, SBK->NNE, HKA->NNE, KWY->NNE, WFS->NNW, MBM->SSE, RCG->SSE, APT->NNE, TMN->NNE, FJT->WSW, KKI->NNE, BCG->NNE, MKA->NNE, KKA->NNE, SGA->NNW, BLE->NNE, TWD->SSE, EGR->NNE, ABE->NNW, SCR->NNE, DSF->NNW, RDN->NNE, JWB->NNW, VMA->SSE, MLE->NNE, CEH->NNE, MRH->NNE, JMA->NNE, JMT->NNE, CGY->NNE, RJZ->NNW, HMN->WSW, DJA->NNE, NMA->NNE, MMY->NNE, MRE->NNE, SMA->NNE, MMA->NNE, JMQ->NNE, LSR->NNW, CMY->NNE, MNA->NNE, ANV->SSE, SNN->NNE, DMN->NNW, FJL->NNE, SOL->NNE, RGF->NNE, EGL->NNE, RJE->NNE, GMR->NNE, MBY->NNE, SML->NNE, AJT->NNE, PAS->NNE, API->NNE, SDN->NNE, BAN->NNE, JJR->SSE, GGH->NNW, MBT->NNE, GDE->NNE, MSR->SSE, LMN->NNW, PST->NNE, KRA->NNE, ESO->NNE, ASO->NNE, PSA->NNE, UJT->NNE, MRZ->WSW, SER->NNW, RSN->NNE, RSR->NNW, JPY->NNE, DLD->NNE, ASA->SSE, HAN->SSE, JAP->SSE, MFR->NNE, MMH->NNE, AJU->SSE, MSL->NNW, PSY->NNE, FSM->NNE, PSZ->SSE, CSN->NNE, TJY->WSW, MDI->NNE, TTI->NNE, ETN->NNE, MRK->NNE, RMS->NNE, REZ->NNE, TBR->NNE, HWG->NNE, SCG->NNW, JLN->NNE, JSG->NNE, EHR->NNE, LHS->NNE, JWR->NNE, SAS->NNE, CGS->NNE, MET->NNE, KWN->WSW, AWN->NNE, HRR->NNE, WHF->NNE, RGE->SSE, HMG->NNE, GWZ->NNE, XYF->NNE, JEN->NNE, BLW->NNE}.
location_of_Person := {BIW->Peoria, KRS->Springfield, TLR->Peoria, VAA->Peoria, JRT->Springfield, AMR->Peoria, MES->Peoria, JAD->Peoria, MJR->Springfield, JRS->Springfield, HCN->Peoria, DAN->Springfield, CWT->Springfield, DCN->Peoria, SWR->Peoria, TBG->Springfield, LVO->Peoria, ECA->Springfield, MAI->Peoria, JCO->Macomb, DWO->Peoria, AJH->Peoria, CAE->Peoria, MRL->Peoria, FTR->Peoria, SJO->Peoria, DHY->Urbana, DHE->Peoria, CWU->Peoria, EAZ->Peoria, RFS->Peoria, JWS->Peoria, RVY->Peoria, PMO->Peoria, RGR->Peoria, LLR->Peoria, FEE->Springfield, ADS->Peoria, CFS->Joliet, DBN->Peoria, PSN->Peoria, REN->Peoria, FWI->Peoria, MPO->Peoria, JDS->Peoria, GCY->Peoria, WMS->Springfield, JMS->Springfield, SWS->Springfield, PMY->Peoria, WAD->Springfield, TAR->Peoria, RPR->Peoria, PWS->Peoria, EJD->Peoria, CPR->Peoria, AVI->Springfield, MTH->Joliet, CGH->Springfield, MKN->Peoria, HFE->Carbondale, SCS->Peoria, DGR->Springfield, IGN->Springfield, CAR->Peoria, JAE->Springfield, OGZ->Peoria, RLN->Peoria, AGI->Peoria, ACI->Peoria, CAH->Peoria, LVN->Springfield, DLT->Peoria, RCR->Peoria, CTS->Peoria, AJS->Peoria, NHI->Carbondale, RHA->Carbondale, RMN->Springfield, RHD->Peoria, SBM->Peoria, PSO->Peoria, RDL->Joliet, DET->Springfield, KWR->Peoria, PSL->Peoria, TEN->Springfield, SME->Springfield, WLB->Peoria, RHE->Peoria, RJY->Springfield, SJH->Cairo, DHR->Peoria, HJO->Carbondale, RLS->Peoria, KLN->Peoria, SBK->Cairo, HKA->Carbondale, KWY->Peoria, WFS->Peoria, MBM->Peoria, RCG->Peoria, APT->Peoria, TMN->Peoria, FJT->Peoria, KKI->Carbondale, BCG->Urbana, MKA->Carbondale, KKA->Peoria, SGA->Springfield, BLE->Peoria, TWD->Peoria, EGR->Peoria, ABE->Peoria, SCR->Peoria, DSF->Springfield, RDN->Peoria, JWB->Peoria, VMA->Peoria, MLE->Macomb, CEH->Springfield, MRH->Peoria, JMA->Carbondale, JMT->Peoria, CGY->Springfield, RJZ->Peoria, HMN->Springfield, DJA->Peoria, NMA->Carbondale, MMY->Peoria, MRE->Peoria, SMA->Joliet, MMA->Carbondale, JMQ->Carbondale, LSR->Peoria, CMY->Peoria, MNA->Carbondale, ANV->Peoria, SNN->Macomb, DMN->Peoria, FJL->Springfield, SOL->Evansville, RGF->Springfield, EGL->Peoria, RJE->Macomb, GMR->Peoria, MBY->Peoria, SML->Springfield, AJT->Peoria, PAS->Peoria, API->Springfield, SDN->Peoria, BAN->Peoria, JJR->Springfield, GGH->Peoria, MBT->Peoria, GDE->Peoria, MSR->Peoria, LMN->Peoria, PST->Springfield, KRA->Peoria, ESO->Springfield, ASO->Carbondale, PSA->Springfield, UJT->Springfield, MRZ->Peoria, SER->Peoria, RSN->Joliet, RSR->Peoria, JPY->Peoria, DLD->Urbana, ASA->Peoria, HAN->Peoria, JAP->Peoria, MFR->Springfield, MMH->Joliet, AJU->Springfield, MSL->Springfield, PSY->Springfield, FSM->Springfield, PSZ->Peoria, CSN->Joliet, TJY->Springfield, MDI->Peoria, TTI->Carbondale, ETN->Peoria, MRK->Peoria, RMS->Peoria, REZ->Evansville, TBR->Peoria, HWG->Peoria, SCG->Joliet, JLN->Peoria, JSG->Peoria, EHR->Peoria, LHS->Peoria, JWR->Springfield, SAS->Peoria, CGS->Springfield, MET->Peoria, KWN->Springfield, AWN->Springfield, HRR->Macomb, WHF->Peoria, RGE->Springfield, HMG->Joliet, GWZ->Joliet, XYF->Peoria, JEN->Peoria, BLW->Peoria}.
gender_of_Person := {BIW->M, KRS->F, TLR->F, VAA->M, JRT->M, AMR->M, MES->M, JAD->M, MJR->M, JRS->M, HCN->M, DAN->M, CWT->M, DCN->M, SWR->M, TBG->M, LVO->M, ECA->M, MAI->F, JCO->M, DWO->M, AJH->M, CAE->M, MRL->M, FTR->M, SJO->M, DHY->M, DHE->M, CWU->M, EAZ->M, RFS->M, JWS->M, RVY->M, PMO->M, RGR->M, LLR->M, FEE->M, ADS->M, CFS->M, DBN->M, PSN->M, REN->F, FWI->M, MPO->M, JDS->M, GCY->M, WMS->M, JMS->M, SWS->M, PMY->M, WAD->M, TAR->M, RPR->M, PWS->M, EJD->F, CPR->M, AVI->F, MTH->M, CGH->M, MKN->M, HFE->M, SCS->M, DGR->M, IGN->M, CAR->M, JAE->M, OGZ->M, RLN->M, AGI->M, ACI->F, CAH->F, LVN->F, DLT->F, RCR->M, CTS->M, AJS->M, NHI->M, RHA->M, RMN->M, RHD->M, SBM->M, PSO->M, RDL->M, DET->M, KWR->M, PSL->F, TEN->M, SME->M, WLB->M, RHE->M, RJY->M, SJH->M, DHR->M, HJO->M, RLS->M, KLN->M, SBK->M, HKA->M, KWY->M, WFS->M, MBM->M, RCG->M, APT->M, TMN->M, FJT->M, KKI->M, BCG->M, MKA->M, KKA->M, SGA->F, BLE->M, TWD->M, EGR->F, ABE->M, SCR->M, DSF->M, RDN->M, JWB->F, VMA->M, MLE->M, CEH->M, MRH->M, JMA->M, JMT->F, CGY->M, RJZ->M, HMN->F, DJA->M, NMA->F, MMY->M, MRE->M, SMA->M, MMA->M, JMQ->F, LSR->M, CMY->M, MNA->M, ANV->M, SNN->F, DMN->M, FJL->M, SOL->M, RGF->M, EGL->M, RJE->M, GMR->M, MBY->F, SML->M, AJT->M, PAS->M, API->M, SDN->M, BAN->M, JJR->M, GGH->M, MBT->M, GDE->M, MSR->M, LMN->F, PST->M, KRA->M, ESO->M, ASO->F, PSA->M, UJT->M, MRZ->F, SER->M, RSN->M, RSR->M, JPY->M, DLD->F, ASA->M, HAN->M, JAP->M, MFR->M, MMH->M, AJU->M, MSL->M, PSY->M, FSM->M, PSZ->M, CSN->M, TJY->M, MDI->M, TTI->M, ETN->M, MRK->M, RMS->M, REZ->M, TBR->M, HWG->M, SCG->M, JLN->F, JSG->M, EHR->M, LHS->M, JWR->M, SAS->F, CGS->M, MET->F, KWN->M, AWN->M, HRR->M, WHF->M, RGE->M, HMG->F, GWZ->M, XYF->M, JEN->M, BLW->M}.
title_of_Person := {BIW->Assistant, KRS->Assistant, TLR->Adjunct, VAA->Deputy, JRT->Deputy, AMR->Deputy, MES->Consultant, JAD->Adjunct, MJR->Assistant, JRS->Assistant, HCN->Deputy, DAN->Adjunct, CWT->Adjunct, DCN->Adjunct, SWR->Adjunct, TBG->Assistant, LVO->Assistant, ECA->Assistant, MAI->Adjunct, JCO->Adjunct, DWO->Adjunct, AJH->Adjunct, CAE->Adjunct, MRL->Assistant, FTR->Adjunct, SJO->Adjunct, DHY->Adjunct, DHE->Adjunct, CWU->Assistant, EAZ->Assistant, RFS->Deputy, JWS->Adjunct, RVY->Adjunct, PMO->Assistant, RGR->Assistant, LLR->Assistant, FEE->Adjunct, ADS->Adjunct, CFS->Assistant, DBN->Adjunct, PSN->Adjunct, REN->Adjunct, FWI->Assistant, MPO->Assistant, JDS->Adjunct, GCY->Adjunct, WMS->Deputy, JMS->Adjunct, SWS->Assistant, PMY->Deputy, WAD->Adjunct, TAR->Assistant, RPR->Adjunct, PWS->Consultant, EJD->Adjunct, CPR->Deputy, AVI->Adjunct, MTH->Assistant, CGH->Adjunct, MKN->Assistant, HFE->Adjunct, SCS->Adjunct, DGR->Assistant, IGN->Assistant, CAR->Assistant, JAE->Assistant, OGZ->Consultant, RLN->Adjunct, AGI->Assistant, ACI->Assistant, CAH->Adjunct, LVN->Assistant, DLT->Adjunct, RCR->Adjunct, CTS->Deputy, AJS->Assistant, NHI->Assistant, RHA->Assistant, RMN->Deputy, RHD->Assistant, SBM->Assistant, PSO->Adjunct, RDL->Adjunct, DET->Assistant, KWR->Assistant, PSL->Assistant, TEN->Adjunct, SME->Consultant, WLB->Adjunct, RHE->Assistant, RJY->Deputy, SJH->Adjunct, DHR->Assistant, HJO->Assistant, RLS->Adjunct, KLN->Adjunct, SBK->Adjunct, HKA->Adjunct, KWY->Deputy, WFS->Adjunct, MBM->Assistant, RCG->Adjunct, APT->Adjunct, TMN->Assistant, FJT->Assistant, KKI->Adjunct, BCG->Adjunct, MKA->Assistant, KKA->Assistant, SGA->Assistant, BLE->Assistant, TWD->Assistant, EGR->Adjunct, ABE->Adjunct, SCR->Adjunct, DSF->Adjunct, RDN->Adjunct, JWB->Deputy, VMA->Adjunct, MLE->Adjunct, CEH->Assistant, MRH->Deputy, JMA->Deputy, JMT->Assistant, CGY->Adjunct, RJZ->Adjunct, HMN->Assistant, DJA->Adjunct, NMA->Assistant, MMY->Assistant, MRE->Assistant, SMA->Adjunct, MMA->Deputy, JMQ->Assistant, LSR->Adjunct, CMY->Adjunct, MNA->Adjunct, ANV->Assistant, SNN->Deputy, DMN->Adjunct, FJL->Assistant, SOL->Assistant, RGF->Adjunct, EGL->Adjunct, RJE->Adjunct, GMR->Assistant, MBY->Assistant, SML->Assistant, AJT->Assistant, PAS->Assistant, API->Adjunct, SDN->Deputy, BAN->Assistant, JJR->Adjunct, GGH->Adjunct, MBT->Adjunct, GDE->Deputy, MSR->Assistant, LMN->Assistant, PST->Assistant, KRA->Adjunct, ESO->Adjunct, ASO->Assistant, PSA->Assistant, UJT->Assistant, MRZ->Assistant, SER->Assistant, RSN->Assistant, RSR->Adjunct, JPY->Adjunct, DLD->Assistant, ASA->Consultant, HAN->Deputy, JAP->Adjunct, MFR->Adjunct, MMH->Adjunct, AJU->Assistant, MSL->Adjunct, PSY->Assistant, FSM->Assistant, PSZ->Assistant, CSN->Assistant, TJY->Adjunct, MDI->Consultant, TTI->Assistant, ETN->Assistant, MRK->Adjunct, RMS->Adjunct, REZ->Adjunct, TBR->Deputy, HWG->Assistant, SCG->Adjunct, JLN->Assistant, JSG->Deputy, EHR->Assistant, LHS->Adjunct, JWR->Assistant, SAS->Adjunct, CGS->Assistant, MET->Assistant, KWN->Assistant, AWN->Adjunct, HRR->Adjunct, WHF->Assistant, RGE->Adjunct, HMG->Assistant, GWZ->Assistant, XYF->Assistant, JEN->Deputy, BLW->Deputy}.
group_of_Person := {BIW->12, KRS->12, TLR->9, VAA->10, JRT->5, AMR->12, MES->5, JAD->6, MJR->1, JRS->4, HCN->2, DAN->3, CWT->5, DCN->6, SWR->8, TBG->12, LVO->2, ECA->11, MAI->3, JCO->5, DWO->11, AJH->3, CAE->4, MRL->6, FTR->4, SJO->5, DHY->11, DHE->10, CWU->3, EAZ->10, RFS->12, JWS->4, RVY->12, PMO->2, RGR->12, LLR->9, FEE->12, ADS->3, CFS->10, DBN->7, PSN->11, REN->6, FWI->5, MPO->4, JDS->2, GCY->1, WMS->7, JMS->5, SWS->4, PMY->10, WAD->4, TAR->1, RPR->5, PWS->6, EJD->8, CPR->7, AVI->6, MTH->4, CGH->6, MKN->11, HFE->10, SCS->2, DGR->10, IGN->4, CAR->8, JAE->6, OGZ->7, RLN->4, AGI->9, ACI->11, CAH->7, LVN->2, DLT->12, RCR->9, CTS->6, AJS->2, NHI->10, RHA->7, RMN->4, RHD->7, SBM->5, PSO->3, RDL->3, DET->1, KWR->10, PSL->7, TEN->8, SME->1, WLB->11, RHE->7, RJY->1, SJH->3, DHR->2, HJO->11, RLS->5, KLN->2, SBK->8, HKA->12, KWY->7, WFS->7, MBM->8, RCG->1, APT->6, TMN->12, FJT->3, KKI->7, BCG->8, MKA->10, KKA->9, SGA->9, BLE->1, TWD->5, EGR->3, ABE->6, SCR->9, DSF->4, RDN->7, JWB->8, VMA->11, MLE->11, CEH->8, MRH->2, JMA->4, JMT->5, CGY->1, RJZ->9, HMN->1, DJA->11, NMA->2, MMY->7, MRE->9, SMA->7, MMA->10, JMQ->9, LSR->8, CMY->2, MNA->9, ANV->3, SNN->2, DMN->9, FJL->10, SOL->1, RGF->2, EGL->10, RJE->11, GMR->3, MBY->2, SML->6, AJT->9, PAS->2, API->3, SDN->2, BAN->5, JJR->3, GGH->9, MBT->12, GDE->9, MSR->1, LMN->12, PST->2, KRA->12, ESO->11, ASO->1, PSA->10, UJT->6, MRZ->3, SER->6, RSN->4, RSR->3, JPY->8, DLD->4, ASA->8, HAN->7, JAP->1, MFR->4, MMH->8, AJU->1, MSL->9, PSY->5, FSM->10, PSZ->4, CSN->7, TJY->5, MDI->5, TTI->6, ETN->12, MRK->11, RMS->9, REZ->1, TBR->6, HWG->5, SCG->12, JLN->5, JSG->8, EHR->7, LHS->4, JWR->12, SAS->11, CGS->10, MET->2, KWN->11, AWN->9, HRR->8, WHF->11, RGE->4, HMG->8, GWZ->5, XYF->9, JEN->7, BLW->11}.
number_in_Group := {1->16, 2->19, 3->16, 4->19, 5->19, 6->16, 7->19, 8->16, 9->19, 10->16, 11->18, 12->17}.
Score := 82494.