Learn the fundamentals of Microsoft SQL Server, a relational database management system that stores and retrieves data when requested by other software applications.

I have here what I think is a classical O.R. (operations research) problem. I'm looking to formulate it mathematically and look at the options available to solve it.

We have a list of say 100 recipes.

These recipes combined use 400 ingredients.

The quantity of ingredients required for all the recipes could be defined by a matrix dimension 100 x 400.

We can combine recipes into meal plans, so that the ingredients required for a meal plan is the total of the ingredients required for each recipe in the meal plan.

Each ingredient has an associated cost, that varies depending on the quantity bought.

Say the cost variations can be expressed with no more than 5 cost buckets per ingredient. Eg.

Bucket, Cost / kg

< 1kg, £4.00

1-5kg, £3.50

5-20kg, £3.00

20-100kg, £2.80

> 100kg, £2.50

The ingredient costs can be expressed in two matrices each of dimension 400 x 5:

a) One matrix 400 x 5 giving the buckets for each ingredient

b) Another matrix 400 x 5 giving the unit costs per ingredient and bucket number (1 to 5)

A given meal plan will have a given ingredient requirement, with associated total cost determined via the above matrices.

Suppose we constrain the number of meals in the meal plan to say 4 meals, and these 4 meals must be different recipes. For simplicity (!) we have no other constraints for now.

Our objective is to choose our meal plan (4 meals) such that the total cost is minimised.

Questions:

1. How do we formulate this problem?

2. How can we solve it efficiently (ie least processing power)?

eg could I use simplex?

See https://en.wikipedia.org/wiki/Mathematical_optimization

Many thanks

We have a list of say 100 recipes.

These recipes combined use 400 ingredients.

The quantity of ingredients required for all the recipes could be defined by a matrix dimension 100 x 400.

We can combine recipes into meal plans, so that the ingredients required for a meal plan is the total of the ingredients required for each recipe in the meal plan.

Each ingredient has an associated cost, that varies depending on the quantity bought.

Say the cost variations can be expressed with no more than 5 cost buckets per ingredient. Eg.

Bucket, Cost / kg

< 1kg, £4.00

1-5kg, £3.50

5-20kg, £3.00

20-100kg, £2.80

> 100kg, £2.50

The ingredient costs can be expressed in two matrices each of dimension 400 x 5:

a) One matrix 400 x 5 giving the buckets for each ingredient

b) Another matrix 400 x 5 giving the unit costs per ingredient and bucket number (1 to 5)

A given meal plan will have a given ingredient requirement, with associated total cost determined via the above matrices.

Suppose we constrain the number of meals in the meal plan to say 4 meals, and these 4 meals must be different recipes. For simplicity (!) we have no other constraints for now.

Our objective is to choose our meal plan (4 meals) such that the total cost is minimised.

Questions:

1. How do we formulate this problem?

2. How can we solve it efficiently (ie least processing power)?

eg could I use simplex?

See https://en.wikipedia.org/wiki/Mathematical_optimization

Many thanks

Do more with

EXPERT OFFICE^{®} is a registered trademark of EXPERTS EXCHANGE^{®}

Not only does a meal have a cost but the total cost will depend on the *number* of meals which isn't presented that I can see.

How many meals do you want to produce in each plan?

It seems clear that the more meals, the lower the cost.

And, *maybe* the quantity doesn't matter if the quantity price breaks track - but I think this aspect is likely important given your description.

If it doesn't matter then you can choose according to single meal plans independent of quantity.

But, you may need to do the analysis before you know about this.

You are correct.

Is this a practical problem for a catering service or a computer science problem where you must have the exact answer even if the difference in a few lowest cost plans is 1 cent?

If practical, then you could compute the cost of the 100 meals, and where there is a big jump in price, throw those away. Maybe now, you only have 20 meals to deal with; and computationally, that is insignificant; and may even give you a close answer. You don't even have to sort the 4 million values, since you only care about the minimum value. Every time you get a value, compare it with the current minimum. If the new minimum is lowest, the save that new value as the current value and save the meal plan.

