計算量理論 6. 4: tightning a constraint 6

Presentation on theme: "計算量理論 6. 4: tightning a constraint 6"— Presentation transcript:

1 計算量理論 6. 4: tightning a constraint 6
計算量理論 6.4: tightning a constraint 6.5: constraint generation for combinatorial-optimiztion problems 岩間研M1 吉田

2 6.4 Tightening a Constraint
aij(1im, 1jn), bi(1im)を整数とし、次のような整数計画 問題IPを考える。 この問題の最適解を変えずに、制約を強めるのがこの節の目 的。

3 ナップサック問題の利用 ある制約 に注目する(複数の制約を同時に考 えない) 。このとき、akj0と仮定してよい。そうでなけれ ば、akj<0なるxjを1-xj’で置き換える。 　　　　　が取りうる最大値bk’を以下のナップサック問題 を用いて時、bkをbk’に置き換える。 i=kに固定する

4 被覆不等式 条件 を満たすW{1,2,...,n}を考える。
このとき任意のIPの実行可能解xに対して、 　　　　　　　 　　　　　　　が成立する。これを被覆不等式と呼ぶ。 (Wの要素をすべて選んではいけない) 被覆不等式は　　　　　　　　　　　　　　を満たすとき極小 であると言う。 現在の（線形計画法により求められた）解をx*とする。 x* がIPの実行可能解で無い場合、満たさない被覆不 等式があるかもしれない。x*が全ての被覆不等式を満 たしているか、満たさないならば、その時のWは何かを 求めたい。 i=kは相変わらず固定

5 被覆不等式の例 7x1+2x2+x3+3x4+6x5+5x68 0x1,x2,x3,x4,5,x61 x1,x2,x3,x4,5,x6Z という制約を考える。 このときx2+x3+x52は極小な被覆不等式である。

6 定理 (finding violated cover inequalities)
次の整数計画問題DPkを考える。 s(x*)1ならばx*は　　　　　　　　　　に対する全ての被覆 不等式を満たしている。 逆にs(x*)<1の時、DPkの解をz*、W:=S(z*)とすると、　　　　　　　　　　 　　　　　　　である(x*はこの被覆不等式を満たして いない)。

7 証明 zがDPkの実行可能解であることの必要十分条件は、z が被覆不等式を構成する集合Wの特性ベクトルになっ ていることである。 もしs(x*)1であれば、DPkで実行可能な全ての解に対 して 、すなわち である。よって全ての被覆不等式が成立する。 もしs(x*)<1であれば、DPkのある実行可能解z*に対し て 、すなわち である。

8 問題 (cover separation) 整数計画問題DPk はzjに1-zj’に置き換えると次の整数計画問題に帰着さ れる。
これはナップサック問題として 解くことができる。

9 クリーク不等式 注目している制約： 条件akj+akl>bk, j,kW, jkを満たすWを考える。
このときIPの任意の実行可能解xについて、　　　　　　　　　　　　　　 　　が成立する。これをクリーク不等式と呼ぶ。 （Wの要素のうち選べるのは高々一つ。） クリーク不等式は任意のiWについて、あるjWが存在 しakj+akibkを満たすとき極大であると言う。 被覆不等式の時と同じように、現在の（線形計画法によ り求められた）解x*から、x*が全てのクリーク不等式を満 たすか、そうでないならばその時のWは何かを知りたい。

10 例 7x1+2x2+x3+3x4+6x5+5x68 0x1,x2,x3,x4,5,x61 x1,x2,x3,x4,5,x6Z
という制約を考える。 このときx1+x4+x51は極大なクリーク不等式である。 x1 x2 V(G)={1,2,...,n}, E(G)={(j,l)|j,lV, akj+akl>bk)} x3 x6 x4 x5

11 問題 (clique separation)
次の整数計画問題CSを考える 被覆不等式の時と同様にs(x*)1か否かでx*が全てのク リーク不等式を成立させているかを判定できる。 無向グラフGを、V(G)={1,2,...,n}, E(G)={(j,l)|j,lV, akj+akl>bk)}で定める。頂点iにxi*の重みを持たせると、 CSを解くことはGの最大重みのクリークを求めることに 等しい。

12 例 7x1+2x2+x3+3x4+6x5+5x68 0x1,x2,x3,x4,5,x61 x1,x2,x3,x4,5,x6Z という制約を考える。 x1 x2 x3 x6 x4 x5

13 リフティング IPの実行可能解xが満たす不等式 を考える。ajは非負と仮定する。 添え字kを選び、次のリフティング問題LPを考える。
LPの制約部分はIPでxk=1と仮定したときの形になって いる。

14 リフティング もしLPが実行可能解を持たなければxk=0である。 もしそうでなければ、任意のak’dkに対して、
　　　　　　　　　　　　　がIPの実行可能解において成立 する。 これを用いて制約式を強めることができる。

15 例 7x1+2x2+x3+3x4+6x5+5x68 0x1,x2,x3,x4,5,x61 x1,x2,x3,x4,5,x6Z という制約を考える。 このときx2+x4+x62は極小な被覆不等式で、これをx1に ついてリフティングする。 最初の制約でx1=1とすると、2x2+x3+3x4+6x5+5x61 これを満たすx2,x4,x6に対するx2+x4+x6の最大値は0。 よって2x1+x2+x3+x52が得られる。

