需要一种算法方法来计算膳食计划

Question

我在解决一个看似简单的问题时遇到了麻烦.我的女朋友和我正在努力制定每周的膳食计划,我有这个绝妙的想法,我可以优化我们购买的东西,以便最大化我们可以用它做的事情.问题是,问题并不像看起来那么容易.简而言之,这是问题陈述:

问题:给出100种成分的清单以及由100种成分中的一种或多种组成的50种菜肴的清单,找到可以产生最大数量的菜肴的32种成分的列表.

这个问题看似简单,但我发现计算答案并非易事.我采用的方法是,我计算了32种成分的组合,作为100位字符串,其中32位设置.然后我检查一下这些配料编号可以制作什么菜.如果菜肴数量大于当前最大值,我将保存清单.然后我计算下一个有效成分组合并重复,重复和重复.

32种成分的组合数量惊人!我看到它的方式,用我的方法计算需要大约300万亿年.我已经优化了代码,因此每个组合只花了75微秒才能搞清楚.假设我可以优化代码,我可以将运行时间缩短到仅仅几万亿年.

我认为一种全新的方法是有序的.我目前正在XOJO(REALbasic)中对此进行编码,但我认为真正的问题在于方法而不是具体实现.有人想知道本世纪有可能完成的方法吗？

谢谢,

罗恩

Answer 1

mcdowella的分支和绑定解决方案将比详尽的枚举有很大的改进,但它可能仍需要几千年.这是ILP解算器最好解决的问题.

假设用餐i的成分组由R [i] = {R [i] [1],R [i] [2],...,R [i] [| R [i] |]给出.你可以按如下方式编码问题:

• 为每个成分创建一个整数变量x [i] 1 <= i <= 100.这些变量中的每一个都应该被约束到范围[0,1].
• 为每餐1 <= i <= 50创建一个整数变量y [i].这些变量中的每一个都应该被约束到范围[0,1].
• 对于每餐i,创建| R [i] | 对于1 <= j <= | R [i] |,形式y [i] <= x [R [i] [j]]的附加约束.这些将保证我们只能将y [i]设置为1,如果包含了所有的膳食成分.
• 添加一个约束,即所有x [i]的总和必须<= 32.
• 最后,目标函数应该是所有y [i]的总和,我们应该尝试最大化这个.

解决这个问题将产生所有变量的赋值x [i]:1表示应该包含成分,0表示不应该包含.

我的感觉是像CPLEX或Gurobi这样的商业ILP求解器可能会在几毫秒内解决这个150变量的ILP问题.像甚至免费提供的求解器lp_solve,这通常是多慢,应该没有问题.在不太可能的情况下,它似乎永远需要,你仍然可以解决LP放松,这将非常快(毫秒),并将给你(a)可以准备的最大膳食数量的上限( b)变量值中的"提示":虽然x [i]通常不会精确地为0或1,但是接近1的值表示应包括的成分,而接近0的值表示无用的成分.