optimization - Need an algorithm approach to calculate meal plan -

i’m having trouble solving deceptively simple problem. girlfriend , trying formulate weekly meal plans , had brilliant idea optimize buy in order maximize things make it. trouble is, problem not easy appears. here’s problem statement in nutshell:

the problem: given list of 100 ingredients , list of 50 dishes composed of 1 or more of 100 ingredients, find list of 32 ingredients can produce maximum number of dishes.

this problem seems simple, i’m finding computing answer not trivial. approach i’ve taken i’ve computed combination of 32 ingredients 100 bit string 32 of bits set. check of dishes can made ingredient number. if number of dishes greater current maximum, save off list. compute next valid ingredient combination , repeat, repeat, , repeat.

the number of combinations of 32 ingredients staggering! way see it, take 300 trillion years calculate using method. i’ve optimized code each combination takes mere 75 microseconds figure out. assuming can optimize code, might able reduce run time mere trillion years.

i’m thinking new approach in order. i'm coding in xojo (realbasic), think real problem approach rather specific implementation. have idea approach has chance of completion during century?

thanks,

ron

mcdowella's branch , bound solution big improvement on exhaustive enumeration, might still take few thousand years. kind of problem best solved ilp solver.

assuming set of ingredients meal given r[i] = { r[i][1], r[i][2], ..., r[i][|r[i]|] }, can encode problem follows:

• create integer variable x[i] each ingredient 1 <= <= 100. each of these variables should constrained range [0, 1].
• create integer variable y[i] each meal 1 <= <= 50. each of these variables should constrained range [0, 1].
• for each meal i, create |r[i]| additional constraints of form y[i] <= x[r[i][j]] 1 <= j <= |r[i]|. these guarantee can set y[i] 1 if of meal i's ingredients have been included.
• add constraint sum of x[i] must <= 32.
• finally, objective function should sum of y[i], , should trying maximise this.

solving produce assignments variables x[i]: 1 means ingredient should included, 0 means should not.

my feeling commercial ilp solver cplex or gurobi solve 150-variable ilp problem in milliseconds; freely available solvers lp_solve, rule much slower, should have no problems. in unlikely case seems taking forever, can still solve lp relaxation, fast (milliseconds) , give (a) upper bound on maximum number of meals can prepared , (b) "hints" in variable values: although x[i] in general not 0 or 1, values close 1 suggestive of ingredients should included, while values close 0 suggest unhelpful ingredients.