Christmas Model
DMCommunity’s January 2023 challenge, called “Christmas Model”, tasks us with finding the optimal assignment of gifts to people, given a specific budget.
Christmas Model
This model defines a set of people, a set of gifts, and the happiness level and cost of each gift. The objective is to maximize the total happiness, subject to the budget constraint that the total cost of the gifts must be less than or equal to the budget, and the constraint that each person can only receive one gift.
Here is a sample of test data:
PEOPLE: “Alice”, “Bob”, “Carol”, “Dave”, “Eve”
GIFTS: “Book”, “Toy”, “Chocolate”, “Wine”, “Flowers”
GIFT COSTS: 10, 20, 5, 15, 7
HAPPINESS:
“Book”: [3, 2, 5, 1, 4]
“Toy”: [5, 2, 4, 3, 1]
“Chocolate”: [1, 3, 4, 5, 2]
“Wine”: [2, 5, 3, 4, 1]
“Flowers”: [4, 3, 1, 2, 5]
BUDGET: 50
By analysing the prompt, we can see that we need to:
Count the total happiness.
Count the total cost.
Ensure the gifts fit within our budget.
Ensure each person only gets one gift.
Before we can do that though, we need to introduce the different symbols that we will be using by listing them in our glossary. Firstly, we introduce our types, which, broadly speaking, represent domains of values. In this problem, there are three such domains: people, gifts, and integers.
| Type | ||
|---|---|---|
| Name | Type | Values |
| Person | string | Alice, Bob, Carol, Dave, Eve |
| Gift | string | Book, Toy, Chocolate, Wine, Flowers |
Note that integers are a standard type in cDMN, and do not need to explicitly be declared.
Next, we need a way to assign a gift to a person, a cost to each gift and a happiness to each (Person, Gift) pair. One thing these three concepts have in common is that they each represent a mapping of one or more types on a single type. In cDMN, we can model these using functions.
| Function | |
|---|---|
| Name | DataType |
| gift of Person | Gift |
| cost of Gift | Int |
| happiness of Person getting Gift | Int |
For example, the function gift of Person has one argument, Person, and maps it on type Gift. Because each person will be mapped on exactly one gift, this representation already adheres to requirement 4 from above.
Lastly, we need a symbol to represent the total amount of happiness, and the total cost. Here, we can use constants, i.e., symbols that have exactly one value.
| Constant | |
|---|---|
| Name | Type |
| TotalHappiness | Int |
| TotalCost | Int |
Now that are glossary is finished, we can enter the data which we know up front. In this case, we already know two things: the cost of each item, and the happiness of each item for each person. In cDMN, we enter these via Data Tables.
| Cost | ||
|---|---|---|
| D | Gift | cost of Gift |
| Book | 10 | |
| Toy | 20 | |
| Chocolate | 5 | |
| Wine | 15 | |
| Flowers | 7 | |
| Happiness | |||
|---|---|---|---|
| D | Person | Gift | happiness of Person gettin Gift |
| Alice | Book | 3 | |
| Alice | Toy | 5 | |
| Alice | Chocolate | 1 | |
| ... | ... | ... | ... |
Now that that’s done, we can focus on modelling our three remaining requirements.
R1 & R2
Count the total happiness and the total cost.
To count the total happiness, we simply count the individual happiness of each person depending on what gift they’re getting. Similarly, for the gift, we count the individual cost of each gift that is given to a person. We can model this in the following C+ (Sum) table:
| Count happiness and cost | |||||
|---|---|---|---|---|---|
| C+ | Person | Gift | gift of Person | TotalHappiness | TotalCost |
| 1 | - | - | Gift | happiness of Person getting Gift | cost of Gift |
“Sum the happiness of each Person if they are getting Gift.” and “Sum the cost of each Gift that has been given to a Person.”
R3
Ensure the gifts fit within our budget.
Our last requirement is expressing the constraint that we must not go over budget. This is very straightforwardly expressed in a constraint (E*) table.
| Budget | |
|---|---|
| E* | TotalCost |
| 1 | ≤ 50 |
Goal
Maximize total happiness
Finally, we want to express that our goal is to optimize the total happiness.
| Goal |
|---|
| Maximize TotalHappiness |
Now that our cDMN specification is finished, we can run the solver to get the optimal gift assignment! This results in the following solution:
Model 1
==========
gift_of_Person := {Alice -> Flowers, Bob -> Wine, Carol -> Book, Dave -> Chocolate, Eve -> Flowers}.
happiness_of_Person_getting_Gift := {(Alice, Book) -> 3, (Alice, Toy) -> 5, (Alice, Chocolate) -> 1, (Alice, Wine) -> 2, (Alice, Flowers) -> 4, (Bob, Book) -> 2, (Bob, Toy) -> 2, (Bob, Chocolate) -> 3, (Bob, Wine) -> 5, (Bob, Flowers) -> 3, (Carol, Book) -> 5, (Carol, Toy) -> 4, (Carol, Chocolate) -> 4, (Carol, Wine) -> 3, (Carol, Flowers) -> 1, (Dave, Book) -> 1, (Dave, Toy) -> 3, (Dave, Chocolate) -> 5, (Dave, Wine) -> 4, (Dave, Flowers) -> 2, (Eve, Book) -> 4, (Eve, Toy) -> 1, (Eve, Chocolate) -> 2, (Eve, Wine) -> 1, (Eve, Flowers) -> 5}.
cost_of_Gift := {Book -> 10, Toy -> 20, Chocolate -> 5, Wine -> 15, Flowers -> 7}.
TotalHappiness := 24.
TotalCost := 44.
Elapsed Time:
0.797s
With a total happiness of 24, the optimal assignment is as follows:
Alice: Flowers
Bob: Wine
Carol: Book
Dave: Chocolate
Eve: Flowers
And with a total cost of 44, we still have enough money left to buy ourselves some chocolates too. :-)