列生成演算法（求解Cutting Stock問題）

列生成是用於求解大規模線性優化問題的一種演算法，其實就是單純形法的一種形式。單純性可以通過不斷迭代，通過換基變數的操作，最終找到問題的最優解。但是當問題的規模很大之後，變數的個數就會增大到在有限時間內無法有效迭代求解。所以可以用列生成方法求解，列生成方法可以一開始不列舉所有的列，通過不斷給模型中加入列的方式，最終找到全部解，其關鍵點就是加新列的過程，可以只加入能讓目標值更優的列，從而減少變數的使用個數。

列生成演算法流程

列生成過程中，需要將問題建模為主問題+子問題的形式。
主問題：就是原問題，主要用於決策是否選用某些方案（列）
主問題鬆弛問題：將主問題變數範圍正整數鬆弛到正數
限制主問題：主問題去掉一部分列
限制主問題對偶問題：對限制主問題求對偶
價格子問題：原問題的局部問題，用於生成新的方案（列）

求解Cutting Stock問題

問題描述：

將一些鋼管切割成為需要的長度以滿足客戶需求，要求使用的鋼管最少。
每根鋼管長度L=16m
需求：3m鋼管25根；6m鋼管20根，7米鋼管18根

模型建立

主問題

\[min\sum_{j \in J} x_{j}\\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\sum_{j \in J} x_j a_{ij} \ge d_i \qquad \forall i \in I\\
x_j \in Z \qquad \qquad \quad \forall j \in J \]

\(x_j\): 方案選用的個數
\(a_{ij}\): 方案\(j\)中鋼管\(i\)的個數
\(d_i\): 鋼管\(i\)的需求量

主問題鬆弛問題

\[min\sum_{j \in J} x_{j}\\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\sum_{j \in J} x_j a_{ij} \ge d_i \qquad \forall i \in I\\
x_j \ge 0 \qquad \qquad \quad \forall j \in J \]

變數是整數的情況下無法用列生成法求得最優解，需要將問題鬆弛。如果需要求得整數最優解需要結合分支定界演算法。

限制主問題

\[min\sum_{j \in J} x_{j}\\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\sum_{j \in J} x_j a_{ij} \ge d_i \qquad \forall i \in I\\
x_j \ge 0 \qquad \qquad \quad \forall j \in \Omega_j \]

將主問題中的變數規模減小，一開始只加入一部分可行的切割方案（\(a_j\)，列），列生成就是不斷生成新的\(a_j\) 加入到問題中。判斷一個列是否可以加入到問題，需要判斷檢驗數\(\sigma_j = c_j – c_B B^{-1}a_j\),如果檢驗數為負，就可以將新的列加入。其中\(c_BB^{-1}\)有兩重含義：

  • 通過限制主問題求得的影子價格
  • 通過限制主問題求得的對偶變數

對偶問題和原問題有同樣的最優解，將原問題進行對偶，可以把原問題的變數轉化為約束、約束轉化為變數，因此，對於變數很多的問題將其轉化為對偶問題可以很容易得到其子問題。

對偶問題

\[max \sum_{i \in I} d_i v_i \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\sum_{i in \ I} a_{ij} v_i \le 1 \qquad \qquad \forall j \in \Omega_j \\
v_j \ge 0 \qquad \qquad \qquad \quad
\forall i \in I \]

對偶問題用於推導子問題。可以進入主問題的列，就是檢驗數為負數的列，對於對偶問題，就是違反了約束的列。對偶問題中只有一個約束，\(\sum_{i in \ I} a_{ij} \lambda_i \le 1\)可以寫成\(1-\sum_{i \in I} a_i \lambda_i \ge 0\)，求其最小值，如果最小值小於0，則說明其違反了約束。子問題用於生成新的切割方案(列)，子問題的約束對應切割約束。

子問題

\[min \quad 1-\sum_{i \in I} a_i v_i \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\sum_{i \in I} a_i l_i \le L \qquad \forall i \in I \\
a_i \ge 0 \qquad \quad \quad \forall i \in I \]

數據帶入模型

以下所有的求解都可以用CPLEX進行求解，直接用CPLEX IDE實現

1. 啟發式獲得初始切割方案

首先有可行的切割方案才能構造出主問題，因此可以用啟發式先計算出一些可行的切割方案，用於構造主問題。很簡單的，每根鋼管只生產一種產品，可以得到三種切割方案

切割方案 3m 6m 7m
1 5 0 0
2 0 2 0
3 0 0 2

2.開始列生成迭代

第1次迭代

鬆弛限制主問題：

\[min \quad x_1 + x_2 + x_3 \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\quad\quad\quad5x_1 \qquad \qquad \quad \ge 25 \\
\quad\quad\quad\qquad 2x_2 \qquad \quad \ge 20 \\
\quad\quad\quad\qquad \qquad 2x_3 \quad\ge 18 \\
\quad\quad\quad x_1,\quad x_2,\quad x_3 \quad \ge 0 \]

