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:

  1. Count the total happiness.
  2. Count the total cost.
  3. Ensure the gifts fit within our budget.
  4. 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.

DataTable: Cost
Gift cost of Gift
Book 10
Toy 20
Chocolate 5
Wine 15
Flowers 7

DataTable: Happiness
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. :-)