16 6.5 constraint Generation for Combinatorial-Optimization Problems
整数計画問題の中には、自然な変数の数に比べて大量 の制約式を必要とするものがある。Gを無向グラフとし、 P(G)をGのハミルトン閉路の特性ベクトルの凸包とする。 最小重みのハミルトン閉路を求める問題は次のように定 式化される。

17 全ての制約式（特に部分閉路除去不等式）を明示的に 列挙するのは非実用的である。
そこで　　　　　　　が与えられた時に、x*が満たしていな い部分閉路除去不等式を生成する方法を考える。 x*は部分閉路除去不等式以外を満たすとする。ある SV(3|S| |V|-3)が　　 　　　　　　であるとき、W:=Sまた はW:=V(G)\Sはx*が満たしていない部分閉路除去不等 式を構成する。 逆に全てのSV(3|S| |V|-3)について　　　　　　　　　　 の時、 x*は全ての部分閉路除去不等式を満たす。 最小カットを使えばSが見つかる

18 separation algorithm for subtour-elimination Inequalities
x*は被覆不等式以外を満たすとする。 有向グラフG’を作る。V(G’):=V(G)とする。E(G’)は eE(G)それぞれを有向枝e’に置き換えることで得る(向 きはどちらでも良い)。 上界関数c: E(G’)→Rをc(e’):=xe*で、 下界関数l: E(G’)→Rをl(e’):=-xe*で定める。 一点vを選び、全てのwV(G’)-vに対してv-w最小容量 カットセットSwを求める。 SV(G)はvS,wSのときv-wカットセットと言う。 カットセットの容量C(S):= カットセットについて説明

19 SをC(S):=min C(Sw)となるように選ぶ
C(S)2であれば、 x*は全ての部分閉路除去不等式を満たす。 C(S)<2であれば、x*はW:=SかW:=V(G)\Sが構築する部分閉路除去不等式を満たさない。 次数の制約は満たしているので、C(S)<2であれば、自 動的に3|S| |V|-3になる。 S S S

20 全ての部分閉路除去不等式を用いても、ハミルトン閉 路多面体P(G)が得られるわけではなく、P(G)外のベクト ルも実行可能解となっている。
櫛を用いて、有理数解をいくつか取り除くことができる。 Gの櫛は柄G[W](WV(G))と歯FE(G)からなり、以下の 性質を満たす。 3|W||V(G)|-1 |F|3,|F|は奇数 FdG(W) Fはマッチングをなす

21 櫛の例 櫛は以下の2-factor不等式を定める。 G[W] F

22 theorem (validity of 2-factor inequalities)
SE(G)は任意のvV(G)に対してSdG(v)=2を満たすと する。このときx(S)は2-factor不等式　　　　　　　　　　　　　　　　　 を満たす。 証明 SE(G[W])がWのハミルトン閉路になっているとき： SF=である。このときx(S)を2-factor不等式に代入す ると、左辺は|W|となるので、x(S)は2-factor不等式を満た す。 G[W] F

23 theorem (validity of 2-factor inequalities)
SE(G[W])がWのハミルトン閉路になっていないとき： SがW中でp個のパスを形成しているとする。 この時|SE(G[W])|=|W|-pである。 また|SF|2pである。 x(S)を2-factor不等式に代入すると、(左辺)|W|+pとなり 2p=|S F||F|から、不等式は成立する。 p=3 |SE(G[W])|=|W|-p=5 |SF|2p=6 G[W] F

24 exercise (violated 2-factor inequality)
１ 1/2 1/2 １ 1/2 1/2 1/2 1/2 １

25 exercise (violated 2-factor inequality)
W １ 1/2 1/2 １ 1/2 1/2 1/2 1/2 １

26 exercise (violated 2-factor inequality)
W F １ 1/2 1/2 １ 1/2 1/2 1/2 1/2 １

27 全ての2-factor不等式を用いても、ハミルトン閉路多面 体P(G)を表現できていない(P(G)外の点も実行可能解 となっている)。他にもP(G)を記述する不等式は数多く 知られているが、P(G)を線形不等式のみで記述するこ とはまだなされていないと思われる。

28 problem (prize-collecting traveling salesperson)
Gを無向グラフとし、始点vV(G)を選ぶ。V(G)-v上の正 関数fとE(G)上の正関数cが与えられる。eE(G)を通る 際のコストはc(e)であり、頂点iに入るときに得られる利益 はf(i)である。 vを始点として、ほかの頂点を高々1回通り、 vに戻ってくることを考える。このときに得られる利益を最 大にしたい。 G v w

29 prize-collecting traveling salespersonを整数計画問題として定式化
wを通りvを通らない閉路を除去 G v w

30 のseparation を固定し、次の線形 計画問題TSPを考える。
s0ならばx*,y*,wがすべての部分閉路除去不等式を満 たし、s>0ならばある部分閉路除去不等式を満たさない ことを示す。

31 もし　　　　　　　　　　　　　　　　　　　　　　　　　　　なるW が存在すれば、 とすることで、s>0。

32 逆にあるz*,u*でs>0すなわち とする。z1,u1を次のように定める。 となり、これはすなわちx*,y*,wが満たさない部分閉路除 去不等式になっている。 ze* ui* uj* ze1 ui1 uj1