對偶問題：

\[max \quad 25 v_1 + 20 v_2 + 18v_3 \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\qquad \quad 5v_1 \qquad \qquad \qquad \quad\le 1 \\
\qquad \quad\qquad \quad 2v_2 \qquad \quad \quad\le 1 \\
\qquad \quad\qquad \qquad \qquad 2v_3\quad \le 1 \\
\quad\quad \quad v_1,\quad \quad v_2,\quad \quad v_3 \quad \ge 0 \]



求得對偶變數的值，將其帶入到子問題中

子問題：

\[min \quad 1-0.2a_1-0.5a_2-0.5a_3 \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\quad\quad\quad 3a_1+6a_2+7a_3 \le 16\\
\quad\quad\quad a_1, \quad a_2, \quad a_3 \quad \ge 0 \]



目標函數值為-0.2<0，可以加入到主問題中繼續求解，新加入的一列是\(a_4=[1,2,0]^T\)，表示這個方案中一根鋼管切出一根3m和2根6米

第2次迭代

鬆弛限制主問題：

\[min \quad x_1 + x_2 + x_3 + x_4 \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\quad\quad\quad5x_1 \qquad \qquad \quad + x_4 \quad\ge 25 \\
\quad\quad\quad\qquad 2x_2 \qquad \quad + 2x_4 \ge 20 \\
\quad\quad\quad\qquad \qquad 2x_3 \quad \quad\quad\quad\ge 18 \\
\quad\quad\quad x_1,\quad x_2,\quad x_3, \quad x_4 \quad \ge 0 \]

對偶問題：

\[max \quad 25 v_1 + 20 v_2 + 18v_3 \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\qquad \quad 5v_1 \qquad \qquad \qquad \quad\le 1 \\
\qquad \quad\qquad \quad 2v_2 \qquad \quad \quad\le 1 \\
\qquad \quad\qquad \qquad \qquad 2v_3\quad \le 1 \\
\qquad \quad v_1\quad+2v_2 \quad\quad\quad\quad\le 1 \\
\quad\quad \quad v_1, \qquad v_2, \qquad v_3 \quad \ge 0 \]



求得對偶變數的值，將其帶入到子問題中

子問題：

\[min \quad 1-0.2a_1-0.4a_2-0.5a_3 \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\quad\quad\quad 3a_1+6a_2+7a_3 \le 16\\
\quad\quad\quad a_1, \quad a_2, \quad a_3 \quad \ge 0 \]



目標函數值為-0.1<0，可以加入到主問題中繼續求解，可以加入到主問題中繼續求解，新加入的一列是\(a_4=[1,1,1]^T\)，表示這個方案中一根鋼管切出1根3m，1根6米，1根7米

第3次迭代

鬆弛限制主問題：

\[min \quad x_1 + x_2 + x_3 + x_4 + x_5\\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\quad\quad\quad5x_1 \qquad \qquad \quad + x_4 \quad + x_5\ge 25 \\
\quad\quad\quad\qquad 2x_2 \qquad \quad + 2x_4 +x_5\ge 20 \\
\quad\quad\quad\qquad \qquad 2x_3 \quad \quad\quad\quad +x_5\ge 18 \\
\quad\quad x_1,\quad x_2,\quad x_3, \quad x_4, \quad x_5 \quad\quad\ge 0 \]

對偶問題：

\[max \quad 25 v_1 + 20 v_2 + 18v_3 \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\qquad \quad 5v_1 \qquad \qquad \qquad \quad\le 1 \\
\qquad \quad\qquad \quad 2v_2 \qquad \quad \quad\le 1 \\
\qquad \quad\qquad \qquad \qquad 2v_3\quad \le 1 \\
\qquad \quad v_1\quad+2v_2 \quad\quad\quad\quad\le 1 \\
\qquad \quad v_1\quad+v_2\quad+v_3 \quad\le 1 \\
\quad\quad \quad v_1, \qquad v_2, \qquad v_3 \quad \ge 0 \]



求得對偶變數的值，將其帶入到子問題中

子問題:

\[min \quad 1-0.2a_1-0.4a_2-0.4a_3 \\
s.t.\qquad\qquad\qquad\qquad\qquad\\
\quad\quad\quad 3a_1+6a_2+7a_3 \le 16\\
\quad\quad\quad a_1, \quad a_2, \quad a_3 \quad \ge 0 \]



根據求解可以得到
目標值：20.2
切割方案：方案1選擇1.2個；方案4選擇1個，方案5選擇18個

最後求得的結果包含了小數，如果想要取得整數解，需要結合分支定界演算法

Tags:

VirMach 便宜 VPS

QNews

QNews