IP Problems
1.knapsack problem/背包問題
- 特色:基礎題,選擇要不要把東西放進背包(只有0or1可選)
2.knapsack problem/背包問題-續
- 特色:簡易條件式,可透過些微判斷得到條件式
3.fixed-charge problem/存在才需支付問題
- 特色:如何讓你的存在影響到我會存在
ex:要做某商品才需要付機器租用費,反之則不租則不用付
4.set-covering problem/覆蓋範圍問題
- 特色:依照距離,能在時限內的只需要有1即可達成條件
條件式 IP problems
1.either-or problem
★小提示:
難理解的話可以先思考這題,
想讀書或睡覺
★可能之一: 讀書 + “不睡”
★可能之二: 睡覺 + “不讀”
★特別注意:
either-or 並不是 or問題,一方成立另一方不可以成立
基本條件式:
f<=0 or g<=0 (這邊其實這樣表示不是很好,應該只有一個能成立)
轉換成
f <= My
g <= M(1-y)
其中:
M為極大數
y等於0或1
y等於0時:
f<=0 f<=0的條件"單獨"發生
g<=M M極大 此式恆成立 (不重要的式子)
y等於1時:
f<=M M極大 此式恆成立 (不重要的式子)
g<=0 g<=0的條件"單獨"發生
2.if-then problem
基本條件式:
if f>0 then g>=0
轉換得
-g <= My
f <= M(1-y)
M為極大數
y等於0或1
等於0時:
-g<=0 -g<=0(等價於g>=0)的條件"單獨"發生 而前式f>0(自動成立)
f<=M M極大 此式恆成立 (不重要的式子)
等於1時:
-g<=M M極大 此式恆成立 (不重要的式子)
f<=0 f<=0的條件"單獨"發生 g因此不受限