ポリマトロイド交叉の双対問題に対する多項式時間アルゴリズム
ポリマトロイド交叉（二つの劣モジュラ多面体の交叉上での線形最適化）は，分離問題が劣モジュラ最小化により解けるので楕円体法を用いて多項式時間で解けます*1．では，そのLP双対は多項式時間で解けるのでしょうか？答えは解ける，なのですが，これについてちゃんと示している文献が意外と見つからなかったので，ここに解法をメモしておきます．
$f_1,f_2:2^V\to \mathbb{R}$を$f_1(\emptyset)=f_2(\emptyset)=0$を満たす劣モジュラ関数とします．（重み付き）ポリマトロイド交叉とは以下のような線形計画問題です．
$$\begin{aligned} \mathrm{max.}\ \ &w^{\top}x\\ \mathrm{s.\ t.}\ \ &x(S)\leq f_1(S)\ \ \ \forall S\subseteq V,\\& x(S)\leq f_2(S)\ \ \ \forall S\subseteq V.\end{aligned}$$
この問題に対応する分離問題は，劣モジュラ最小化を2回行うことで多項式時間で解けるので，楕円体法を用いてこの問題自身も多項式時間で解けます．
では，この問題の双対問題はどのように多項式時間で解くのでしょうか．主問題が多項式時間で解けるので，双対問題の最適値はもちろん多項式時間で得られますが，双対最適解をどう得るのかが非自明な部分です．
双対問題は以下です．
$$\begin{aligned} \mathrm{min.}\ \ &\sum_{S\subseteq V,\ i\in [2]}y_i(S)f_i(S)\\ \mathrm{s.\ t.}\ \ &y_1,y_2\in \mathbb{R}_+^{2^V}, \\ &\sum_{S\subseteq V,\ i\in [2]}y_i(S)\chi_S=w.\end{aligned}$$
特殊ケースとして，$f_1,f_2$がマトロイドのランク関数の場合はweight-splittingから双対最適解が得られて，$w$がall one vector の場合は整数性から$f_1(S)+f_2(V\setminus S)$の最小化に帰着されて，この関数は劣モジュラなので劣モジュラ最小化により双対最適解が得られます．では，一般の場合には双対最適解はどのように得られるのでしょうか．
以下のように，主問題の最適解のタイトな制約がなす分配束に着目することで得られます．
- 主問題の最適解$x^*$を楕円体法などで得る．
- 各$i\in [2]$について，$f_i(S)=x^*(S)$を満たす$S\subseteq V$たちがなす分配束のイデアル表現（Birkhoffの表現定理）を，$f_i-x^*$の最小化などにより得る．
- 得られたイデアルを$I_1,I_2$とする．$I_1$において，$\emptyset$の直上の集合$T$をとる．各$S\subseteq V$に対して，$S$が$T$を含まない場合双対変数$y_1(S)$の値を$0$に固定した双対問題を考える（$T$を含まないすべての$S$に対して変数$y_1(S)$を消去して，$T$を含む$S$に対する変数のみ残す）．この問題に対応する主問題は，$f_1$側の制約が$T\subseteq S\subseteq V$を満たす$S$に対するものだけとなる．このような$S$たちは分配束をなすので，分配束上の劣モジュラ最小化を用いて変形後の主問題も解ける．つまり，変形後の双対問題の最適値は多項式時間で求められる．このとき変形前の双対問題の最適値と変形後の最適値が同じであれば，双対最適解$y_1^*,y_2^*$であって，$y_1^*(S)>0$なるすべての$S$が$T\subseteq S$を満たすものが存在することになる．$\emptyset$の直上の集合のいずれかは，このような条件を満たす$T$なので（サポートが鎖である双対最適解の存在から従う），このような$T$を全探索で探す．所望の$T$が見つかったら，今度は$T$の直上か，もしくは$\emptyset$の直上の集合で$T$以外のものの中から，$U$であって，変数$y_1(S)$を「$S=T$または$T\cup U\subseteq S\subseteq V$」の範囲に限定して，それ以外の$y_1(S)$を消去しても最適値が変わらないものを全探索で探す．これを繰り返すことで，鎖$\mathcal{C}$であって，双対変数$y_1(S)$の範囲を$S\in \mathcal{C}$に限定しても最適値が変わらないものが得られる．これにより，変数$y_1$のサイズを多項式サイズに落とすことができる．同様に$y_2$のサイズも多項式にすれば，あとは楕円体法で双対問題が解ける．
書くと思ったよりも複雑な感じになりましたが，イデアルの最小元側から愚直に双対最適解のサポートとなりうる鎖を（途中までの鎖に制限したLPの最適値を見比べることで）構成しています．
一般に主LPの最適解から双対LPの最適解を多項式時間で構成する方法はあるのか，たまに気になります．主LPが多項式時間で解けるなら，感覚的には当然双対LPも多項式時間で解けるだろうと思うのですが，一般的な構成方法は（自分が知る限りでは）知られていないので，誰かいい感じの結果を示してほしいですね．
*1:楕円体法を使わずに解くこともできます．Schrijver B のChapter 47参照．
