Hamburger Challenge

This example is also taken from dmcommunity.org. It’s called Make a Good Burger.

Hamburger Challenge

A burger most include at least one of each item, and no more than five of each item. You must use whole items (for example, no half servings of cheese). The final burger must contain less than 3000 mg of sodium, less than 150 grams of fat, and less than 3000 calories. To maintain certain taste quality standards, you’ll need to keep the servings of ketchup and lettuce the same. Also, you’ll need to keep the servings of pickles and tomatoes the same. Below is a list of ingredients and their information.

Try to find the most, and least expensive burger possible using the following items.

Item Sodium (mg) Fat (g) Calories Cost
Beef Patty 50 17 220 0.25
Bun 330 9 260 0.15
Cheese 310 6 70 0.10
Onions 1 2 10 0.09
Pickles 260 0 5 0.03
Lettuce 3 0 4 0.04
Ketchup 160 0 20 0.02
Tomato 3 0 9 0.04

As always, we start by filling out the glossary. From the description of the problem, we immediately know that we will need a type for the items. Also, thinking ahead, we will also need a type for every number used in the problem (such as the number of calories). For this purpose, we create Item, and Nat (for natural number). Because having to type over every item in the Values column is cumbersome, we refer to the data table in which we will be writing down all the food names.

Type
Name Type Values
Item String See Data Table Nutritions
Nat Int [0..10000]

Next up, we need a way to assign each item their nutritional information. Since each item can only have one value for sodium, fat, calories and cost, we can model these best as functions!

Function
Name Type
Sodium of Item Nat
Fat of Item Nat
Calories of Item Nat
Cost of Item Nat
Number of Item Nat

We also need a way to find out the total amount of each nutritional value. Since there is only one burger, and only one total amount per attribute, we use constants here.

Constant
Name Type
Total Sodium Nat
Total Fat Nat
Total Calories Nat
Total Cost Nat

Now that our glossary is done, we can move on to the next step in modeling the challenge: the data.

Data

Inputting the nutritional values

In our glossary entry for Item, we wrote see DataTable Nutritions. This tells the cDMN solver to add all the values in the Item column of the data table to the list of possible values. Creating the data table is easy. We have one input column, Item, and 4 output columns (one for every nutritional value). This greatly shows one of the advantages of data tables: if the list of nutritional values is supplied in table format or as a CSV, all we need to do is copy and paste the values and change the header names.

Data Table: Nutritions
Item Sodium of Item Fat of Item Calories of item Cost of Item
1 Beef Patty 50 17 220 25
2 Bun 330 9 260 15
3 Cheese 310 6 70 10
4 Onions 1 2 10 9
5 Pickles 260 0 5 3
6 Lettuce 3 0 4 4
7 Ketchup 160 0 20 2
8 Tomato 3 0 9 4

Rule

The burger must contain at least one of each, and no more than five of each item.

This rule can be modeled as a simple constraint table. We evaluate every item, and specify that their amount is in the range of 1 to 5.

Number Constraint
E* Item Number of Item
1 - [1, 5]

Rule

The amount of lettuce and ketchup is the same, as well as pickles and tomatoes.

Once again, a contraint table suffices. In fact, we can even reuse our previous table by adding two rows. We evaluate each item of lettuce, and make sure that their amount is the same as the amount of ketchup, and repeat this for the pickles and the tomatoes. We could even add these rules to the previous table, since the two rules use the same input and output column.

Number Constraint
E* Item Number of Item
1 - [1, 5]
2 Lettuce Number of Ketchup
3 Pickles Number of Tomato

Rule

The burger must contain less than 3000mg of sodium, less than 150g of fat and less than 3000 calories.

This rule is a bit more complex, because we need to calculate these total values first. For each item, we calculate their number multiplied by their nutritional value and add all of those up to get the total, using the C+ hit policy. Then we use another E* to make sure we don’t cross the nutritional thresholds. Note how this second table doesn’t have any inputcolumns. Because we use constants, no inputs are needed.

Determine Nutrition
C+ Item Total Sodium Total Fat Total Calories Total Cost
1 - Number of Item * Sodium of Item Number of Item * Fat of Item Number of Item * Calories of Item Number of Item * Cost of Item

Nutrition Constraints
E* Total Sodium Total Fat Total Calories
1 < 3000 < 150 < 3000

Rule

Find the most expensive burger.

To maximize the total cost, we can add a Goal table. In this table, we need to specify the term we want to minimize, which in this case, is Total Cost.

Goal
Minimize Total Cost

We can now run our model using the cDMN solver. This results in the following output:

Number of models: 1
Model 1
=======
structure  : V {
  Calories = { Beef_Patty->220; Bun->260; Cheese->70; Ketchup->20; Lettuce->4; Onions->10; Pickles->5; Tomato->9 }
  Cost = { Beef_Patty->25; Bun->15; Cheese->10; Ketchup->2; Lettuce->4; Onions->9; Pickles->3; Tomato->4 }
  Fat = { Beef_Patty->17; Bun->9; Cheese->6; Ketchup->0; Lettuce->0; Onions->2; Pickles->0; Tomato->0 }
  Number = { Beef_Patty->1; Bun->1; Cheese->1; Ketchup->1; Lettuce->1; Onions->1; Pickles->1; Tomato->1 }
  Sodium = { Beef_Patty->50; Bun->330; Cheese->310; Ketchup->160; Lettuce->3; Onions->1; Pickles->260; Tomato->3 }
  Total_Calories = 598
  Total_Cost = 72
  Total_Fat = 34
  Total_Sodium = 1117
}

Elapsed Time:
0.050393

We are able to make a burger which only costs 72, and still meets (meats? :-) ) all the requirements.