BTW, computing the cost of 4 million possible choices of meal plan is not computationally very large. To get the different meal plans, just consider 4 bits of a 100-bit word, and start permuting them for all combinations.

I understand 4 meals per "plan" but not how many instances of the plan?

Otherwise one may as well compute the cost of a single plan and disregard the quantity price breaks for ingredients.

What am I missing here?

In other words, I'm missing:

"We want to produce 3,000 meal plans (i.e. 4 meals each). What is the optimum plan?"

2. Calculate the cost for each of your 100 meal recipes, based on (1)

3. Sort the list of meals-and-costs (2) in ascending order of the cost value.

The top/first items in the sorted list (3) is your desired result.

Your approach is another variant of a "practical" approach, but it likely will not give the correct answer from a computer science perfection point of view; although it may very well be a good close answer.

In any case, no need to sort 100 meal recipes, since as you calculate the each meal, you immediately just keep the top 4 meals.

But it may be that the lowest cost meal-plan will consist of 4 meals in the top 50 lowest cost recipes.

My approach is meant to be extendable to different top-N values (not just 4), be more efficient by only sorting once. Also, my approach allows for multi-week meal planning. Also, this is a 100% coverage solution.

>> you could

>>Re computing meals individually, of course this ignores the savings from combining meals that share ingredients.

Were you referring to my above statement in italics? The point I was trying to make is that probably by throwing away the higher cost meals, then you have much less computations to process. Even if you throw away only the 25 highest cost meals, you now only have 1M meal plans to compute instead of 4M. Keeping only the lowest cost 30 meals results in only 27K meal plans to compare.

20C4 = 4845

30C4 = 27405

50C4 = 230300

75C4 = 1215450

