建模組合優化？問題

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 *普通+烤麪包，具體取決於相對成本）包裝好，然後繼續這種方式就足夠了。