集合覆寫問題在供應鏈管理中扮演著重要的角色，例如如何選擇最少的供應商以滿足所有零件需求。利用數學模型，我們可以將此問題轉化為最小化選中供應商數量的目標函式，並透過約束條件確保每個零件至少被一個供應商覆寫。Python 的 OR-Tools 函式庫提供瞭解決此類別問題的有效工具，可以快速計算出最優的供應商組合。集合包裝問題則關注如何在滿足特定限制條件下最大化選中的子集數量，例如在航空公司排班問題中，如何最大化被排班的工作人員數量，同時避免人員衝突。同樣地，OR-Tools 也能有效處理這類別問題。最後，容器裝載問題旨在最小化所需的容器數量，同時滿足容量限制。在建立數學模型時，需要仔細定義決策變數、約束條件和目標函式，並考慮使用對稱破壞限制等技巧來提升求解效率。
集合覆寫問題的數學模型與實作
問題描述
在實際的供應鏈管理中，企業經常面臨如何選擇最優供應商的問題，以滿足所有零件需求同時最小化成本。這類別問題在數學上被建模為集合覆寫問題（Set Cover Problem），其目標是從一組供應商中選取最小數量的供應商，使得每個零件至少被一個選中的供應商所提供。
數學模型
集合覆寫問題的數學模型可以表示如下：
假設有 $n$ 個供應商和 $m$ 個零件，每個供應商 $i$ 提供一個零件集合 $P_i$。我們的目標是選擇最小數量的供應商，使得每個零件 $j$ 至少被一個選中的供應商所提供。
數學上，這可以表示為：
$$\min \sum_{i=1}^{n} S_i$$
受限於：
$$\sum_{i: j \in P_i} S_i \geq 1, \forall j$$
其中，$S_i$ 是一個二元變數，如果供應商 $i$ 被選中，則 $S_i = 1$，否則 $S_i = 0$。
可執行模型
下面是使用 Python 和 OR-Tools 函式庫實作的集合覆寫問題模型：
def solve_model(D, C=None):
t = 'SetCover'
s = pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING
s = pywraplp.Solver(t, s)
nbSup = len(D)
nbParts = max([e for d in D for e in d]) + 1
S = [s.IntVar(0, 1, '') for i in range(nbSup)]
for j in range(nbParts):
s.Add(1 <= sum(S[i] for i in range(nbSup) if j in D[i]))
s.Minimize(s.Sum(S[i] * (1 if C is None else C[i]) for i in range(nbSup)))
rc = s.Solve()
Suppliers = [i for i in range(nbSup) if SolVal(S[i]) > 0]
Parts = [[i for i in range(nbSup) if j in D[i] and SolVal(S[i]) > 0] for j in range(nbParts)]
return rc, ObjVal(s), Suppliers, Parts
內容解密：
S = [s.IntVar(0, 1, '') for i in range(nbSup)]：定義二元變數 $S_i$，表示供應商 $i$ 是否被選中。s.Add(1 <= sum(S[i] for i in range(nbSup) if j in D[i]))：實作集合覆寫的限制條件，確保每個零件至少被一個選中的供應商提供。s.Minimize(s.Sum(S[i] * (1 if C is None else C[i]) for i in range(nbSup)))：定義目標函式，如果沒有提供成本陣列C，則最小化選中的供應商數量；否則，最小化選中的供應商的總成本。
應使用案例項
假設我們有一組供應商和零件的資料，如下表所示：
| 供應商 | 提供的零件 |
|---|---|
| 0 | {0, 2, 5} |
| 1 | {1, 3} |
| 2 | {2, 4} |
透過執行上述模型，我們可以得到最優的供應商選擇方案。
變化與擴充套件
集合覆寫問題在許多領域有廣泛的應用，如航空公司的機組排班問題。除了基本的集合覆寫問題外，還可以根據實際需求進行變化和擴充套件，例如考慮不同供應商的成本、服務品質等因素。
集合覆寫與集合包裝問題的建模與應用
在離散最佳化領域中，集合覆寫（Set Cover）與集合包裝（Set Packing）是兩個重要的問題，它們在許多實際應用中扮演著關鍵角色，例如資源分配、排班和物流管理等。
集合覆寫問題
集合覆寫問題旨在從一組子集合中選取最少數量的子集，使得這些子集的聯集能夠覆寫整個全集。例如，在電腦病毒檢測中，我們希望從大量的病毒特徵中找出最少數量的特徵，以便檢測出所有的病毒。在這個問題中，我們需要決策哪些特徵應該被選取。
模型建立
- 決策變數：使用0-1變數來表示是否選擇某個子集。
- 目標函式：最小化所選擇的子集數量。
- 限制條件：確保每個元素至少被一個所選擇的子集包含。
集合包裝問題
集合包裝問題與集合覆寫問題相反，它旨在從一組子集合中選取盡可能多的子集，使得這些子集之間不重複。例如，在航空公司的工作人員排班問題中，我們希望最大化能夠被排班的工作人員數量，同時確保每個人不會被安排到多個航班上。
例項說明
考慮一個簡單的航空公司排班例子，每個航班需要一名飛行員、一名副飛行員、一名導航員和一名乘務長。我們可以將每個可能的排班組合視為一個子集，目標是最大化能夠被選取的排班數量。
模型建立
- 決策變數：使用0-1變數來表示是否選擇某個排班。
- 目標函式：最大化所選擇的排班數量。
- 限制條件：對於每個工作人員，包含該工作人員的排班數量不能超過1。
程式碼實作
以下是一個使用Python實作的集合包裝問題模型範例：
def solve_model(D, C=None):
s = newSolver('SetPacking', True)
nbRosters, nbCrew = len(D), max([e for d in D for e in d]) + 1
S = [s.IntVar(0, 1, "") for i in range(nbRosters)]
for j in range(nbCrew):
s.Add(1 >= sum(S[i] for i in range(nbRosters) if j in D[i]))
s.Maximize(s.Sum(S[i] * (1 if C == None else C[i]) for i in range(nbRosters)))
rc = s.Solve()
Rosters = [i for i in range(nbRosters) if S[i].SolutionValue() > 0]
return rc, s.Objective().Value(), Rosters
內容解密：
newSolver函式：用於建立一個新的求解器例項。nbRosters和nbCrew變數：分別代表排班數量和工作人員數量。S列表：包含用於表示是否選擇某個排班的0-1變數。- 限制條件：確保每個工作人員最多被安排到一個排班中。
- 目標函式：最大化所選擇的排班數量，可以根據需要加入成本考量。
Bin Packing 問題
Bin Packing 問題是一種將物品分配到有限容量的箱子中的問題，目標是最小化所使用的箱子數量。這個問題在物流和運輸領域有著廣泛的應用。
例項說明
例如，一家物流公司需要將不同重量的包裹裝載到具有重量限制的卡車上，目標是最小化所需的卡車數量。
容器裝載最佳化模型建構
在探討容器裝載（Bin Packing）問題時，我們需要建立一個數學模型來最佳化貨物的分配。這個問題的核心是如何將不同重量的包裹分配到最少數量的貨車中，同時確保每輛貨車的載重量不超過其容量。
決策變數的定義
首先，我們需要定義決策變數來描述包裹與貨車之間的分配關係。假設有 $P$ 個包裹和最多 $T$ 輛貨車，我們定義二元變數 $x_{i,j}$，其中 $x_{i,j} = 1$ 表示第 $i$ 個包裹被裝入第 $j$ 輛貨車。另一個重要的變數是 $y_j$，用於表示第 $j$ 輛貨車是否被使用。
# 變數定義
x = [[[s.IntVar(0,1,"") for _ in range(nbT)] for _ in range(d[0])] for d in D]
y = [s.IntVar(0,1,"") for _ in range(nbT)]
內容解密：
這段程式碼定義了兩個重要的決策變數：x 和 y。x 是一個三維陣列，用於表示每個包裹是否被分配到特定的貨車中；y 則是一個一維陣列，用於表示每輛貨車是否被使用。這些變數的值將由求解器根據目標函式和限制條件進行最佳化。
約束條件的建立
貨車使用與包裹分配的關聯：如果任何包裹被分配到某一輛貨車，則該貨車必須被使用。這個關係可以透過以下約束來表達： $$\sum_{i=1}^{P} w_i x_{i,j} \leq W_j y_j, \forall j$$
# 約束條件：貨車容量限制 for k in range(nbT): sxk = sum(D[i][1]*x[i][j][k] for i in range(nbC) for j in range(D[i][0])) s.Add(sxk <= W*y[k])內容解密：
這段程式碼確保瞭如果任何包裹被裝入某一輛貨車（$x_{i,j} = 1$），則該貨車必須被使用（$y_j = 1$）。同時，它也保證了裝入該貨車的所有包裹總重量不超過該貨車的容量 $W$。
每個包裹必須被裝入恰好一輛貨車： $$\sum_{j=1}^{T} x_{i,j} = 1, \forall i$$
# 約束條件：每個包裹恰好被裝入一輛貨車 for i in range(nbC): for j in range(D[i][0]): s.Add(sum([x[i][j][k] for k in range(nbT)]) == 1)內容解密：
這段程式碼確保每個包裹都被分配到恰好一輛貨車中，滿足問題的基本需求。
目標函式
我們的目標是最小化使用的貨車數量，因此目標函式可以表示為： $$\min \sum_{j=1}^{T} y_j$$
# 目標函式：最小化使用的貨車數量
s.Minimize(sum(y[k] for k in range(nbT)))
內容解密：
這段程式碼定義了模型的目標函式，即最小化被使用的貨車數量。這是容器裝載問題中的一個關鍵最佳化目標。
可執行模型的建立
完整的模型建構和求解過程在 solve_model 函式中實作，該函式接收包裹的重量分佈、貨車的容量等引數，並傳回求解結果。
# 求解模型
def solve_model(D, W, symmetry_break=False, knapsack=True):
# ...（模型建構細節）
rc = s.Solve()
# ...（結果處理）
return rc, ObjVal(s), P2T, T2P
內容解密：
這段程式碼呼叫求解器對建立的模型進行求解，並傳回求解狀態、目標函式值以及包裹到貨車的分配結果。透過這個函式，我們可以獲得最佳化的容器裝載方案。
限制規劃模型中的對稱破壞：以貨物裝載問題為例
在處理複雜的離散最佳化問題時，例如貨物裝載（Bin Packing）問題，限制規劃（Constraint Programming）提供了一種有效的建模與求解方法。然而，這類別問題往往存在眾多具有相同目標函式值的解，這種現象被稱為對稱性（Symmetry）。對稱性會嚴重影響求解器的效率，因為它會導致求解器在眾多等價的解之間進行無謂的搜尋。
貨物裝載問題的建模
貨物裝載問題旨在將一組不同重量的貨物分配到多個容量相同的車輛中，以最小化所需的車輛數量。我們的模型使用了兩個主要的決策變數：一個三維陣列 x 用於表示貨物是否被裝載到某個車輛上，以及一個一維陣列 y 用於表示某個車輛是否被選中。
# 決策變數定義
x = [[[model.NewBoolVar(f'x[{w}][{p}][{t}]') for t in range(T)] for p in range(P[w])] for w in range(W)]
y = [model.NewBoolVar(f'y[{t}]') for t in range(T)]
內容解密：
x是一個三維布林變數陣列，x[w][p][t]表示第w個重量等級中的第p個包裹是否被裝載到第t個車輛上。y是一維布林變數陣列，y[t]表示第t個車輛是否被選中用於裝載貨物。
對稱破壞
對稱性主要體現在兩個方面：車輛選擇的隨機性和貨物分配的隨機性。為了消除這些對稱性，我們引入了額外的限制條件。
車輛選擇的對稱破壞
為了確保車輛按照順序被選中，我們引入了以下限制：
for t in range(1, T):
model.Add(y[t-1] >= y[t])
內容解密：
- 這段程式碼強制要求，如果第
t個車輛被選中，那麼第t-1個車輛也必須被選中，從而避免了車輛選擇的隨機性。
貨物分配的對稱破壞
對於同一重量等級的貨物，我們希望它們按照一定的順序被裝載到車輛上，以避免貨物分配的隨機性。例如，如果第一個貨物被裝載到第 t 個車輛上，那麼第二個貨物應該被裝載到第 t 或後續的車輛上。
for w in range(W):
for p in range(P[w] - 1):
for t in range(T):
model.Add(x[w][p][t] <= sum(x[w][p+1][t2] for t2 in range(t, T)))
內容解密：
- 這段程式碼確保，如果第
w個重量等級中的第p個貨物被裝載到第t個車輛上，那麼第p+1個貨物必須被裝載到第t或後續的車輛上，從而維持了貨物分配的順序性。
此圖示
@startuml
skinparam backgroundColor #FEFEFE
skinparam componentStyle rectangle
title 集合覆寫與裝載問題模型最佳化
package "集合覆蓋與裝載最佳化" {
package "集合覆蓋問題" {
component [供應商選擇] as supplier
component [零件覆蓋] as parts
component [成本最小化] as cost
}
package "集合包裝問題" {
component [航班排班] as crew
component [衝突避免] as conflict
component [人員最大化] as maximize
}
package "Bin Packing" {
component [容器裝載] as bin
component [對稱破壞] as symmetry
component [OR-Tools] as ortools
}
}
collect --> clean : 原始資料
clean --> feature : 乾淨資料
feature --> select : 特徵向量
select --> tune : 基礎模型
tune --> cv : 最佳參數
cv --> eval : 訓練模型
eval --> deploy : 驗證模型
deploy --> monitor : 生產模型
note right of feature
特徵工程包含：
- 特徵選擇
- 特徵轉換
- 降維處理
end note
note right of eval
評估指標：
- 準確率/召回率
- F1 Score
- AUC-ROC
end note
@enduml內容解密：
- 此圖示展示了貨物裝載問題如何透過限制規劃模型進行建模，並透過對稱破壞技術提高求解效率。對稱破壞分為車輛選擇和貨物分配兩個方面，均有助於減少搜尋空間，提升求解效能。
5.3.1.4 對稱破壞限制與啟發式方法
在前述的模型中，我們建立了一個基本的整數規劃模型來解決貨包裝載問題（Bin Packing Problem）。然而，這類別問題往往存在對稱性，這會導致求解效率降低。對稱破壞限制（Symmetry-Breaking Constraints）的引入可以有效減少搜尋空間，從而提升求解效率。
對稱破壞限制的作用
對稱破壞限制的主要目的是消除模型中的對稱性。在貨包裝載問題中，對稱性體現在多個貨車（Trucks）具有相同的容量，從而導致多種等價的裝載方案。透過引入對稱破壞限制，我們可以確保貨包按照一定的順序裝載到貨車上，避免重複的裝載方案。
具體來說，我們引入了以下兩類別對稱破壞限制：
若一個貨包被裝載到某個貨車上，則序號更大的貨包必須被裝載到序號更大或相等的貨車上。
這些限制確保了貨包的裝載順序與貨車的序號保持一致，避免了不必要的搜尋空間。
若貨包 (i) 被裝載到貨車 (k) 上，則序號更小的貨包必須被裝載到序號更小或相等的貨車上。
這些限制雖然在某些情況下是冗餘的，但在特定的求解器（Solver）中仍然可以提升求解效率。
正確實施對稱破壞限制
在實施對稱破壞限制時，需要小心避免過度約束模型。例如，對於約束 (x_{0,1} = 1 \Rightarrow x_{1,1} + x_{1,2} = 1)，如果我們錯誤地使用等式約束 (x_{1,1} + x_{1,2} = x_{0,1})，則當 (x_{0,1} = 0) 時，會錯誤地限制 (x_{1,1} + x_{1,2} = 0)，從而排除掉可行的裝載方案。正確的做法是使用不等式約束 (x_{1,1} + x_{1,2} \geq x_{0,1})，這樣當 (x_{0,1} = 0) 時，不會對 (x_{1,1}) 和 (x_{1,2}) 施加不必要的限制。
# 正確的對稱破壞限制範例
def symmetry_breaking_constraints(model, x, num_packages, num_trucks):
for i in range(num_packages - 1):
for k in range(num_trucks):
# 若貨包 i 被裝載到貨車 k 上，則序號更大的貨包必須被裝載到序號更大或相等的貨車上
model.add_constraint(x[i + 1, k] <= sum(x[i, j] for j in range(k + 1)))
內容解密：
此段程式碼展示瞭如何正確實施對稱破壞限制。我們遍歷每個貨包和每個貨車，確保當前貨包若被裝載到某個貨車上，則下一個貨包只能被裝載到該貨車或之後的貨車上。這樣的限制有效地減少了模型的對稱性。
啟發式方法
為了進一步提升求解效率，我們可以使用啟發式方法來界定所需的貨車數量。一個簡單的貪婪演算法可以實作這一點：不斷將貨包新增到第一輛貨車，直到達到容量限制，然後再新增到下一輛貨車。這種方法雖然不總能得到最優解，但可以提供一個合理的上限。
# 簡單的貪婪演算法來界定所需的貨車數量
def bound_trucks(weights, capacity):
num_trucks = 1
total_weight = 0
for weight in weights:
if total_weight + weight <= capacity:
total_weight += weight
else:
total_weight = weight
num_trucks += 1
lower_bound = math.ceil(sum(weights) / capacity)
return num_trucks, lower_bound
內容解密：
此函式首先初始化所需的貨車數量和當前貨車的總重量。然後，它遍歷每個貨包的重量，若當前貨車的總重量加上該貨包的重量不超過容量，則將該貨包新增到當前貨車；否則，將該貨包新增到下一輛新的貨車，並更新總重量和所需的貨車數量。最後，計算所需的最低貨車數量下限，即所有貨包總重量除以單個貨車的容量。
變體問題
貨包裝載問題有多種變體，包括：
- 不同容量限制的貨車：需要調整容量約束和對稱破壞限制，以適應不同容量的貨車。
- 固定數量貨車下的最大化價值裝載：目標是最大化被裝載的貨包總價值。
- 單一貨車的0/1揹包問題：簡化版的裝載問題，只有一個貨車，需要最大化被裝載的貨包總價值。
- 資本預算問題：將多個專案分配給有限的預算，目標是最大化專案的總價值。
這些變體問題在實際應用中具有重要意義，並可以使用類別似的方法進行建模和求解。
