Document

計算量理論
6.4: TIGHTNING A CONSTRAINT
6.5: CONSTRAINT GENERATION FOR
COMBINATORIAL-OPTIMIZTION
PROBLEMS
岩間研M1 吉田
6.4 TIGHTENING A CONSTRAINT

aij(1im, 1jn), bi(1im)を整数とし、次のような整数計画
問題IPを考える。 n
max  c j x j
j 1
subject to :
n
a x
ij
j
 bi , for i  1,2,..., m
j
0  x j  1, for i  1,2,..., n
x j  Z , for i  1,2,..., n

この問題の最適解を変えずに、制約を強めるのがこの節の目
的。
ナップサック問題の利用
a x b

 ある制約
に注目する(複数の制約を同時に考
n
j 1
kj
j
k
えない) 。このとき、akj0と仮定してよい。そうでなけれ
ば、akj<0なるxjを1-xj’で置き換える。
n
a


xj
が取りうる最大値bk’を以下のナップサック問題
を用いて時、bkをbk’に置き換える。
j 1
kj
n
b : max  akj x j
'
k
j 1
subject to :
n
a
j 1
kj
x j  bk
0  x j  1, for i  1,2,..., n
x j  Z , for i  1,2,..., n
被覆不等式
akj  bk
条件 
を満たすW{1,2,...,n}を考える。
jW
 このとき任意のIPの実行可能解xに対して、
 jW x j | W | 1が成立する。これを被覆不等式と呼ぶ。
(Wの要素をすべて選んではいけない)
 被覆不等式は 
a  bk , l  W を満たすとき極小
jW  l kj
であると言う。
 現在の（線形計画法により求められた）解をx*とする。
x* がIPの実行可能解で無い場合、満たさない被覆不
等式があるかもしれない。x*が全ての被覆不等式を満
たしているか、満たさないならば、その時のWは何かを
求めたい。

被覆不等式の例
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は極小な被覆不等式である。
定理
(FINDING VIOLATED COVER INEQUALITIES)
次の整数計画問題DPkを考える。
s ( x ) : min
*
n
 (1  x ) z
*
j
j 1
n
a
j 1
kj
j
z j  bk
z j  {0,1}, for j  1,2,..., n
s(x*)1ならばx*は

n
j 1
akj x j  bk に対する全ての被覆
不等式を満たしている。
逆にs(x**)<1の時、DPkの解をz*、W:=S(z*)とすると、
 jW x | W | 1である(x*はこの被覆不等式を満たして
いない)。
j
s ( x ) : min
*
n
*
(
1

x

j )z j
j 1
n
a
証明
j 1
kj
z j  bk
z j  {0,1}, for j  1,2,..., n
zがDPkの実行可能解であることの必要十分条件は、z
が被覆不等式を構成する集合Wの特性ベクトルになっ
ていることである。
もしs(x*)1であれば、DPkで実行可能な全ての解に対
n
n
*
n
*
x
z

して  j 1 (1  x j ) z j  1、すなわち  j 1 j j  j 1 z j  1
である。よって全ての被覆不等式が成立する。
もしs(x*)<1であれば、DPkのある実行可能解z*に対し
て nj1 (1  x*j ) z *  1 、すなわちn x*j z *  n z *  1
j 1
j 1
である。
j
j
j
問題
(COVER SEPARATION)
n
整数計画問題DPk s ( x ) : min  (1  x*j ) z j
*
j 1
n
a
j 1
kj
z j  bk
z j  {0,1}, for j  1,2,..., n
はzjに1-zj’に置き換えると次の整数計画問題に帰着さ
n
れる。
max  (1  x*j ) z j '
これはナップサック問題として
j 1
n
n
解くことができる。
a
j 1
kj
z j '   akj bk
j 1
z j ' {0,1}, for j  1,2,..., n
クリーク不等式
n
注目している制約：  akj x j  bk
j 1
条件akj+akl>bk, j,kW, jkを満たすWを考える。
 このときIPの任意の実行可能解xについて、
x j  1 が成立する。これをクリーク不等式と呼ぶ。

jW
（Wの要素のうち選べるのは高々一つ。）
 クリーク不等式は任意のiWについて、あるjWが存在
しakj+akibkを満たすとき極大であると言う。
 被覆不等式の時と同じように、現在の（線形計画法によ
り求められた）解x*から、x*が全てのクリーク不等式を満
たすか、そうでないならばその時のWは何かを知りたい。

例
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
x3
x6
x5
x4
V(G)={1,2,...,n},
E(G)={(j,l)|j,lV, akj+akl>bk)}
問題
(CLIQUE SEPARATION)