(Unfortunately, I don't know the analysis of how to compute the confidence interval of 95% that we will be within 3% of an optimal solution. Possibly a sampling of the remaining 80 meals and meal plans?)

Fred - ah ok i think i get your question. We are making a fixed number only, eg 1 instance. This then acts as a scalar on the recipe quantities. ie the same as altering the recipes to make them bigger/smaller.I am still missing something.

If you produce 100 plans of 4 meals each, for each 4-recipe combination there is a calculable cost for 4 meals.

If you produce 10,000 plans of 4 meals each, for each 4-recipe combination there is a

The unit cost per meal, or per set of 4 recipes, will be different because of the ingredient cost breaks.

Otherwise, why did you bother to mention the price breaks in the first place?

The amount of ingredient goes with the recipe so that's "fixed" per meal.

The cost of ingredient goes with the quantity, so that's NOT "fixed" per meal and goes with the quantity price breaks.

So, in order to optimize, you need the quantity to be produced.

Thanks you on the clarification on the (unit) cost columns.

```
4
7
9
10
12
13
16
18
23
25
26
30
36
45
45
46
48
53
61
65
68
85
89
95
97
```

Do these numbers relate to the ingredient name or the row in the worksheet?How many Kg of each ingredient is used for a recipe? I'm a little confused about the Generator worksheet contents.

I've found that communicating requirements and interpreting the data is important to both understanding the problem and solving it. The original description of the problem differs from the contents of the Google doc.

Fred, I'm not sure if i understand. We're only looking for one instance of a meal plan. So any quantity variation comes about only from the choice of which 4 meals to include, since some meals share common ingredients

Here is what I'm thinking:L

You are asking for an optimum solution to meal plan selection. But, without further analysis, one knows that the ingredients vary from plan to plan and that you have provided price cut information. In fact, price cut information (i.e. quantity discounts) are

I can't be sure what you mean by "one instance of a meal plan".

Do you mean that you want to know which, single, meal plan is optimum? That's what I thought was your objective.

But, since price breaks affect the outcome then one would necessarily need to know the intended quantity.

Here's an example:

Meal plan X is optimum at low quantities going from 1 to 100. There is no lower cost meal plan at this quantity.

Meal plan Y is optimum at higher quantities; say over 1,000. There is no lower cost meal plan at this quantity.

etc.

It *may* be that plan X is always optimum but I see no guarantee of that. So it seems that quantity must be included.

What am I missing?

Consider a simple recipe which includes the lowest-price ingredients at low quantity. And, what if those ingredients don't have much of a price break?

Then consider that there's a different recipe which includes (different) lowest-price ingredients at some higher quantity which results from a very attractive price break?

Isn't it then clear that the quantity affects the selection of an optimum solution?

Isn't it clear that a single cost does not represent a meal plan unit cost

There are ingredients given for each meal.

There are 100 meals defined.

There are ingredients given for each meal.

There are, in total, 400 ingredients over the 100 meals.

A meal plan consists of 4 unique meals.

For each ingredient, there are an arbitrarily-selected set of 5 price points as a function of quantity. In other words, there is provision for a quantity price break for each ingredient. Mathematically the price break may be zero - meaning that the unit price remains the same for all quantities. So, in the end, there is a unit price at each quantity which *may* decrease as quantity increases. The numbers are different for each ingredient.

The optimization objective is to find the meal plan with the lowest cost.

Because of the quantity price breaks being independent amongst the ingredients, the optimum solution is necessarily a function of the quantity of the meal plans to be produced.

Does that about sum it up?

There are ingredients given for each meal.

There are N meals defined.

There are ingredients given for each meal.

There are, in total, M ingredients over the N meals.

A meal plan consists of K unique meals.

For each ingredient, there are an arbitrarily-selected set of L price points as a function of quantity. In other words, there is provision for a quantity price break for each ingredient. Mathematically the price break may be zero - meaning that the unit price remains the same for all quantities. So, in the end, there is a unit price at each quantity which *may* decrease as quantity increases. The numbers are different for each ingredient.

The optimization objective is to find the meal plan with the lowest cost.

Choosing the meal plan with the lowest cost requires that each ingredient price point be selected.

Selecting each ingredient price point requires that the number of meals; thus the quantity of ingredients; thus the cost of ingredients be given.

Notation: Meal plan k, Meal m, ingredient n (in kg), total quantity of meal plans to be produced Q:

Cost of meal plan k = sum over m,n,Q

Example:

Cost of meal plan 44:

Total quantity of each ingredient for meal plan 44.

How many meal plans will be produced?

The number of meal plans to be produced yields the quantity of each ingredient for that selection.

The quantity of each ingredient for that selection, yields the unit cost of each ingredient.

The unit cost and quantity of each ingredient for the meal plan yields the cost of the meal plan for the given number of meal plans to be produced.

Optimization comes next.

I rather agree with phoffric.

An exhaustive approach that calculates the above and saves the lowest result is memory efficient and not very computationally intensive really.

It's called "brute force" search.

i.e.

Compute the cost of Meal Plan 1. Save the result Meal Plan Number and Cost.

Compute the cost of Meal Plan 2. If the result is less than the saved result, replace the saved result.

Compute the cost of Meal Plan 3. If the result is less than the saved result, replace the saved result.

etc.

Compute the cost of Meal Plan ~4,000,000. If the result is less than the saved result, replace the saved result.

Observe the saved result. It's the optimum solution.

```
5201.66 cost 5
6428.76 cost 11
7359.72 cost 3
7700.54 cost 91
7725.71 cost 76
7795.54 cost 33
7843.34 cost 53
8020.72 cost 40
8075.98 cost 95
8107.76 cost 9
8116.53 cost 55
8277.29 cost 23
8298.7 cost 80
8398.96 cost 1
8454.32 cost 94
8662.83 cost 49
9144.62 cost 78
9257.67 cost 50
9377.05 cost 56
9513.31 cost 19
9663.14 cost 68
9712.24 cost 96
9732.4 cost 90
9760.52 cost 93
9781.53 cost 61
9791.56 cost 26
9848.21 cost 85
9917.27 cost 69
9982.38 cost 15
10006.35 cost 71
10094.95 cost 7
10122.76 cost 72
10144.35 cost 10
10172.21 cost 8
10184.64 cost 20
10205.89 cost 2
10273.21 cost 89
10447.01 cost 52
10525.68 cost 18
10575.7 cost 64
10592.97 cost 54
10655.32 cost 46
10659.79 cost 4
10715.28 cost 6
10927.5 cost 84
10929.63 cost 22
11068.77 cost 59
11102.9 cost 34
11138.1 cost 35
11152.83 cost 44
11197.1 cost 58
11211.18 cost 14
11211.32 cost 16
11219.11 cost 27
11247.41 cost 97
11312.47 cost 77
11553.96 cost 28
11662.56 cost 47
11675.1 cost 31
11717.13 cost 21
11752.62 cost 42
11783.45 cost 67
11784.96 cost 37
11883.62 cost 32
11986.18 cost 62
12048.04 cost 17
12078.73 cost 79
12121.96 cost 81
12152.41 cost 51
12251.75 cost 92
12385.52 cost 45
12656.34 cost 38
12666.14 cost 65
12676.24 cost 82
12698.61 cost 98
12793.14 cost 29
12800.39 cost 41
12801.6 cost 66
12887.84 cost 87
12924.65 cost 75
12962.49 cost 57
12996.55 cost 73
13185.86 cost 70
13212.5 cost 83
13313.58 cost 25
13369.03 cost 36
13567.73 cost 74
13835.07 cost 86
13861.36 cost 88
13974.19 cost 63
14201.71 cost 12
14240.8 cost 48
14416.4 cost 30
14481.82 cost 60
14606.93 cost 24
15027.19 cost 13
15848.52 cost 100
15868.11 cost 39
16000.2 cost 99
18396.59 cost 43
```

The formula in the cost cells is this:```
=IF(M2<>"",M2*$L2,0)
```

Just to be quick:

Using the minCost in test data 1!Column L, makes no sense because it assumes the quantity is greater than or equal to the bucket 5 quantity.

And, from an optimization point of view, what if the bucket 3 price represented the need but the need was close to the bucket 4 quantity. Then you may well want to buy the bucket 4 quantity and surplus or discard what's left over because it would be an overall lower cost.

Some ingredients have an unlimited shelf life, such as salt, rice, and beans.

selecting the bucket 5 cost only doesn't seem to make any senseColumn L is a formula that produces the lowest unit cost value among all buckets for an ingredient.

If this happens to be the largest bucket in your sample data, it is either by coincidence or your design. Any bucket size is eligible to be the lowest unit cost. It is understandable that the largest bucket is the lowest unit cost for several reasons (packaging, shipping, economies of scale, etc.).

Do you understand what I did in algorithmic-ally?

My algorithm can be considered 'brute force'. I use all the data and only trim-the-tree by using the MIN() function to get a single unit cost value.

I tried to fix the spreadsheet to demonstrate a sensible approach.

It appears that you were getting there in the "generator" sheet but I ran out of time on that one.

I also had real trouble with Excel not behaving with the Test data 1 sheet - which is what took up the time.

In concept:

You would choose a quantity of meal plans to be produced (which is what I assume a "recipe" is and not just a recipe for a single meal).

You would compute the quantity of each ingredient for each meal plan.

You would select the bucket that would yield the lowest price for this plan:

Compute the cost for the exact total quantity (where the quantity is less than the next bucket quantity)

Compare this cost with the next bucket quantity.

If the next bucket cost is less than the multi-bucket cost then buy at the next bucket quantity to save money while yielding surplus ingredient.

Example: Ingredient 1 is $10/kg for up to 99.9kg. And you need 90kg for a total cost of $900. And, it is 9$/kg for >100kg. So, this is the break-even point as 100kg will cost $900 and 90kg will cost $900.

Formula for break-even is: Q1=Q2*B2/B1

So, in this case B1 = $10/kg

B2 = $9/kg

Q2 = 100kg

Q1 = 100kg*$9/$10 = 90kg

So, with this you can create a table, if you like, of break-even quantities and select from there according to the needed quantity.

If you need less, then buy less at the higher price.

If you need more, then buy even more at the lower price.

So, the meal plan cost will simply use some logic and arithmetic to select the ingredient cost. And this will vary from recipe to recipe.

To answer your question about Simplex: It looks like it may fit into that solution context but it also seems it's a lot harder than an exhaustive search would be.

Also, it seems to me that the issue of different shelf lives goes well beyond the original question and requires all sorts of specialized user-specific information.

And the selection of a time span is exactly what the simpler optimization here would cover would be for a week, a month, a semester, a year EACH. Since it's not scalar with respect to quantity, each optimum plan will be likely different.

To deal with the shelf like issues, I would suggest that the purchasing intervals be separated and an optimum purchase for each be selected .. subject to meal plan selection constraints.

In a first iteration, there would be a list of recipes greater than 4 but perhaps with some overlap (and perhaps not).

Perhaps you would separate the meal plans out so that the ingredients with long shelf lives are purchase, as you have done, at the minimum cost (bucket5 quantities) with the idea that these ingredients would be stockpiled at zero cost of storage.

Then you could compute meal plans with a mixture of ingredient prices as above.

etc.

Our objective is to choose our meal plan (4 meals) such that the total cost is minimised.So the emphasis has been on that problem.

Questions:

1. How do we formulate this problem?

And now you say:

a pretty good answer (eg 95% chance of being within 3% of optimal)

These are different objectives. So it appears we've wasted our time on the first one.

Now you say:

I can do the same for recipes 1-100 in several hours.So an approach isn't really unknown but the computation time is at issue.

You said:

Some ingredients have an unlimited shelf life, such as salt, rice, and beans.Then you said

:I am not interested in looking at shelf life etc at this pointSo I was just confirming that the shelf life aspect was NOT of concern right now even though the aspect was brought into the conversation.

>> computing the cost of 4 million possible choices of meal plan is not computationally very large

I was thinking of languages like C++. If using SQL, then I would expect the time to complete to be many times longer.

If you plan on using Access or other database, then the appropriate zone should be added to get the experts in that field.

If you require less than the break point but, at some level, approaching it, it's cheaper to purchase the break point quantity than to use the higher unit price. The price remains the same as the quantity grows until you need the same amount as the break point. Otherwise, the price goes up with quantity before hitting the price break quantity.

I ran Excel Solver in Evolutionary mode - repeatedly until there was no further improvement.

There was probably a 20% improvement from the first "best" solution to the last.

There was something that stopped the Simplex (linear programming) mode - that I didn't investigate.

Starting with recipes 1,2,3,4 it ended at 5, 11, 53, 80

$94,392 vs. $216,344 starting out.

Each run lasted well under 1 minute.

There was no attempt to make the formulation efficient and that seems likely to be possible even in the Excel context.

Meal-Plan-Selection.xlsx

I had noticed that you had a lower number but I didn't understand where it came from - no formulas that I saw in my copied spreadsheet.

Sumproduct does this:

It selects those ingredients that will be used (using a 1 or a 0). It multiplies that by the TOTAL cost of the quantity of the ingredient for the meal plan and unit cost of the ingredient at that quantity - which is calculated in a separate column. So you end up with a total cost of all the ingredients involved in the meal plan. i.e. all 4 recipes.

I didn't see where the plan numbers in T3-W3 were being picked up from AI6-AI9 (which are the Soiver variables) so I changed the former from constants to be simple transfers (+) from the latter. Now the Solver works and the result with the new weights, quantities and prices comes out to be: 31709 with 5,11,76,91.

I hope this helps.

## Premium Content

You need an Expert Office subscription to comment.Start Free Trial