Optimisation problem

xenium
xenium used Ask the Experts™
on
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
Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Top Expert 2014

Commented:
Should bucket 4 be 21-100kg, £2.80?
Top Expert 2014

Commented:
will the bucket sizes be consistent between ingredients?

Author

Commented:
Buckets could vary by ingredient. I guess best to spec buckets at upper range only, eg, falls into bucket b if size  <=z
b, z, cost
1, 1, 4.00
2, 5, 3.50
3, 20, 3.00
4, 100, 2.80
5, 9999, 2.50
Exploring SQL Server 2016: Fundamentals

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

Top Expert 2014

Commented:
can we assume that all the units will be Kg?

Author

Commented:
Yes let's assume that for this question.
I sense a disconnect going from the two matrices described and into meals.
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.

Author

Commented:
The output should be just one meal plan, consisting of exactly 4 different meals.

I think there are just under 4 million possible choices of meal plan (100 choose 4 = 100!/96!4!) so arriving at a solution algorithmically would be preferred.
>> I think there are just under 4 million possible choices of meal plan
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.
The output can be one meal plan but, I believe, has to be tied to HOW MANY?
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?"
Top Expert 2014

Commented:
1. I go through the ingredients list, and find the minimum/lowest unit cost for each ingredient.
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.
@aikimark,
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.

Author

Commented:
Thanks all for your input. It's a bit of a head spinner... apologies if i have missed anything but we'll get there...

phoffric - it's a practical problem so if it can be shown that an approximate solution is say 95% likely to be within say 3% of an optimal solution that would be fine. And since as you say these numbers are not computationally very large then this could be tested fairly easily with a simulation.

Re computing meals individually, of course this ignores the savings from combining meals that share ingredients. This saving is amplified if the ingredient pack sizes are restricted to set sizes, resulting in some wastage if the pack is not all used up. I have not explicitly stated this here and won't change the question now, but that will be a follow-up to consider.

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.

aikimark - I'll need to think through that a bit more and get back to you!
Top Expert 2014

Commented:
I realize that any implementation could just store the top 4 values.  However, this approach also involves comparing the top-N list after every meal cost calculation.

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.
ERRATA: I left out a syllable that I highlighted
>> 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.

>>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?)

Author

Commented:
Thanks again. I'm going to try setup a simulation to test these approaches and report back.

Author

Commented:
Here is some test data (not entirely realistic but hopefully it has the required characteristics):

https://docs.google.com/spreadsheets/d/1wU_1gat9WbbEbMT3GW4FHic0iAVyZZOJcL2fXSxYkaE

Sheet 'test data 1' will remain static.

Sheet 'generator' also contains the data, plus formulae to regenerate new test data.

Sheet 'generator' also contains formulae to evaluate the cost of specific meal plans (4 meals). eg entering recipes 1,2,3,4 (in cell s2) gives a total cost of 4942.58 (cell V1)

Next steps:
1. I'll do some scripts to test the proposed solutions on this data, and compare this to the optimal solution (all 4 million)
2. Repeat 1 with different test data to check for consistency of results
Top Expert 2014

Commented:
Your test/sample data lacks bucket size.  I'm, or an algorithm, can not determine the unit cost from this data.

Author

Commented:
The 5 columns 'bucket' 1-5 are the sizes, the 5 columns 'price' 1-5 are the unit prices upto each bucket size.
Top Expert 2014

Commented:
I thought that each ingredient might have different size buckets.

Author

Commented:
Yes they do, hence the 5 columns for the bucket sizes. Or am i missing something..
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 different calculable cost for 4 meals.
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.
Top Expert 2014

Commented:
I meant that your previous answer to my question seemed to imply that different ingredients were shipped in different sized buckets.  Although there were many ingredients that had the same bucket sizes, this would vary between ingredients.

Thanks you on the clarification on the (unit) cost columns.
I don't see where bucket size matters at all.  The issue is quantity (in this case in kg.. but that's not important).  One can calculate the price per kg and apply the  price breaks there and not deal with buckets at all.
Top Expert 2014

Commented:
So, recipe 1 has 25 unique ingredients?
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

Open in new window

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.
Top Expert 2014

Commented:
@Fred

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.

Author

Commented:
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.

Author

Commented:
aikimark, i don't have access to check the details now, but the numbers in the recipe columns are the amount needed eg. kg, for the ingredient in that row.

Author

Commented:
aikimark, if there's a mismatch between the question and the doc i'll provide a revised version. In any case there will be other versions which may be the subject of followup questions.
xenium: sez:  
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 explicit in the matrices you suggested in the first place.  So, it seems clear that the quantity to be produced will affect the optimum selection.  
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 costEXCEPT at a given quantity?
OK.  I have reviewed things somewhat carefully and I get:

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?
More mathematically:
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.

Author

Commented:
Fred, many thanks for the extra input, I am going to have a closer look at that later today when I have a bit more time & space to concentrate on it.

Meanwhile here are some interim results from the test data I provided:

Using "brute force", but reducing the problem to just 20 recipes (1-20), the optimum solution for "test data 1" appears to be recipes 3,5,9,11 at a cost of 29609.31