次の整数計画問題CSを考える
n
s ( x* ) : max  x*j z j
j 1
z j  zl  1, j,l s.t. akj  akl  bk
z j  {0,1}, for j  1,2,..., n
被覆不等式の時と同様にs(x*)1か否かでx*が全てのク
リーク不等式を成立させているかを判定できる。
 無向グラフGを、V(G)={1,2,...,n}, E(G)={(j,l)|j,lV,
akj+akl>bk)}で定める。頂点iにxi*の重みを持たせると、
CSを解くことはGの最大重みのクリークを求めることに
等しい。

例
7x1+2x2+x3+3x4+6x5+5x68
0x1,x2,x3,x4,5,x61
x1,x2,x3,x4,5,x6Z
という制約を考える。
x1
x2
n
s ( x ) : max  x*j z j
*
x3
x6
j 1
z j  zl  1, j,l s.t. akj  akl  bk
z j  {0,1}, for j  1,2,..., n
x5
x4
リフティング
IPの実行可能解xが満たす不等式  j 1a j x j  
を考える。ajは非負と仮定する。
添え字kを選び、次のリフティング問題LPを考える。
n

 k :   max  a j x j
jk
subject to :
a
j k
ij
x j  bi  aik , for i  1,2,..., m
0  x j  1, for j  k
x j  Z , for j  k
LPの制約部分はIPでxk=1と仮定したときの形になって
いる。
リフティング
 k :   max  a j x j
jk
subject to :
a
jk
ij
x j  bi  aik , for i  1,2,..., m
0  x j  1, for j  k
x j  Z , for j  k
もしLPが実行可能解を持たなければxk=0である。
 もしそうでなければ、任意のak’kに対して、
a 'k xk   j  k a j x j   がIPの実行可能解において成立
する。
これを用いて制約式を強めることができる。

例
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が得られる。
6.5 CONSTRAINT GENERATION FOR
COMBINATORIAL-OPTIMIZATION
PROBLEMS
整数計画問題の中には、自然な変数の数に比べて大量
の制約式を必要とするものがある。Gを無向グラフとし、
P(G)をGのハミルトン閉路の特性ベクトルの凸包とする。
最小重みのハミルトン閉路を求める問題は次のように定
式化される。
min
 c (e) x
e
eE ( G )
subject to :
x


e
e
 2, v  V (G ) (次数の制約 )
G (v)
x
e
eE ( G [W ])
| W | 1, W  V (G ),3 | W | V (G )  3 (部分閉路除去不等式 )
0  xe  1, e  E (G )
xe  Z , e  E (G )
全ての制約式（特に部分閉路除去不等式）を明示的に
列挙するのは非実用的である。
*
E (G )
x

R
 そこで
が与えられた時に、x*が満たしていな

い部分閉路除去不等式を生成する方法を考える。

x*は部分閉路除去不等式以外を満たすとする。ある
*
x
SV(3|S| |V|-3)が e ( S ) e  2 であるとき、W:=Sまた
はW:=V(G)\Sはx*が満たしていない部分閉路除去不等
式を構成する。
*
x
 逆に全てのSV(3|S| |V|-3)についてe ( S ) e  2
の時、 x*は全ての部分閉路除去不等式を満たす。

G
G
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):=  c(e)   l (e)
e G ( S )
e G ( S )

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
全ての部分閉路除去不等式を用いても、ハミルトン閉
路多面体P(G)が得られるわけではなく、P(G)外のベクト
ルも実行可能解となっている。
 櫛を用いて、有理数解をいくつか取り除くことができる。
 Gの櫛は柄G[W](WV(G))と歯FE(G)からなり、以下の
性質を満たす。
1. 3|W||V(G)|-1
2. |F|3,|F|は奇数
3. FG(W)
4. Fはマッチングをなす

櫛の例
G[W]
F

櫛は以下の2-factor不等式を定める。
| F | 
xe   xe | W |  

 2 
eE ( G[W ])
eF
THEOREM
(VALIDITY OF
2-FACTOR INEQUALITIES)
SE(G)は任意のvV(G)に対してSG(v)=2を満たすと
する。このときx(S)は2-factor不等式  xe   xe | W |  | F | 
 2 
eE ( G[W ])
eF
を満たす。
 証明
SE(G[W])がWのハミルトン閉路になっているとき：
SF=である。このときx(S)を2-factor不等式に代入す
ると、左辺は|W|となるので、x(S)は2-factor不等式を満た
す。

