Project 3: Menu

You are managing the menu for a family of p people. Your job is to order foods that make the family as happy as possible, where the happiness is determined by the level of satisfaction of the least satisfied family member. Each family member has their own food preferences that determine what they like and dislike. Additionally, people don't like repeating foods; satisfaction is diminished if you eat the same food two days in a row, for example.

Meals are divided into breakfast, lunch and dinner, each with their own food types and constraints. There are 10 kinds of breakfast food, 10 kinds of lunch food, and 20 kinds of dinner food. We'll call them $B_1,\ldots,B_{10}$, $L_1,\ldots,L_{10}$, $D_1,\ldots,D_{20}$. Each person in the family has a personal satisfaction for each food type, which is a number between 0 and 1. The closer that number is to 1, the more that person likes it.

For breakfast and lunch, each person can be assigned their own food type from the available food in the pantry. However, for dinner all family members eat the same food. Ideally, there are at least p units of the chosen dinner food in the pantry. However, if there are only k<p items, then the satisfaction of each family member is scaled by k/p.

For breakfast, there is no penalty for repeating a food you had recently. For lunch and dinner, however, the satisfaction of a family member is multiplied by d/(d+1) if you ate that food d days ago. Thus, the net satisfaction of repeating a lunch or dinner food on the day after eating the same food is halved. (This scaling only happens once, based on the most recent time the food was eaten.)

Your pantry has capacity C, which is at least 21p, the number of meals needed per week for the family, but could be significantly larger. You get to stock your pantry once each week, filling any empty slots using a shopping list. The shopping procedure is complicated by the fact that each week, only half of the foods (i.e., half the breakfast foods, half the lunch foods, and half the dinner foods) are available. Your shopping list is actually three lists, one for each meal type, together with a limit for each meal type. For example, suppose you have 100 slots available in your pantry. You may decide that you want to order 25 breakfast foods, 25 lunch foods, and 50 dinner foods.

Let's look at a lunch list for example. You might write your list as

$$L_3,L_3,L_4,L_4,L_1,L_1,L_3,\ldots$$

With 25 lunch foods to order, the simulator will read the list from left to right, checking whether that item is available, and if so adding one unit to your pantry. The simulator continues down the list until either the list ends, or 25 items have been added to your pantry. An analogous process happens for breakfast and dinner foods. Each week you get to come up with new lists. For example, you might bias the list based on what's left in the pantry. The subset of available foods is determined at random by the simulator each week, and you don't know what will be available when you write your lists. (Side puzzles: (a) what is the shortest list that is guaranteed to yield 25 available items? (b) what is the longest list for which it is possible that 25 available items will not be found?)

Having filled your pantry, you then plan meals for the week, assigning breakfast, lunch and dinner foods to each person according to the constraints mentioned above. If you don't have enough meals to go around, a person missing a meal gets a satisfaction of zero for that meal. After planning the week's meals, the simulator will calculate the level of satisfaction for each family member, and adjust your pantry inventory. You then get to repeat the process over additional weeks. Your optimization goal, over the course of many weeks, is to maximize the average satisfaction of the least-satisfied family member.

There are several parameters to the simulation. The number of weeks w will be large enough (e.g., w=52) to overcome start-up effects and reflect a longer-term equilibrium. The preferences of family members are given at the start of the simulation in a configuration file. We'll explore different kinds of family structures, such as families with shared preferences, families with disparate preferences, and families with one or two fussy eaters. We'll also explore different family sizes by varying p. For the first deliverable, each group will be asked to propose a family structure (p value, together with preference lists) that they find interesting. We'll also vary C, aiming to cover a range of settings between having barely enough capacity and having plentiful capacity.

The details of the simulator will be provided later. It will give you access to your inventory, and to a history of meal allocations that you have previously made. The simulator will use a random number seed to generate the available/unavaliable items, so that you can get repeatable runs by using the same seed.

At the end of the project we'll run tournaments using various parameters (some of which you won't have seen before) to see how well your programs do at keeping families happy.

Some things to think about:

• Your first shopping list occurs when the pantry is empty and there is no history of prior meals to cause repetition penalties. Do you do something special/different for the first list?
• Should you balance capacities among breakfast/lunch/dinner foods, or might an unbalanced allocation be superior?