With this test data, the combining of ingredients does not affect the choice of optimum solution, however it does move some meal plans up in ranking:

https://docs.google.com/spreadsheets/d/1wU_1gat9WbbEbMT3GW4FHic0iAVyZZOJcL2fXSxYkaE/edit#gid=1129649097

Author

Commented:
aikimark - to clarify re your previous question - recipe 1 has 30 ingredients as follows:

ingredient		recipe 1 quantity needed
ingredient 1	45
ingredient 3	16
ingredient 6	16
ingredient 9	23
ingredient 16	85
ingredient 21	97
ingredient 29	4
ingredient 56	12
ingredient 69	9
ingredient 86	12
ingredient 101	18
ingredient 128	95
ingredient 140	10
ingredient 141	7
ingredient 152	13
ingredient 153	4
ingredient 170	26
ingredient 175	23
ingredient 178	48
ingredient 188	53
ingredient 207	97
ingredient 222	30
ingredient 237	61
ingredient 289	89
ingredient 338	45
ingredient 366	65
ingredient 381	25
ingredient 386	46
ingredient 390	36
ingredient 391	68

Open in new window

Top Expert 2014

Commented:
got it.  thanks.
Top Expert 2014

Commented:
A filled down and right formula, a copy paste special (transform), and a sort, produces this list.  The first column is the minimum possible cost for the recipe.  The second column lets you know which recipe.  
Example: "cost 5" indicates this row contains the minimum cost calculation/value for recipe 5.
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

Open in new window

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

Open in new window

Note: column L contains the formula for the MIN() value of the bucket unit cost columns.
Top Expert 2014

Commented:
In an effort to show my work, I've attached the workbook.
Meal-plan-optimisation-ee-question-.xlsx
I'm trying to include the Quantity of Meal Plans into the spreadsheet.
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.
Top Expert 2014

Commented:
The number of buckets you'll need depends on the recipes you are going to cook.  You might use the same ingredient in several/all meals.  Once you've determined the lowest possible cost meals, you need to plan for the week/month/semester/year and do purchase planning.  Adding a waste minimizing constraint will likely add to the cost, since you will probably purchase bucket combinations that might not be the MIN() size for an ingredient.

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

Author

Commented:
Thanks again for your inputs. Sorry I ran out of time to look into this further today, but will try to catch up tomorrow.

Appreciate the problem setup is not entirely realistic, and I have not provided the context. But the intention is to get the ball rolling on the kind of techniques that might be employed to solve this kind of problem. I'll be aiming towards a solution that does not use "brute force", even though this will be useful for testing.

Author

Commented:
aikimark, sorry the approach of selecting the bucket 5 cost only doesn't seem to make any sense.

btw here is an exhaustive "brute force" implementation in MS Access (not the most efficient but it seems to work!):

StartRecipe = 1
EndRecipe = 20

For r1 = StartRecipe To EndRecipe
 For r2 = StartRecipe To EndRecipe
  For r3 = StartRecipe To EndRecipe
   For r4 = StartRecipe To EndRecipe
    
    If Not (r1 >= r2 Or r2 >= r3 Or r3 >= r4) Then
   
        strSQL = "INSERT INTO MealPlanCosts  SELECT '" & r1 & "," & r2 & "," & r3 & "," & r4 & "' as MealPlan, sum(totalcost) as MealPlanCost from (SELECT ingredient, Nz([recipe " & r1 & "])+Nz([recipe " & r2 & "])+Nz([recipe " & r3 & "])+Nz([recipe " & r4 & "]) AS qty, Switch([qty]<[b1],1,[qty]<[b2],2,[qty]<[b3],3,[qty]<[b4],4,[qty]<[b5],5) AS bucket, Switch([qty]<[b1],[p1],[qty]<[b2],[p2],[qty]<[b3],[p3],[qty]<[b4],[p4],[qty]<[b5],[p5]) AS price, [qty]*[price] AS totalcost FROM ingredients)"
        DoCmd.RunSQL strSQL
    End If
    
   Next r4
  Next r3
 Next r2
Next r1

Open in new window

Top Expert 2014

Commented:
selecting the bucket 5 cost only doesn't seem to make any sense
Column 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.

Author

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

I agree we need the ingredient quantities. For the purpose of this exercise, as stated earlier, we can assume the number of instances of each meal plan to be produced is a fixed quantity, let's say 1, in which case the quantities are exactly as provided in the recipe columns.

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.

Does this make sense?
xenium:  I'm sorry but: no, it doesn't make sense.  It doesn't make sense because you asked for an optimization approach.  The relationship between total cost of a selected plan *is not* a linear relationship (i.e. not scalar) with respect to quantity.  And that is because there are price breaks that you provided.  If it were not for the price breaks then this would work.  But there are quantity price breaks involved *by definition*... your definition.

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.

Author

Commented:
I understand that the optimum solution (output) is not linear in relation to the input quantity. But the input quantity does not affect the approach taken so I am not interested in how many meal instances we solve for. So I am suggesting we solve for 1 instance to demonstrate the process.