G[W]
F
THEOREM
(VALIDITY OF
2-FACTOR INEQUALITIES)
SE(G[W])がWのハミルトン閉路になっていないとき：
SがW中でp個のパスを形成しているとする。
この時|SE(G[W])|=|W|-pである。
また|SF|2pである。
p=3
|SE(G[W])|=|W|-p=5
G[W]
|SF|2p=6
F
x(S)を2-factor不等式に代入すると、(左辺)|W|+pとなり
2p=|S F||F|から、不等式は成立する。
| F | 
xe   xe | W |  

 2 
eE ( G[W ])
eF
EXERCISE
(VIOLATED

2-FACTOR INEQUALITY)
以下のグラフは最大重みハミルトン閉路を求める整数
計画問題を線形計画問題として解いたときに得られる
有理数解である。この有理数解は全ての部分閉路除去
不等式を満たしているが、満たしていない2-factor不等
式がある。
１
1/2
1/2
１
1/2
1/2
1/2
1/2
１
EXERCISE
(VIOLATED

2-FACTOR INEQUALITY)
以下のグラフは最大重みハミルトン閉路を求める整数
計画問題を線形計画問題として解いたときに得られる
有理数解である。この有理数解は全ての部分閉路除去
不等式を満たしているが、満たしていない2-factor不等
式がある。 W
１
1/2
1/2
１
1/2
x
e
eE ( G [W ])
1/2
1/2
1/2
１
| W | 1, W  V (G ),3 | W | V (G )  3
EXERCISE
(VIOLATED

2-FACTOR INEQUALITY)
以下のグラフは最大重みハミルトン閉路を求める整数
計画問題を線形計画問題として解いたときに得られる
有理数解である。この有理数解は全ての部分閉路除去
不等式を満たしているが、満たしていない2-factor不等
式がある。 W
F
１
1/2
1/2
１
1/2
1/2
1/2
1/2
１
| F | 
x

x

|
W
|



e
e
 2 
eE ( G[W ])
eF

全ての2-factor不等式を用いても、ハミルトン閉路多面
体P(G)を表現できていない(P(G)外の点も実行可能解
となっている)。他にもP(G)を記述する不等式は数多く
知られているが、P(G)を線形不等式のみで記述するこ
とはまだなされていないと思われる。
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
PRIZE-COLLECTING TRAVELING
SALESPERSONを整数計画問題として定式化
max
 f (i) y
iV ( G )  v
i

 c (e) x
eE ( G )
e
subject to :
x


e
e
 2 yi , i  V (G )
G (i )
x
e
eE ( G [W ])

 y , W  V (G )  v, w W (部分閉路除去不等式)
iW  w
i
0  x e  1, e  E (G ) \  G (v)
0  xe  2, e   G (v)
wを通りvを通らない閉路を除去
0  yi  1, i  V (G )  v
G
xe  Z , e  E (G )
yi  Z , i  V (G )  v
yv  1
v
w
x
e
eE ( G [W ])


 y , W  V (G)  v, w W のSEPARATION
iW  w
i
x*  RE (G ) , y*  RV (G ) , w V (G) を固定し、次の線形
計画問題TSPを考える。
s : max

eE ( G ) \
xe* ze 
G (v)
y u
*
i i
iV ( G ) \{ v , w}
subject to :
ze  ui , ze  u j , {i, j}  E (G ) \  G (v)
0  ze  1, e  E (G ) \  G (v)
0  ui  1, i V (G ) \ {v, w}
uw  1
s0ならばx*,y*,wがすべての部分閉路除去不等式を満
たし、s>0ならばある部分閉路除去不等式を満たさない
ことを示す。
もし eE (G[W ]) xe  iW  w yi , W  V (G )  v, w  W なるW
が存在すれば、 ze  1, e  E (G[W ])
ui  1, i  W  w
とすることで、s0。
s : max

eE ( G ) \
xe* ze 
G (v)
*
y
 i ui
iV ( G ) \{ v , w}
subject to :
ze  ui , ze  u j , {i, j}  E (G ) \  G (v)
0  ze  1, e  E (G ) \  G (v)
0  ui  1, i V (G ) \ {v, w}
uw  1
逆にあるz*,u*でs0すなわち
* *
* *
x
z

y
eE (G[W ]) e e iW w i ui , W  V (G)  v, w W
とする。z1,u1を次のように定める。
*

1
,

z
1
e 0
ze  
0, otherwise
 1, ui*  0
u 
0, otherwise
1
i

ui*
ui1
ze*
ze1
uj*
uj1
* 1
* 1
x
z

y
ui , W  V (G )  v, w  W

e
e
i
eE ( G [W ])
iW  w
となり、これはすなわちx*,y*,wが満たさない部分閉路除
去不等式になっている。

Download Report