この記事はJij Inc. Advent Calendar 2024の19日目の記事です．
はじめに
Jij Inc.の馬場です。この記事では列生成法を扱います。初めての列生成法や第３回：はじめての配送計画の列生成法【ブレインパッドの数理最適化ブログ】では集合被覆問題ベースに列生成法の説明をされていますが、実務で応用するとなると集合被覆問題で表現しきれない複雑な制約を目にすることが多々あります。検討する中で双対変数の取り扱いが少し気になったので考えてみます。
列生成法
ここでは配送計画問題を例に説明します。
経路選択問題
Rを経路候補集合、Nを拠点集合、c_jを経路jコスト、a_{ij}を経路jで輸送する拠点iの荷物量、b_iを拠点iの荷物需要量とします。x_jを、x_j=1のとき経路jを選択する、x_j=0のとき経路jを選択しない決定変数として定義すると、以下のように総コストを最小化するような経路を選択する問題に定式化できます。
\min_{x}: \sum_{j \in R} c_j x_j, \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
s.t. \ \ \ \
\sum_{j \in R} a_{ij}x_j \geq b_i,\ \ \forall i \in N, \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
x_j \in \{0, 1\}, \ \ \forall j \in R.
列生成法を適用するには、最初に経路選択問題の実行可能解になる初期経路を作成します。
経路選択問題の線形緩和問題
次に経路選択問題の線形緩和問題を考えます。変数x_jがバイナリ変数から連続変数に変化しています。
\min_{x}: \sum_{j \in R} c_j x_j, \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
s.t. \ \ \ \
\sum_{j \in R} a_{ij}x_j \geq b_i,\ \ \forall i \in N, \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
0 \leq x_j \leq 1, \ \ \forall j \in R.
ここで注意が必要なのがx_jの範囲です。初めての列生成法に書いてあるように、任意のjに対してc_j=1、任意のiに対してb_i=1、任意のi,jに対してa_{ij} \in \{0, 1\}のケースだとx_j \leq 1は不要になります。問題設定次第では必ずしもx_j \leq 1は不要、としてはいけなくなります。例えば、拠点の需要を満たすために複数のトラックで輸送するのはOK、という問題設定を考えます。以下の例だと、x_1=x_2=1が最適解になりますが、x_j \leq 1がないとx_2=2が最適解になってしまいます。
\min_{x}: 4x_0 + 3x_1+x_2, \\
\ \ \ \ \ \
s.t. \ \ \ \
3x_0 + x_1 + x_2 \geq 2, \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
0 \leq x_j, \ \ 0 \leq j \leq 2.
今回は上記のケースを想定して、x_j \leq 1を考慮して考えていきます。線形緩和問題を双対問題に変形していきますが、その前に線形緩和問題を以下のようにx_j \leq 1を-x_j \geq -1という制約条件としてみてみます。
\min_{x}: \sum_{j \in R} c_j x_j, \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
s.t. \ \ \ \
\sum_{j \in R} a_{ij}x_j \geq b_i,\ \ \forall i \in N, \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
-x_j \geq -1, \ \ \forall j \in R, \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
0 \leq x_j, \ \ \forall j \in R.
\sum_{j \in R} a_{ij}x_j \geq b_iに対する双対変数をy_i \geq 0、-x_j \geq -1に対する双対変数をw_j \geq 0とすると双対問題は以下の通りになります。
\max_{y}: \sum_{i \in N} b_i y_i - \sum_{j \in R} w_j, \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
s.t. \ \ \ \
\sum_{i \in N} a_{ij}y_i - w_j \leq c_j,\ \ \forall j \in R, \\
\ \ \ \ \ \ \ \ \ \
0 \leq y_i, \ \ \forall i \in N,\\
\ \ \ \ \ \ \ \ \ \ \
0 \leq w_j, \ \ \forall j \in R.
経路生成問題
双対問題を解きます。最適解をy_i^*, w_j^*とします。これらの値を使って経路を生成していきます。コストが下がる可能性のある経路を生成したいですが、今まで見てきた最適化問題の関係性に注目してみます。双対問題の最適値は経路選択問題の下界になっていて、下界を下げる経路を追加すれば経路選択問題の最適値も更に改善できる余地が出てきます。双対問題の最適値を下げられたからといって必ずしも経路選択問題の最適値が下がるとは限らないことに注意してください。
(経路選択問題の最適値) \geq (線形緩和問題の最適値) = (双対問題の最適値)
双対問題の最適値を下げる経路を追加する方法ですが、ここで被約費用c_j - (\sum_{i \in N} a_{ij}y_i^* - w_j^*)を考えます。y_i^*, w_j^*は双対問題の実行可能解なので、任意のjに対して被約費用は0以上です。新たな経路j'を追加し、c_j' - (\sum_{i \in N}a_{ij'}y_i^* - w_j^*) < 0となればy_i^*, w_j^*は実行不能解になるため、双対問題の最適値を下げることができます。なので被約費用を最小化するような経路を求める問題を解けば良いということになります。経路を求める問題は問題設定に応じて変わってきます。詳細は省きますが、第３回：はじめての配送計画の列生成法【ブレインパッドの数理最適化ブログ】や資材切出し問題と列生成法を参考にしてみてください。
以降は、経路を生成したら双対問題の制約に追加して、被約費用が0以上になるまで繰り返します。最後に経路選択問題を解いて終了です。
経路生成問題における双対変数の取り扱い
ここで１つ気になるのがw_jの取り扱いです。w_jは各経路に対する双対変数でしたが、経路を生成する問題でどう考慮すれば良いかという問題が生じます。これから生成する経路j'はもちろん双対問題では考慮されていないので、w_j'^*の値は分かりません。以下あたりがパッと思いつく対処法でしょうか。どうすれば良いか時間があったときに調べてみたいなと思います。
- 定式化を工夫して集合被覆問題に落とし込む
-
w_j'^*は一旦無視する
２番目ですが、考慮しない場合で影響があるのが、終了条件（被約費用が0以上の）です。終了条件に収束してきた段階ではw_j'^*を無視すると期待通りに終了しない可能性があるのでケアが必要になりそうです。
おわりに
今回は集合被覆問題に落とし込めない場合を想定して色々考えてみました。実際に解くときは定式化等を工夫して集合被覆問題に落とし込むのが良いのかもしれませんが、どうしても表現できない問題設定で列生成法を試してみたいという方の参考になれば嬉しいです。
募集
Jijでは各ポジションを絶賛採用中です！
ご興味がございましたらカジュアル面談からでもぜひ！ ご連絡お待ちしております．
数理最適化エンジニア
量子コンピューティングソフトウェアエンジニア
Rust エンジニア (アルゴリズムエンジニア)
研究チーム PMO
オープンポジション等その他の採用情報はこちら
Discussion