Dantzig–Wolfe分解(Dantzig–Wolfe decomposition)とは、ブロックごとの制約と少数のつなぐ制約からなる線形計画問題を、各ブロックの有界な実行可能領域を頂点の凸結合で書き直した主問題に変え、列生成で解く方法である。主問題の列は頂点の数だけあるが、制限主問題の双対の乗数を価格とするブロックごとの線形計画を解けば、目的関数を改善する列が見つかるか、最適であることが分かり、列は除かないので反復は有限回で止まり、各段で価格から最適値の下界も得られる。主問題の最適値は、つなぐ制約を外した Lagrange 緩和の双対問題の最適値に等しく、切り出し問題の列生成(Gilmore–Gomory)も同じ考えによる。
Dantzig–Wolfe 分解(Dantzig–Wolfe decomposition)は、いくつかのブロックに分かれた線形計画問題を、少数の「ブロックをつなぐ制約」と、ブロックごとの易しい問題に分けて解く方法である。各ブロックの実行可能領域を頂点の凸結合で書き直すと、元の問題は「頂点の重み」を変数とする 主問題 に変わる。主問題の変数(列)は頂点の数だけあって膨大だが、単体法で必要になる「目的関数を改善する列」は、ブロックごとの線形計画(価格づけの問題)を解けば 1 本ずつ見つかる。この 列生成 を繰り返すと、有限回で最適解に達する。
方法は Dantzig と Wolfe(1960、DW60)による。主問題の双対は、つなぐ制約を外した Lagrange緩和 の双対問題と同じもので、反復の途中でも最適値の下界が得られる。切り出し問題(cutting stock problem)のように、列が組合せの対象で暗に与えられる問題にも同じ考えが使われる。
この記事では、元の問題と主問題の同値、列生成の停止の判定と有限停止、各段の下界、Lagrange 双対との一致を証明し、切り出し問題で反復を追う。
以下、ベクトルの不等式は成分ごととし、内積を $a\cdot x$ と書く。$k=1,\dots,K$ について、$c_k\in\mathbb{R}^{n_k}$、$A_k\in\mathbb{R}^{m\times n_k}$ と、空でない有界な多面体 $P_k=\{x_k\in\mathbb{R}^{n_k}\mid D_kx_k\le d_k\}$ をとり、$b\in\mathbb{R}^m$ とする。ブロック角型 の線形計画
$$
\text{(LP)}\qquad z^*:=\min\Bigl\{\sum_{k=1}^Kc_k\cdot x_k\Bigm|\sum_{k=1}^KA_kx_k=b,\ x_k\in P_k\ (k=1,\dots,K)\Bigr\}
$$
を考える。$\sum_kA_kx_k=b$ を つなぐ制約 という。つなぐ制約がなければ、問題は $K$ 個の小さな線形計画に分かれる。
$P_k$ の頂点の集合を $V_k$ とする。多面体 の定理「凸多面体は頂点の凸包」により、$V_k$ は空でない有限集合で $P_k=\operatorname{conv}V_k$ である。
変数 $\lambda_{kv}$($k=1,\dots,K$、$v\in V_k$)についての線形計画
$$
\text{(MP)}\qquad\text{最小化 }\sum_{k=1}^K\sum_{v\in V_k}(c_k\cdot v)\,\lambda_{kv}\quad\text{条件 }\sum_{k=1}^K\sum_{v\in V_k}(A_kv)\,\lambda_{kv}=b,\quad\sum_{v\in V_k}\lambda_{kv}=1\ (k=1,\dots,K),\quad\lambda\ge0
$$
を (LP) の 主問題 という。$\sum_v\lambda_{kv}=1$ を 凸結合の制約 という。$\lambda_{kv}$ の係数の列 $\bigl(c_k\cdot v;\ A_kv;\ e_k\bigr)$($e_k$ は第 $k$ 単位ベクトル)を 列 という。
1。 $\lambda_{kv}\ge0$、$\sum_v\lambda_{kv}=1$ なので $x_k$ は $V_k$ の点の凸結合で、$P_k$ は凸なので $x_k\in P_k$ である。1 次式なので
$$
\sum_kA_kx_k=\sum_k\sum_v(A_kv)\lambda_{kv}=b,\qquad\sum_kc_k\cdot x_k=\sum_k\sum_v(c_k\cdot v)\lambda_{kv}
$$
である。逆に $x_k\in P_k=\operatorname{conv}V_k$ なら、$x_k=\sum_v\lambda_{kv}v$($\lambda_{kv}\ge0$、$\sum_v\lambda_{kv}=1$)と書け、同じ計算でこの $\lambda$ は (MP) の実行可能解で値も等しい。
2。 1 により、(LP) と (MP) の実行可能解の値の集合は等しい。(MP) の実行可能領域は有界(各 $\lambda_{kv}\in[0,1]$)なので、目的関数は下に有界で、(MP) を最大化の形に直して 線形計画法 の定理「最適解の存在」を当てると最適解がある。その値は (LP) の値の集合の最小値でもあるので、1 で対応する $x$ が (LP) の最適解である。$\square$
1 の対応は 1 対 1 ではない。$P_k$ の点を頂点の凸結合に書く仕方は一般にたくさんある。$P_k$ が有界でなく直線を含まない(頂点をもつ)場合は、頂点に加えて後退錐の向きの列を足し、向きの列には凸結合の制約の係数を付けない(Lee21 Theorem 7.1・Corollary 7.2、pp. 66–67、BHM77 §12.7、pp. 389–390)。
主問題の列のうち一部 $W_k\subset V_k$ だけを使った線形計画を 制限主問題(RMP)という。等式の制約を 2 つの不等式に書いて 線形計画法 の定義「双対問題」を当てると、制限主問題の双対問題は、つなぐ制約の乗数 $\pi\in\mathbb{R}^m$ と凸結合の制約の乗数 $\sigma\in\mathbb{R}^K$(符号は自由)について
$$
\text{最大化 }\pi\cdot b+\sum_k\sigma_k\quad\text{条件 }\pi\cdot(A_kv)+\sigma_k\le c_k\cdot v\quad(k=1,\dots,K,\ v\in W_k)
$$
である。列 $(k,v)$ の 被約費用 を
$$
\bar c_{kv}(\pi,\sigma):=(c_k-A_k^{\mathsf T}\pi)\cdot v-\sigma_k
$$
とおく。双対の制約は「使っている列の被約費用が $0$ 以上」と同じである。
制限主問題が実行可能になる初めの列の集合 $W_k^{(0)}\subset V_k$ をとる。$t=0,1,2,\dots$ について次を行う。
2 の価格づけは、つなぐ制約を価格 $\pi$ で目的関数に移した、ブロック $k$ だけの線形計画である。線形計画法 の定理「最適解は頂点でとれる」により最小は頂点で達成され、単体法 は頂点で答えを返す。
(LP) は実行可能とし、制限主問題は各段で実行可能とする。
制限主問題の双対。 制限主問題の実行可能領域は有界なので最適解があり、双対問題が実行不可能なら 線形計画法 の定理「実行可能性と非有界性」により制限主問題が非有界になって矛盾する。よって双対問題も実行可能で、定理「線形計画法の双対定理」により $z^{(t)}=\pi^{(t)}\cdot b+\sum_k\sigma_k^{(t)}$ である。
1。 $x$ を (LP) の実行可能解とし、$\pi\in\mathbb{R}^m$ とする。$\sum_kA_kx_k=b$ なので
$$
\sum_kc_k\cdot x_k=\pi\cdot b+\sum_k(c_k-A_k^{\mathsf T}\pi)\cdot x_k\ge\pi\cdot b+\sum_k\min_{x'\in P_k}(c_k-A_k^{\mathsf T}\pi)\cdot x'=\mathcal{L}(\pi)
$$
で、$x$ について最小をとると $\mathcal{L}(\pi)\le z^*$ である。$\pi=\pi^{(t)}$ では最小は $\zeta_k^{(t)}$ で、前段の等式から $\mathcal{L}(\pi^{(t)})=z^{(t)}-\sum_k\sigma_k^{(t)}+\sum_k\zeta_k^{(t)}$ である。最後に、制限主問題の実行可能解は 0 を補えば (MP) の実行可能解なので、thm-dw-equiv により $z^*\le z^{(t)}$ である。
2。 すべての $k$ で $\zeta_k^{(t)}\ge\sigma_k^{(t)}$ なら、1 の左辺は $z^{(t)}$ 以上なので $z^{(t)}\le z^*\le z^{(t)}$ で、$z^{(t)}=z^*$ である。$\lambda^{(t)}$(0 を補ったもの)は (MP) の実行可能解で値 $z^*$ をもつので最適であり、thm-dw-equiv の 1 により $x$ は値 $z^*$ の (LP) の実行可能解、すなわち最適解である。
3。 $(\pi^{(t)},\sigma^{(t)})$ は制限主問題の双対の実行可能解なので、$v\in W_k$ では $\bar c_{kv}\ge0$ である。加える $v_k$ は $\bar c_{kv_k}=\zeta_k^{(t)}-\sigma_k^{(t)}< 0$ をみたすので $v_k\notin W_k$ である。列は除かないので、止まらない段ごとに $\bigcup_kW_k$ は真に大きくなり、その大きさは $\sum_k\lvert V_k\rvert$ を超えない。$\square$
1 の下界は、止まる前でも「いまの解 $z^{(t)}$ が最適値からどれだけ離れうるか」を教える。列生成は最適値の近くで改善が遅くなること(tailing off)が多いので、上界 $z^{(t)}$ と下界の最大値の差で打ち切ることが多い(BHM77 §12.7、pp. 387–388、Lee21 p. 72)。最初の列で制限主問題が実行可能にならないときは、つなぐ制約に人工変数を足した第 1 段の問題を同じ方法で解く(BHM77 §12.4、p. 375、Lee21 §7.1.2、p. 70)。
(LP) が実行可能なら、1 の $\mathcal{L}$ は最大値をもち、
$$
z^*=\max_{\pi\in\mathbb{R}^m}\mathcal{L}(\pi)
$$
である。最大を与える $\pi$ として、(MP) の双対問題の最適解の $\pi$ 成分がとれる。
(MP) は最適解をもつ(thm-dw-equiv の 2)ので、thm-dw-colgen の証明の最初の段と同じ議論で、その双対問題(制限主問題の双対の $W_k$ を $V_k$ に替えたもの)にも最適解 $(\pi^*,\sigma^*)$ があり、$z^*=\pi^*\cdot b+\sum_k\sigma_k^*$ である。双対の制約から、各 $k$ で $\sigma^*_k\le\min_{v\in V_k}(c_k-A_k^{\mathsf T}\pi^*)\cdot v=\min_{x\in P_k}(c_k-A_k^{\mathsf T}\pi^*)\cdot x$ である(頂点で最小がとれることによる)。よって $\mathcal{L}(\pi^*)\ge\pi^*\cdot b+\sum_k\sigma_k^*=z^*$ で、thm-dw-colgen の 1 の $\mathcal{L}\le z^*$ と合わせて等号が成り立つ。$\square$
$\mathcal{L}(\pi)$ は、つなぐ制約 $\sum_kA_kx_k=b$ を乗数 $\pi$ で外した Lagrange 緩和の値(最小化の形)で、つなぐ制約が等式なので $\pi$ の符号は自由である。この定理は、(LP) が線形計画なので双対ギャップがないことを述べている(Lee21 Theorem 7.5、pp. 74–75 は同じ事実を別の形で示している)。ブロックが整数の条件をもつ場合には、主問題は $\operatorname{conv}(P_k\cap\mathbb{Z}^{n_k})$ の頂点を列にした線形計画になり、その値は Lagrange緩和 の定理「Geoffrion の定理」の値と一致する。列生成で主問題を解くことと、Lagrange 双対問題を解くことは、同じ線形計画の主と双対を解くことにあたる。
幅 $W$ の原反(ロール)から、幅 $w_i$ の製品を $d_i$ 本ずつ($i=1,\dots,m$)切り出すのに、原反を何本使えばよいかを考える。1 本の原反の切り方を、$w\cdot a\le W$ をみたす整数のベクトル $a\in\mathbb{Z}_{\ge0}^m$(幅 $w_i$ を $a_i$ 本とる)で表し、切り方(pattern)という。切り方 $a$ を使う回数を $x_a$ とすると、問題の線形計画緩和は
$$
\text{最小化 }\sum_ax_a\quad\text{条件 }\sum_aa\,x_a\ge d,\quad x\ge0
$$
である。切り方は膨大にあるので、Dantzig–Wolfe の主問題と同じく、一部の切り方だけで解いて列を足す(Gilmore と Gomory、1961、GG61。Lee21 §7.3、pp. 82–84)。双対の乗数を $y\ge0$ とすると、切り方 $a$ の被約費用は $1-y\cdot a$ なので、価格づけの問題は
$$
\kappa:=\max\{y\cdot a\mid w\cdot a\le W,\ a\in\mathbb{Z}_{\ge0}^m\}
$$
という ナップサック問題 である。$\kappa\le1$ なら止まる。$\kappa>1$ でも、$y/\kappa$ はすべての切り方で $(y/\kappa)\cdot a\le1$ をみたす双対の実行可能解なので、線形計画法 の命題「弱双対性」により $d\cdot y/\kappa$ が緩和の最適値の下界になる。
$W=10$、$w=(3,4,5)$、$d=(5,4,3)$ とする。初めの切り方を、1 種類の幅だけを詰めた $(3,0,0)$、$(0,2,0)$、$(0,0,2)$ とする。
| 段 | 制限主問題の値 | 双対 $y$ | 価格づけ $\kappa$(切り方) | 下界 $d\cdot y/\kappa$ |
|---|---|---|---|---|
| $0$ | $\frac{31}6$ | $(\frac13,\frac12,\frac12)$ | $\frac76$($(2,1,0)$) | $\frac{31}7$ |
| $1$ | $\frac{19}4$ | $(\frac14,\frac12,\frac12)$ | $1$ | $\frac{19}4$ |
段 $0$ の解は $x_{(3,0,0)}=\frac53$、$x_{(0,2,0)}=2$、$x_{(0,0,2)}=\frac32$ である。切り方 $(2,1,0)$($3+3+4=10$)を足した段 $1$ の解は $x_{(2,1,0)}=\frac52$、$x_{(0,2,0)}=\frac34$、$x_{(0,0,2)}=\frac32$ で、$\kappa=1$ なので止まり、緩和の最適値は $\frac{19}4$ である。
原反の本数は整数なので、本数は $\lceil\frac{19}4\rceil=5$ 本以上必要である。実際、切り方 $(2,1,0)$ を 2 回、$(1,0,1)$ を 1 回、$(0,1,1)$ を 2 回使うと、幅 $3,4,5$ をそれぞれ $5,4,3$ 本とれるので、5 本が最小である。緩和の解を切り上げると $3+1+2=6$ 本になり、最小ではない。
各行は 1 つの条件だけを外している($K=1$)。
| 外す条件 | 例 | 成り立たなくなる結論 |
|---|---|---|
| $P_k$ が有界 | $P=[0,\infty)\subset\mathbb{R}$、最小化 $x$、つなぐ制約 $x=1$ | thm-dw-equiv((LP) は値 $1$ で実行可能、(MP) は実行不可能) |
| 凸結合の制約を (MP) に入れる | $P=[1,2]\times[0,1]$、最小化 $-x_1$、つなぐ制約 $x_2=1$ | thm-dw-equiv の 2((LP) は $-2$、凸結合の制約を除いた (MP) は下に非有界) |
| $x_k$ が連続の変数 | $P=[0,1]$ で $x\in\mathbb{Z}$、最小化 $0$、つなぐ制約 $2x=1$ | thm-dw-equiv の 1 の対応((MP) は $\lambda_1=\frac12$ で実行可能、整数の問題は実行不可能) |
1 行目:$P=\{x\mid -x\le0\}$ は空でない多面体で、頂点は $0$ だけである。(MP) のつなぐ制約は $0\cdot\lambda_0=1$ で解がない。(LP) は $x=1$ で実行可能、値 $1$ である。$P$ が有界でないことだけが違う。
2 行目:(LP) は $x_2=1$、$1\le x_1\le2$ の上で $-x_1$ を最小にし、$-2$ である。頂点は $(1,0),(2,0),(1,1),(2,1)$。凸結合の制約を除くと、$\lambda_{(2,0)}=s$、$\lambda_{(1,1)}=1$ はつなぐ制約 $\lambda_{(1,1)}+\lambda_{(2,1)}=1$ をみたし、値 $-2s-1$ は $s\to\infty$ でいくらでも小さくなる。
3 行目:$P=[0,1]$ の頂点は $0,1$。(MP) のつなぐ制約 $0\cdot\lambda_0+2\lambda_1=1$ と $\lambda_0+\lambda_1=1$ は $\lambda=(\frac12,\frac12)$ でみたされるが、対応する $x=\frac12$ は整数でない。整数の $x\in\{0,1\}$ では $2x\in\{0,2\}$ で $2x=1$ にならない。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する