はじめに
大規模な線形計画問題を解く方法の1つに、列生成法(column generation method)が挙げられます。列生成法を解説した文献は、日本オペレーションズ・リサーチ学会機関誌57巻4号に掲載されているはじめての列生成法やしっかり学ぶ数理最適化の著者による資材切出し問題と列生成法等があります。
この列生成法、なんとなく有用そうということはわかるものの、理解するのが難しそうで避けておりました。しかし、分枝価格法を実装したい！と思った暁には避けて通れない手法ですし、いつまでも逃げ続けることはできません。そこで、列生成法の理論を学び、備忘録としてまとめました。初心者の解説ですので、わかりにくい部分や誤りのある部分などありましたら、コメント等で指摘していただけましたら幸いです。この記事が、誰かの支えとなれば幸いです。よろしくお願いします。
(復習)線形計画問題と双対問題への変換
はじめに、復習として線形計画問題から双対問題を求める方法をまとめます。変数が非負の最小化問題を対象に、制約式が等式の場合と不等式の場合に分けて考えます。なお、線形計画問題から双対問題を導く方法の整理には、線形計画問題のパターン別に、双対問題がどのような形になるかについて簡潔にまとめられています。
制約式が等式の場合
双対問題の求め方(左辺=右辺の場合)
以下の線形計画問題を考えます。なお、この問題を便宜的に(P)と呼びます。
\begin{align*}
\min \quad & \sum_{j = 1}^n c_j x_j & \\
\rm{s. \; t. } \quad & \sum_{j = 1}^n a_{ij} x_j = b_i, \quad & \forall i = 1, \dots, m \\
& x_j \geq 0, \quad & \forall j = 1, \dots, n
\end{align*}
いま、最も関心のある事は(P)の最適値を得ることなのですが、最適値を得ることが困難な問題も存在します。そのようなとき(P)の下界値Lが分かれば、(P)の最適値\rm{OPT} \left( (P) \right)との関係は、
\rm{OPT} \left( (P) \right) \geq L
ですので、最適値が取りうる範囲を狭めることができます。より大きな下界を得ることができれば、それだけ(P)の最適値が取りうる範囲をより狭めることができるので、最大の下界値を求めることを考えます。
各制約式に係数y_iを掛けて足し合わせると、
\sum_{i = 1}^m \left ( \sum_{j = 1}^n a_{ij} x_j \right ) y_i = \sum_{i = 1}^m b_i y_i
を得ることができます。この等式は、y_iに正負の制約を設けることなしに成り立つため、y_iは自由変数です。この式を整理すると、
\sum_{j = 1}^n \left ( \sum_{i = 1}^m a_{ij} y_i \right ) x_j = \sum_{i = 1}^m b_i y_i
を得ることができます。今、x_jは非負の変数ですので、任意のj = 1, \dots, mについて
c_j \geq \sum_{i = 1}^m a_{ij} y_i
が成り立てば、
\sum_{j = 1}^n c_j x_j \geq \sum_{j = 1}^n \left ( \sum_{i = 1}^m a_{ij} y_i \right ) x_j = \sum_{i = 1}^m b_i y_i
となって(P)の下界を得ることができます。まとめると、最大の下界を求める問題は、c_j \geq \sum_{i = 1}^m a_{ij} y_iが成り立つという条件のもとで、\sum_{i = 1}^m b_i y_iを最大化する問題です。この問題は、(P)に対する双対問題と呼ばれます。
\begin{align*}
\max \quad & \sum_{i = 1}^m b_i y_i & \\
\rm{s. \; t. } \quad & \sum_{i = 1}^m a_{ij} y_i \leq c_j, \quad & \forall j = 1, \dots, n
\end{align*}
制約式が不等式(左辺\leq右辺)の場合
双対問題の求め方(左辺<=右辺の場合)
\begin{align*}
\min \quad & \sum_{j = 1}^n c_j x_j & \\
\rm{s. \; t. } \quad & \sum_{j = 1}^n a_{ij} x_j \leq b_i, \quad & \forall i = 1, \dots, m \\
& x_j \geq 0, \quad & \forall j = 1, \dots, n
\end{align*}
各制約式に非正の係数y_iを掛けて足し合わせ整理すると、
\sum_{j = 1}^n \left ( \sum_{i = 1}^m a_{ij} y_i \right ) x_j \geq \sum_{i = 1}^m b_i y_i
を得ることができます。今、x_jは非負の変数ですので、任意のj = 1, \dots, mについてc_j \geq \sum_{i = 1}^m a_{ij} y_iが成り立てば、
\sum_{j = 1}^n c_j x_j \geq \sum_{j = 1}^n \left ( \sum_{i = 1}^m a_{ij} y_i \right ) x_j \geq \sum_{i = 1}^m b_i y_i
となって下界を得ることができます。最大の下界を求める問題は、
\begin{align*}
\max \quad & \sum_{i = 1}^m b_i y_i & \\
\rm{s. \; t. } \quad & \sum_{i = 1}^m a_{ij} y_i \leq c_j, \quad & \forall j = 1, \dots, n \\
& y_i \leq 0, & \forall i = 1, \dots, m
\end{align*}
となります。制約式が左辺\leq右辺のとき、y_iに非正の条件がつきました。
制約式が不等式(左辺\geq右辺)の場合
双対問題の求め方(左辺>=右辺の場合)
\begin{align*}
\min \quad & \sum_{j = 1}^n c_j x_j & \\
\rm{s. \; t. } \quad & \sum_{j = 1}^n a_{ij} x_j \geq b_i, \quad & \forall i = 1, \dots, m \\
& x_j \geq 0, \quad & \forall j = 1, \dots, n
\end{align*}
各制約式に非負の係数y_iを掛けて足し合わせ整理すると、
\sum_{j = 1}^n \left ( \sum_{i = 1}^m a_{ij} y_i \right ) x_j \geq \sum_{i = 1}^m b_i y_i
を得ることができます。今、x_jは非負の変数ですので、任意のj = 1, \dots, mについてc_j \geq \sum_{i = 1}^m a_{ij} y_iが成り立てば、
\sum_{j = 1}^n c_j x_j \geq \sum_{j = 1}^n \left ( \sum_{i = 1}^m a_{ij} y_i \right ) x_j \geq \sum_{i = 1}^m b_i y_i
となって下界を得ることができます。最大の下界を求める問題は、
\begin{align*}
\max \quad & \sum_{i = 1}^m b_i y_i & \\
\rm{s. \; t. } \quad & \sum_{i = 1}^m a_{ij} y_i \leq c_j, \quad & \forall j = 1, \dots, n \\
& y_i \geq 0, & \forall i = 1, \dots, m
\end{align*}
となります。制約式が左辺\geq右辺のとき、y_iに非負の条件がつきました。
ここまで、変数が非負である最小化問題について、制約条件の違いによって生じる双対問題の形の違いを丁寧に追ってきました。線形計画問題から双対問題を求める方法については、しっかり学ぶ数理最適化2.3節や、オペレーションズ・リサーチⅠにまとめられており、一読をお勧めします。
並列機械ロットスケジューリング問題と定式化
列生成法を解説した記事は、その多くが資材切り出し問題か配送計画問題を取り扱っている印象があります。そこで、今回は演習を兼ねて、別の問題を扱ってみようと思います。少し古いですが、日本経営工学論文誌55(2)に掲載されている同一並列機械ロットスケジューリング問題への列生成法の適用の問題をお借りします。
問題設定
ある原材料から、品種i = 1, \dots, Nを製造する工場があります。時間を離散単位とし、時刻t = 1, \dots, T期の生産計画を立てることを考えます。
各品種はいずれも一工程で製造することができ、この工場には同一性能の機械がM台存在します。機械はどの品種も処理することができます。ただし、前のt - 1期において、機械が未稼働であったとき、または、t-1期に品種iを生産したが別の品種i^\prime (\neq i)を生産する場合には、段取り替えが必要であり、段取り替えにはs_iの段取り替え費用と、1期分の段取り替え時間がかかります。さらに、期の途中で生産を止めることはできず、t期に各機械は、特定の品種を生産するか、t + 1期の生産に備えて段取り替えをするか、非稼働かのいずれかの状態をとります。なお、機械を1台稼働させて1期品種iの生産を行うとき、p_iの生産費用がかかります。
品種iの需要は、期別に与えられ確定的であるものとします。1つの機械が1期に生産可能な量を1単位として、需要もこの単位で表現し、品種iのt期の需要をd_{it}とします。また、ある期において品種iの生産が追いつかず、それまでの期に生産し保管していた在庫をもってしても需要を満たせない場合はバックオーダーとなります。バックオーダーは、顧客が納入を待っている状態ですので、品種iにバックオーダーが発生しているとき、バックオーダー1単位に対し、g_iのペナルティを設けます。なお、段取りと生産は各期の最初に開始し、需要への対応は各期の最後に対応することとし、残った品種iは在庫として次期に繰り越され、在庫には1単位あたりh_iの在庫保管費用がかかるものとします。
最後に、原材料は常に利用可能で、製品の在庫保管量に上限は設定しないものとします。このようなとき、費用が最小となる生産計画を立てることを考えます。
(普通の)定式化
品種iの初期在庫量をI^+_{i0}、初期バックオーダー量をI^-_{i0}とします。決定変数については、I^+_{it}をt期末における品種iの在庫量とし、I^-_{it}をt期末における品種iのバックオーダー量とします。さらに、x_{it}をt期に品種iの生産を行う機械台数、y_{it}を品種iの生産のためにt期に段取り替えを行う機械の台数とします。すると、この問題は以下のように定式化できます。
\begin{align}
\min \quad & \sum_{i = 1}^N \sum_{t = 1}^T \left(s_i y_{it} + p_i x_{it} + h_i I^+_{it} + g_i I^-_{it} \right) & \\
\rm{s. \; t. } \quad & \sum_{i = 1}^N \left(x_{it} + y_{it} \right) \leq M, \quad & \forall t = 1, \dots, T \\
& x_{it+1} \leq y_{it} + x_{it}, & \forall i = 1, \dots, N, \quad \forall t = 1, \dots, T - 1 \\
& \left( I^+_{it-1} + x_{it} \right) - \left( I^-_{it-1} + d_{it} \right) = I^+_{it} - I^-_{it}, & \forall i = 1, \dots, N, \quad \forall t = 1, \dots, T \\
& I^+_{i0} = I^-_{i0} = 0, & \forall i = 1, \dots, N \\
& I^+_{it}, \; I^-_{it} \geq 0 & \forall i = 1, \dots, N, \quad \forall t = 1, \dots, T \\
& x_{it}, \; y_{it} \in \mathbb{Z}_+ & \forall i = 1, \dots, N, \quad \forall t = 1, \dots, T
\end{align}
本問題は、生産計画を実現したときにかかる総費用を最小化することが目的です。(1)式は、目的関数であり、段取り替え費用、生産費用、在庫保管費用、バックオーダーにかかるペナルティを最小化しています。(2)式は、生産中の機械台数と段取り替え中の機械台数の合計がM台以下であることを表します。(3)式は、t期に品種iを生産できる機械台数は、その前のt-1期に品種iの生産をしていた機械台数と、段取り替えをしていた機械台数の合計以下であることを表します。(4)式は、生産量と需要量、バックオーダー量の推移を表したものであり、第1項の生産量から第2項の需要量を引くことで在庫量を求めています。なお、バックオーダーにより、負の在庫量になることもあります。(5)式は、初期在庫量と初期バックオーダー量を表し、(6), (7)式は変数制約を表します。
一般化集合分割問題への再定式化(トリッキーな定式化)
上記の定式化は、変数や制約式の個数が入力の多項式サイズとなる「普通の」定式化でした。ここで、変数の個数が入力の指数サイズとなる、トリッキーな定式化(一般化集合分割問題への定式化)を行ないます。なお、海外ではextended formulationなどとも呼ばれているようです。
品種iの解集合をS_iとします。a_{it}を品種iのt期における機械の使用台数(a_{it} = x_{it} + y_{it})とすると、制約式(3)-(7)を満たしたベクトル\bm{a}_i = (a_{i1}, \dots, a_{iT})^\topは、品種iの1つの解(生産計画)といえます。まとめると、S_i = \left \{ \bm{a}_i \in \mathbb{Z}^T_+ \; | \; (3)-(7) \right \}と表すことができます。なお、制約式(3)-(7)を満たす\bm{a}_i \in \mathbb{Z}^T_+は膨大な数が存在します。ここで、S_iの要素数をK_iとします。品種iのk \; (\in K_i)個目の解(生産計画)を\bm{a}^k_iで表し、そのときの費用をc^k_iで表すこととします。
\lambda^k_iを生産計画a^k_iを選択するとき1、それ以外を0とする変数とすれば、以下のように定式化できます。
\begin{align}
\min \quad & \sum_{i = 1}^N \sum_{k = 1}^{K_i} c^k_i \lambda^k_i & \\
\rm{s. \; t. } \quad & \sum_{i = 1}^N \sum_{k = 1}^{K_i} a^k_{it} \lambda^k_i \leq M, \quad & \forall t = 1, \dots, T \\
& \sum_{k = 1}^{K_i} \lambda^k_i = 1, & \forall i = 1, \dots, N \\
& \lambda^k_i \in \left \{0, \; 1 \right \} & \forall k = 1, \dots, K_i, \quad \forall i = 1, \dots, N
\end{align}
ここで(8)式は、選択した生産計画にかかる費用を最小化しています。(9)式は、稼働する機械台数の上限を表しています。(10)式は、各品種の生産計画はいずれか1つ選択することを表しています。(11)式は、決定変数の取りうる値を表しています。
双対問題と列生成法
実際に解きたいのは(8)-(11)式で定義された整数計画問題なのですが、変数の整数条件を緩和して得られる線形計画問題を解き、得られた最適解を(適当に)丸めることで、実務的には十分であることが多いです。よって、今後は変数\lambda^k_iの整数条件を緩和した以下の問題を考えてみます。
\begin{align*}
\min \quad & (8) & \\
\rm{s. \; t. } \quad & (9), (10) \\
& 0 \leq \lambda^k_i \leq 1, & \forall k = 1, \dots, K_i, \quad \forall i = 1, \dots, N
\end{align*}
目的関数の(8)式を確認すると、変数\lambda^k_iの和の最小化になっています。よって、各変数\lambda^k_iは、小さければ小さいほど嬉しいです。一方、\lambda^k_iは非負であることと、2つ目の制約式から、\lambda^k_iに1よりも大きい値を設定する必要はありません。よって、0 \leq \lambda^k_i \leq 1のうち、\lambda^k_i \leq 1を省いてしまっても最適解は変わりません。以上の考察から、結局以下の線形計画問題を解けばよいことがわかります。
\begin{align*}
\min \quad & (8) \\
\rm{s. \; t. } \quad & (9), (10) \\
& 0 \leq \lambda^k_i, & \forall k = 1, \dots, K_i, \quad \forall i = 1, \dots, N
\end{align*}
双対問題の導出
上記の線形計画問題に対する双対問題を求めます。(9)式に非正の係数\pi_tを掛けて足し合わせ整理すると、
\sum_{i = 1}^N \sum_{k = 1}^{K_i} \left ( \sum_{t = 1}^T a^k_{it} \pi_t \right ) \lambda^k_i \geq \sum_{t = 1}^T M \pi_t
また、(10)式に係数\mu_iを掛けて足し合わせ整理すると、
\sum_{k = 1}^{K_i} \left( \sum_{i = 1}^N \mu_i \right) \lambda^k_i = \sum_{i = 1}^N \mu_i
となります。2つの式を足し合わせて(8)式と比較すると、
\sum_{i = 1}^N \sum_{k = 1}^{K_i} c^k_i \lambda^k_i \geq \sum_{i = 1}^N \sum_{k = 1}^{K_i} \left ( \mu_i + \sum_{t = 1}^T a^k_{it} \pi_t \right ) \lambda^k_i \geq \sum_{t = 1}^T M \pi_t + \sum_{i = 1}^N \mu_i
を得ることができます。よって、双対問題は、
\begin{align}
\max \quad & \sum_{t = 1}^T M \pi_t + \sum_{i = 1}^N \mu_i & \\
\rm{s. \; t. } \quad & \mu_i + \sum_{t = 1}^T a^k_{it} \pi_t \leq c^k_i, \quad & \forall k = 1, \dots, K_i, \quad \forall i = 1, \dots, N \\
& \pi_t \leq 0, & \forall t = 1, \dots, T
\end{align}
となります。今後は、この双対問題について考えます。今後、便宜的にこの双対問題を(D)と呼びます。
限定問題(restricted problem)
K_iは品種iの解集合S_iの要素数を表していることを思い出すと、この双対問題の制約式の本数はN \sum_{i = 1}^N K_iと非常に膨大です。すると、それらの制約式を全て列挙して、ソルバーに入力し解かせるということは難しそうです。しかしS_iの中には、最適解として選ばれそうにもない非効率な解も多数含んでいるはずですが、果たしてそれらを全て考慮する必要があるでしょうか。そこで、全ての制約式を考慮するのではなく、一部の制約式だけ取り入れた(D)を解くことを考えます。今、(D)における品種iの制約式集合をJ_iとし、その一部の制約式集合を\tilde{J}_i \; (\subset J_i)とします。\tilde{J}だけで構成した(D)を考えると、
\begin{align}
\max \quad & (12) & \nonumber \\
\rm{s. \; t. } \quad & \mu_i + \sum_{t = 1}^T a^k_{it} \pi_t \leq c^k_i, \quad & \forall k \in \tilde{J}_i, \quad \forall i = 1, \dots, N \tag{13'} \\
& (14) \nonumber
\end{align}
となります。一部の制約式に限定した問題のことを、(D)の限定問題(restricted problem)といいます。今後、便宜的にこの限定問題を(RD)と呼びます。
価格問題(pricing problem)
(RD)を解くと、最適解\pi^*_tと\mu^*_iが得られます。このとき、品種i別にk^\prime \in J_i \; \backslash \; \tilde{J}_iを満たす制約式k^\primeについて、c^{k^\prime}_i - \left(\mu^*_i + \sum_{t = 1}^T a^{k^\prime}_{it} \pi^*_t \right) < 0が成り立つならば、\pi^*_tと\mu^*_iは、(D)の全ての制約式を満たしていないことになります。であれば、\tilde{J}_iに制約式k^\primeを追加(\tilde{J}_i \leftarrow \tilde{J}_i \cup k^\prime)して再度解き直せば、今度は制約式k^\primeまで考慮された解が出てくるはずです。これを品種i別にc^{k^\prime}_i - \left( \mu^*_i + \sum_{t = 1}^T a^{k^\prime}_{it} \pi^*_t \right) \geq 0となるまで繰り返せば、最適解を得ることができます。
ここで、c^{k^\prime}_i - \left( \mu^*_i + \sum_{t = 1}^T a^{k^\prime}_{it} \pi^*_t \right) < 0を満たすようなk^\primeを、全て列挙することは可能でしょうか。そもそも、J_iの数が膨大なので制約式を\tilde{J}_iに限定した問題を解いていることを思い出すと、k^\primeを全て調べることは難しそうです。よって、代わりに\min \left \{ c^k_i - \left( \mu^*_i + \sum_{t = 1}^T a^k_{it} \pi^*_t \right) \right \}を解き、最も制約違反が大きい制約式を追加することを考えます。なお、この問題のことを価格問題(pricing problem)といいます。他にも列生成小問題などとも呼ばれています。
ところで、価格問題を解くとはどういうことでしょうか。既に(RD)は解かれているため、\pi^*_tと\mu^*_iの値は既に所与です。また、この価格問題は、そもそも(D)を満たさない制約式を見つけるために解くのでした。つまり、この価格問題は\pi^*_tと\mu^*_iの値を使ってa^k_{it}を求める問題です。また、a^k_{it}にはどのような制約があったでしょうか。今、\bm{a}^k_i = (a^k_{i1}, \dots, a^k_{iT})は品種iの生産計画であり、その生産計画の費用はc^k_iで表されているのでした。a^k_{it} = x^k_{it} + y^k_{it}であること、\bm{a}^k_iが満たすべき制約は(3)-(7)式であること、生産計画の費用c^k_iはs_i y^k_{it} + p_i x^k_{it} + h_i {I^+}^k_{it} + g_i {I^-}^k_{it}で計算されることを思い出すと、
\begin{align}
& c^k_i - \left( \mu^*_i + \sum_{t = 1}^T a^k_{it} \pi^*_t \right) & \nonumber \\
= & c^k_i - \left(\mu^*_i + \sum_{t = 1}^T (x^k_{it} + y^k_{it}) \pi^*_t \right) \nonumber \\
= & \sum_{t = 1}^T (s_i y^k_{it} + p_i x^k_{it} + h_i {I^+}^k_{it} + g_i {I^-}^k_{it}) - \left(\mu^*_i + \sum_{t = 1}^T (x^k_{it} + y^k_{it}) \pi^*_t \right) \nonumber \\
= & \sum_{t = 1}^T \left \{ (s_i - \pi^*_t ) y^k_{it} + (p_i - \pi^*_t) x^k_{it} + h_i {I^+}^k_{it} + g_i {I^-}^k_{it} \right \} - \mu^*_i
\end{align}
と式変形を施せば、結局、
\begin{align*}
\min \quad & (15) & \\
\rm{s. \; t. } \quad & (3)-(7)
\end{align*}
を解いて、最適なa^k_{it}を求めれば良いことが分かります。なお、この問題は、品種別の同一並列機械ロットスケジューリング問題になっていて、品種ごとに問題を分割できた分、やや簡単になっています。元論文では、この価格問題を動的計画法で解いていますが、解さえ分かれば解き方は自由です。この価格問題の解き方は問題ごとに様々で、価格問題の問題構造に依存する部分があるといえます。例えば、第3回：はじめての配送計画の列生成法では、価格問題を整数計画問題として定式化してソルバーで解いており、実乗務制約を有する鉄道乗務員運用計画問題に対する列生成法の適用では、元々の問題構造に注目して、価格問題を制約付き最短路問題に落とし込みラベリング法を使って解いています。
限定問題が最初に考慮する制約式
これまでの議論では、既に\tilde{J}_iが存在することを前提として話してきました。しかし、一番最初のステップでは、\tilde{J}_iをどのように設定すればよいでしょうか。幸いなことに、非効率な解であればいくらでも思いつきそうです。例えば、N \leq Mと仮定して、各品種iについて「毎日1台だけ機械を稼働させる」という生産計画を作ります。この生産計画を\bm{a}_i = (a_{i1}, \dots, a_{iT})^\top = (1, \dots, 1)^\topで表現することで、この問題は解決できそうです。なお、これが実務の問題で、既に何らかの解が分かっている場合は、それを入力する事も有用そうです。
まとめ(列生成法の流れ)
補足事項
実は、双対問題を経由せずとも列生成法の説明は可能です。はじめての列生成法では、
この記事では，列生成法の設計と実行をわかりやすく説明するために，双対問題の観点から，制約式を増やす手法であると説明した．しかし，双対問題は主問題と一対一に対応するので，実は双対問題を経由する必要はない．先ほどの手続きを，主問題の観点から書き直すと，変数を生成していることになる．線形計画問題を行列形式で記述すると，変数の生成は行列の列生成になる．これが列生成法とよばれる所以であろう．
と書かれていますが、このことは、岡本先生の離散最適化基礎論 第11回の講義資料を確認すると、よく理解することができます。この講義資料では、双対問題を経由せずに価格問題などを解説しています。
https://youtu.be/pYJ98WPHz-k?feature=shared&t=3170
岡本先生は、授業動画も公開してくださっているため、自学自習に大いに役立っております。ありがとうございます。
最後に、列生成法における双対変数の取り扱いが気になったので考えてみるで指摘されている事項を考えてみます。岡本先生の講義資料を参考にすれば、双対問題を経由せずに限定主問題から価格問題を作ることで、w_jを取り扱わずに済むのではないかと考えています。記事で扱われている問題は、\min \{\bm{c}^\top \bm{x} \; | \; \bm{A} \bm{x} \geq \bm{b}, \; \bm{0} \leq \bm{x} \leq \bm{1} \}です。はじめに、\bm{I}を単位行列とし、
\tilde{\bm{A}} =
\begin{pmatrix}
\bm{A} \\
- \bm{I} \\
\end{pmatrix}
, \;
\tilde{\bm{b}} =
\begin{pmatrix}
\bm{b} \\
- \bm{1} \\
\end{pmatrix}
と定義して、元問題を\min \{\bm{c}^\top \bm{x} \; | \; \tilde{\bm{A}} \bm{x} \geq \tilde{\bm{b}}, \; \bm{0} \leq \bm{x} \}に変換します。次に、\bm{s}をスラック変数とし、
\hat{\bm{c}} =
\begin{pmatrix}
\bm{c} \\
\bm{0} \\
\end{pmatrix}
, \;
\hat{\bm{A}} =
\begin{pmatrix}
\tilde{\bm{A}}, - \bm{I} \\
\end{pmatrix}
, \;
\hat{\bm{x}} =
\begin{pmatrix}
\bm{x} \\
\bm{s} \\
\end{pmatrix}
と定義します。すると、\min \{ \hat{\bm{c}}^\top \hat{\bm{x}} \; | \; \hat{\bm{A}} \hat{\bm{x}} = \tilde{\bm{b}}, \; \bm{0} \leq \hat{\bm{x}} \}という問題を作ることができ、この形は岡本先生のスライド(28/44)の形と一致します。結局、c_{j^\prime} - \hat{\bm{c}}^\top_B \hat{\bm{A}}^{-1}_B \bm{a}_{j^\prime} < 0となる列j^\primeを求めれば良いことになり、価格問題は、\min \{ c_{j^\prime} - \hat{\bm{c}}^\top_B \hat{\bm{A}}^{-1}_B \bm{a}_{j^\prime} \; | \; j^\prime \notin J \}となります(Jは主問題の一部の制約式集合)。ここで、\hat{\bm{c}}^\top_B \hat{\bm{A}}^{-1}_Bは、すでに限定主問題を解いているので既知です。このように限定主問題から考えることで、未知の双対変数w_jを取り扱わずに済むのではないかと考えています。
まとめ
本記事では、はじめに、線形計画問題に対する双対問題の求め方を復習しました。次に、ある1つの並列機械ロットスケジューリング問題に対し列生成法を適用する様子を紹介し、その中で集合分割問題として定式化する方法と、価格問題を解く方法を紹介しました。初心者の解説ですので、わかりにくい部分や誤りのある部分などありましたら、コメント等で指摘していただけましたら幸いです。今後は、分枝限定法やDantzig-Wolfe分解などを学び、解説記事を書きたいと思います。
Discussion