建模组合优化？问题

Question

我一直无法将这个问题匹配到一些规范的问题，我想要一些指南来构建/使用算法并解决它。描述如下：

---

我们有一些人想要早餐。每个人都可以订购任意数量的咖啡，果汁和吐司。我们积累了所有组的订单。

InitialOrder = { C1, J1, T1 } with C1, J1, T1 being integer non-negative numbers.

每个组件都有一个给定的价格，因此初始顺序的总价格是

InitialPrice = C1 * Pc + J1 * Pj + T1 * Pt with Pc, Pj, Pt being rational positive numbers

咖啡馆也具有“早餐菜单”包括在标准项目组合

full breakfast = coffee + juice + toast 
normal breakfast = coffee + toast 
bread breakfast = 2 toast 

选择这些菜单比单独选择每个组件便宜，所以我们ve

Pf < Pc + Pj + Pt 
Pn < Pc + Pt 
Pb < 2 * Pt 
with Pf, Pn, Pb being rational positive numbers 

人们希望将初始订单分组到菜单中以最小化花费总额。然后

FinalOrder = { C2, J2, T2, F, N, B } with C2, J2, T2, F, N, B integer non-negative numbers

，我们将有一个FinalPrice < = InitialPrice作为

FinalPrice = C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb with Pc, Pj, Pt, Pf, Pn, Pb as rational positive numbers

所有价格（PC，PJ，PT，PF Pn和铅）是预先知道。

---

请问，你知道我应该遵循哪种方法来构建一个算法，以最小化给定的InitialOrder的FinalPrice？随时问任何你需要的更多细节。

预先感谢您。

Answer 1

这看起来像一个Linear Integer Programming问题。

给定线性约束条件（必须匹配初始顺序），您有六个变量和一个需要最小化的线性方程（用于最终价格）。限制是变量是非负的并且取整数值。

比如在你的榜样情况下这将是（我假设你的实际问题比:-)你的例子更复杂）

最小化

C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb 

（乘PC等具有适当的整让他们整数如果需要的话）

视乎约束

C2 + F + N = C1 
    T2 + F + N + 2B = T1 
    J2 + F = J1 

在一般情况下，整数规划是NP-Hard，但考虑到问题的小尺寸和约束条件，标准求解技术可能很快为您解决。

希望有所帮助。

Answer 2

如果你不想整个猪群（整数线性规划，这是一个相当复杂的区域），考虑一个穷尽树搜索使用分支定界。 BnB本质上是深度优先搜索，您可以在当前分支成本高于或等于迄今为止找到的最佳解决方案的任何位置回溯。

正如Moron说的那样，对于任何大问题，您都需要ILP。

Answer 3

由于您的问题与bin包装（或至少它的矢量版本）密切相关，因此一些相关的启发式技术也可能派上用场。特别是，贪婪的启发式方法首先要贪心地将全套早餐（或2 *普通+烤面包，具体取决于相对成本）包装好，然后继续这种方式就足够了。