Maybe there is a misunderstanding on how the buckets work, so let's run through an example to check this. To calculate the cost of a meal plan consisting of recipes 1-4:

Cost of ingredient 1:
recipe 1 requires 45 units
recipe 2 requires 0 units
recipe 3 requires 2 units
recipe 4 requires 0 units
Total 47 units of ingredient 1, this quantity falls into bucket 4 giving a price of 11.39 per unit
Total cost for ingredient 1 is 47 * 11.39 = 535.33

etc for each ingredient.

I am not interested in looking at shelf life etc at this point, just in solving the mathematical problem.

I have solved the problem exhaustively for recipes 1-20 only, which takes several seconds using the MS access routine above, and extrapolated that I can do the same for recipes 1-100 in several hours.

I could reduce this time with a better programming language or hardware, but at this stage I want to reduce the time by using a better method. Ultimately i want to know if the processing time can be reduced to a split second by using a heuristic approach that gives a pretty good answer (eg 95% chance of being within 3% of optimal) That's a dramatic change from several hours that I have now, so the "brute force" method can only be for checking results.
You said:
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?
So the emphasis has been on that 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 point
So I was just confirming that the shelf life aspect was NOT of concern right now even though the aspect was brought into the conversation.

Author

Commented:
Fred,

The topic of shelf life etc was raised by aikimark, I am not interested in this.

I would like an optimal solution, but a "pretty good" one may do. I don't see this as a different objective, rather a compromise if an optimal solution is not forthcoming or practical.

In the question I asked:

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

Yes I can solve it with brute force -  I agree that is not an unknown - but I used the word "efficiently" as I suspect there is a better way to do it than brute force.

Author

Commented:
I suggest leaving this question to sit for a while. I suspect that the problem maybe harder than we have all imagined, so some stewing time may be good.

Thanks all for your contributions so far.
When I wrote earlier:
>> 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.

Author

Commented:
Implementation would be using a much more efficient language.

VBA, SQL etc is just to test the logic.

The final implementation probably needs to complete such tasks within a fraction of a second, so I need to see what is the most efficient logical way to solve the problem. Hence the assigned groups are mathematics & algorithms, and not any programming language.
I modified the approach to include the break-even points for ingredient purchase.
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

Author

Commented:
Thanks a lot. It looks good, but it's blown my head, so I will probably close that as the answer once i have had a chance to digest it better.

Good point on the breakeven points, makes sense.

Incidentally, when i run my script on recipes  5, 11, 53, 80 i get meal plan cost of $30626.56 but i may have missed something obvious.
You can look at the formulas that I entered.  I didn't deal with the quantity issue that I'd raised earlier as this is supposed to be a demo of sorts.
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 will probably close that as the answer

Author

Commented:
hi Fred thanks a lot. I've just been through that now, i think there were a couple of bugs in your spreadsheet:
1. the weight was used instead of the unit price,
2. the quantity purchased should sometimes be the breakeven quantity if that is cheaper

I have corrected this in the attached, and also moved the input formulae. The solver sheets i've formatted in strike-through for now - would you mind giving it a quick check see if it looks right?

Thanks again
Meal-Plan-Selection-v2.xlsx
I guess I don't understand your formulation regarding weights, quantities and prices.  So, if it's correct now then good!

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.

Author

Commented:
Thanks Fred

There's a lot in this question so to tidy up I'll close this now and link to any side questions that may come out from it.

Thanks all for your contributions and patience.

Author

Commented:
fyi i'll post a few notes on the xls for the record shortly..

Author

Commented:
Hope this makes sense:

Cells: U3:X3
The 4 selected recipes in a meal plan.

Cols U:X
the quantities (in kg) of each ingredient needed for each recipe

Y: qty needed
total quantity (in kg) of ingredient needed to produce all 4 meals in the plan

Z: bucket
the bucket number (from cell B2:F2) relating to qty needed (column Y)

AA: unit price
lookup price from cols I:M, based on bucket (column Z)

Now considering breakeven quantities (as raised by Fred)
A breakeven quantity is a quantity above which it is cheaper to purchase at the next price break point by purchasing excess stock.

AC: b/e bucket
lookup breakeven bucket number from columns O:S, based on qty needed (column Y)

AD: b/e qty
lookup breakeven quantity (kg) from columns O:S (index on bucket number in column AC)

AE: bucket qty
the price break quantity relating to the break-even bucket number (column AC)
ie. the quantity needed to get the next price break

if the quantity needed (column Y) is above the breakeven quantity (column AD) then purchase the price break quantity (column AE), otherwise purchase the exact quantity needed (column Y)

AG: unit price
the price from columns I:M relating to the breakeven bucket (column AC)

Cell AG2: total cost of meal plan
sumproduct purchase quantity (column AF) and unit price (column AG)

Author

Commented:
AF: buy qty
if the quantity needed (column Y) is above the breakeven quantity (column AD) then purchase the price break quantity (column AE), otherwise purchase the exact quantity needed (column Y)

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial