blogoid

blogのようなもの

分離問題とLP

 

線形計画問題が楕円体法などによって多項式時間で解けることは有名です.しかし,例えばある問題のLP表現において,制約式の個数がその問題の入力長に関して指数個あった場合,その問題は普通の楕円体法では多項式時間で解くことはできません.では,そのようなLPが(元の問題の入力長に関する)多項式時間で解ける場合はあるのでしょうか?

実は,分離問題と呼ばれる問題が多項式時間で解けるなら,LPは制約式の個数にはよらない多項式時間で解くことができます.多面体$P$(多面体とは,$\mathbb{R}^n$におけるいくつかの線形不等式によってつくられる領域のことです.例えば,LPの実行可能領域は多面体です)に対する分離問題とは次のような問題です:

分離問題

    入力: ベクトル $y\in \mathbb{R}^n$

タスク: $y\in P$かどうかを判定し,$y\notin P$なら$c\in \mathbb{R}^n$であって$c^Ty>\mathrm{max} \{c^Tx\mid x\in P\}$を満たすものを返す.

 

$y\notin P$のときに返す$c$は$P$と$y$を分離する超平面の傾きになっています.

 あるLPの実行可能領域を多面体$P$とします.$P$に対する分離問題の多項式時間オラク*1が存在し,かつ$P$をつくる線形不等式たちのビット長の上界がわかっているなら,そのLPは制約式の個数によらない多項式時間で解けるという非常に強い定理が成り立ちます.

定理 [1]

 多面体$P$に対する分離問題の多項式時間オラクルが存在し,かつ$P$を表現するある有理数係数の線形不等式系に対して,各不等式のビット長が$\varphi$で抑えられるような$\varphi$が得られているとする.このとき,実行可能領域が$P$であるLPは,その目的関数の係数$c$のビット長と$\varphi$に関する多項式時間で解くことができる.

 

ちなみに,多項式時間で解けるの内訳として,分離問題のオラクルの呼び出しと初等的操作の回数は$\varphi$に関する多項式で抑えられ,途中で出てくる数のビット長は$\varphi$と$c$に関する多項式で抑えられます.

 

 参考文献

 [1] M. Grotschel, L. Lovasz, A. Schrijver, Geometric Algorithms and Combinatrial Optimization, Springer, Heidelberg, 1988.

*1:ここでは多項式時間オラクルの定義として,入力に対して多項式時間で正しい解を多項式長のビット列として返すというものを考えます.計算複雑性理論などで用いられる厳密なオラクルの定義についてはComputational Complexity(S. Arora, B. Barak)などを参照すると良いです(教えてくださったNさんありがとうございます).