chap0_4

A First Course in Combinatorial
Optimization
Chapter 0.4-0.9
岩間研究室 D2
川原純
0.4 感度分析
• 1ページしかないので、省略
0.5 Polytope
• polytope （多面体）についての定理
–
–
–
–
–
次元定理
ミンコフスキーの定理
余分な不等式の定理
ファセットの必要性
ファセットの一意性
注意
以下で紹介する定理はすべて幾何学的に自明なことである
多面体の次元
• 定義多面体 P の次元
dim (P) = （P 内のアフィン独立な点の最大個数）－ 1
P が線分の場合
1次元
多角形の場合
2次元
n 次元の多面体 P が n 次元空間にあるとき、
P を full dimensional という。
多面体の場合
3次元
幾何学的な直感と一致
方程式の独立性
• m 本の方程式
a11x1 + a12x2 + … + a1nxn = b1
...
am1x1 + am2x2 + … + amnxn = bn
が線形独立であるとは、m 個の点
線形独立であることと定義する。
線形独立でない
2x + 3y = 4
4x + 6y = 8
線形独立である
x + 2y = 3
x–y=4
a11
a12
...
a1n
b1
a21
am1
a22
am2
... … ...
a2n
amn
b2
bm
が
次元定理
• 定理 n 次元空間にある多面体 P について、
dim(P) = n – e
e は「P に属するすべての点が満たす線形独立な
方程式の個数の最大値」
例：2 次元（平面）上にある線分 P
例：2 次元上にある点 P
2x – 4y ≦ 3
P
x + 2y ≧ 5
2x – 4y = 3
点も多面体とみなす
P
3x – 2y = 4
3x – 2y = 4
方程式の本数は 1 本なので、dim(P) = 2 – 1 = 1
方程式の本数は 2 本なので、
dim(P) = 2 – 2 = 0
次元定理の証明
• X を P の頂点集合とする。
y
X = {x, y, z, w}
z
x
行列を作る
w
x1
y1
G=
z1
w1
x2
y2
z2
w2
x3
y3
z3
w3
1
1
1
1
dim(P) = n – e
e は方程式の本数
正確には P = conv(X)
次元定理の証明
• X を P の頂点集合とする。
dim(P) = n – e
e は方程式の本数
正確には P = conv(X)
y
X = {x, y, z, w}
z
x
行列を作る
w
x1
y1
G=
z1
w1
x2
y2
z2
w2
x3
y3
z3
w3
P の定義より
dim(P) = rank(G) － 1
1
1
1
1
(x1, x2, x3) と (y1, y2, y3) が
アフィン独立
⇔ (x1, x2, x3, 1) と (y1, y2, y3, 1) が
線形独立
dim(P) はアフィン独立な点の個数
マイナス1
rank(G) は線形独立な行ベクトルの本数
次元定理の証明
• X を P の頂点集合とする。
dim(P) = n – e
e は方程式の本数
正確には P = conv(X)
y
X = {x, y, z, w}
P の定義より
z
x
行列を作る
w
α1
α2
α3
β
x1
y1
G=
z1
w1
∈ Ker(G) なら
x2
y2
z2
w2
α1
α
G 2
α3
β
dim(P) = rank(G) － 1
x3
y3
z3
w3
1
1
1
1
線形代数の rank-nullity 定理（次元定理）より
dim(Ker(G)) + rank(G) = n + 1
（G の列は n + 1 個なので）
2 式から
dim(P) = n – dim(Ker(G))
～
～
～
α1x1 + α2x2 + α3x3 + β’ = 0
= 0 より、
Ker(G) の次元 =
線形独立な方程式の本数 e となる
～
x = λ1x + λ2y + λ3z + λ4w
α1x1 + α2x2 + α3x3 + β = 0
α1y1 + α2y2 + α3y3 + β = 0
α1z1 + α2z2 + α3z3 + β = 0
α1w1 + α2w2 + α3w3
dim(P) = n – e
e は方程式の本数
λ1 + λ2 + λ3 + λ4 = 1
次元定理の証明
+β=0
2t
3t
4t
5t
～
なので、任意の x ∈P について
～
～
α1•x1 +Xα2を
x2～+P
α3xの頂点集合とする。
Ker(G) =
3 + β’ = 0
y
t は実数
X = {x, y, z, w}
の例で考えてみると、
z
x
行列を作る
w
α1
α2
α3
β
x1
y1
G=
z1
w1
∈ Ker(G) なら
x2
y2
z2
w2
α1
α
G 2
α3
β
x3
y3
z3
w3
1
1
1
1
⇔
2t x1 + 3t x2 + 4t x3 + 5t = 0
2 x1 + 3 x2 + 4 x3 + 5 = 0
Ker(G) からは独立な方程式は１本しか作れない
2 式から
dim(P) = n – dim(Ker(G))
～
～
～
α1x1 + α2x2 + α3x3 + β’ = 0
= 0 より、
Ker(G) の次元 =
線形独立な方程式の本数 e となる
face （フェイス）と facet （ファセット）
•
が多面体 P に対し有効であるとは、
P に属するすべての点がこの不等式を満たすこと。
• 有効な不等式は face を描く。
例：2 次元（平面）上にある多角形 P
6x – 3y ≦2
2x – 4y ≦ 3
有効な不等式
P
face
(facet)
face
(extreme
point)
有効な不等式
P
0 次元の face を extreme point、
dim(P) – 1 次元の face を facet と呼ぶ
face を表す式
2x – 4y ≦ 3
P:
有効な不等式
P
face
(facet)
3x + 4y ≦ 5
x + 2y ≦ 3
2x – 4y ≦ 3
2x – 4y = 3
3x + 4y ≦ 5
F : 3x + 4y ≦ 5
x + 2y ≦ 3
x + 2y ≦ 3
ミンコフスキーの定理
• 定理
かつ、P が有界のとき、P は多面体である。
証明
X を P の extreme point の集合とする。明らかに conv(X) ⊂ P である。
～
P
conv(X)
となる x が存在すると仮定して
矛盾を示す。
X は extreme point の集合
ミンコフスキーの定理の証明
x2
x1
y conv(X)
X = { x1, x2, x3 }
x3
なので、
成分にわけてかくと
conv(X) の中の点は
y = λx1 x1 + λx2 x2 + λx3 x3
λx1 + λx2 + λx3 = 1
とかける
を満たすような λx は存在しない。
を満たすような λx は存在しない。
X は extreme point の集合
ミンコフスキーの定理の証明
Farkas の定理
(I), (II) のいずれか一方のみが解をもつ
(I)
を満たすような λx は存在しない。
Farkas の定理より、
(II)
を満たす t 、c は存在する。
X は extreme point の集合
ミンコフスキーの定理の証明
～
≧ －t
xは
～
x
P
<－t
≧ －t
≧ －t
を満たすような λx は存在しない。
Farkas の定理より、
の実行可能解で、値は－t 未満となるが、
すべての extreme point での値は－t 以上
となるので、矛盾。
を満たす t 、c は存在する。
余分な不等式の定理
• 定理 P の dim(P) – 1 次元未満の face を描く
有効な不等式は余分である。 P を表す式として不要である。
例：2 次元（平面）上にある多角形 P
6x – 3y ≦2
2x – 4y ≦ 3
余分ではない
P
face
0 次元
余分である
P
face
1 次元
jump 20
定理
P の dim(P) – 1 次元未満の face を描く有効な不等式は余分である。
余分な不等式の定理の証明
P を表す式を
線形独立
とすると、
とする。
を満たす
が存在する。
次元定理より、dim(P) = n – k である。
が成り立つ。
定理
P の dim(P) – 1 次元未満の face を描く有効な不等式は余分である。
定理の証明の続き
• 一般性を失うことなく、face F を描く不等式を
とする。
x と x1 を結んだ線分上に x2 が存在。
が成り立つ。
この不等式は P を表すのに余分でないと
仮定する。以下を満たす x1 が存在
x2は F 内にあるので、
が成り立つ。
ファセットの必要性
• 定理多面体 P の各ファセット F について、F を
描く有効な不等式は、 P を表すのに必要である。
2x – 4y ≦ 3
P
facet
jump 22
•定理
多面体 P の各ファセット F について、F を描く有効な不等式は、 P を表すのに必要
定理の証明
線形独立
Ｐ ⊂ Rn
dim(P) = n
ファセットの一意性
• 定理（Unique Description Theorem）
P を full-dimensional な多面体とする。
P のファセットを描く有効な不等式は（定数倍を除き）
一意に定まる。
逆に、フェイスF が（定数倍を除き）一意な不等式で
表されるなら、F は P のファセットである。
2x – 4y ≦ 3
P
facet
jump 24
定理ファセットの不等式は一意に定まる。逆に、一意に定まるフェイスの不等式はファセット。
定理の証明
0.6 ラグランジュ緩和
• f を Rm → R なる凸関数とする。
～
が成り立つとき、h ∈
Rm
～
を f の π における劣勾配とよぶ。
～
f
傾き h
f がπで微分可能なら
劣勾配は一意に定まる
（勾配と同じ）
～
π
π
0.6 ラグランジュ緩和
• f を Rm → R なる凸関数とする。
～
が成り立つとき、h ∈
Rm
～
を f の π における劣勾配とよぶ。
f
～
傾き h
微分不可能なとき、
劣勾配は複数の値をとりうる
～
π
π
劣勾配法
• 凸関数 f の最小化を考える
劣勾配法
1.
2.
3.
4.
5.
m を選ぶ。
k～:= 0 にし、π～0 ∈R
～
k
π での劣勾配 hk を計算する（1つ選ぶ）
ステップサイズ λk (> 0) を選ぶ
～
～k+1
～
k
k
π
:= π – λk h
～
終了条件（hk = 0）を満たさないならステップ2へ
f
λ1
～
h1
λ0
～
～
～
π2 π1 π0
π
～
h0
ステップサイズλk の選び方は
いろいろある
凸関数 f の最小化
劣勾配法
1.
2.
3.
4.
5.
m を選ぶ。
k～:= 0 にし、π～0 ∈R
～
k
π での劣勾配 hk を計算する（1つ選ぶ）
ステップサイズ λk (> 0) を選ぶ
～
～k+1
～
k
k
π
:= π – λk h
～
終了条件（hk = 0）を満たさないならステップ2へ
勾配ベクトルの
逆向き
λ1
～
h1
λ0
～
～
π2
～
π1
π0
～
h0
ラグランジュ緩和
subject to
subject to
(P’)
(P)
for i = 1,2,...,m
x∈P
P と P’ の最適解は同じである。
for i = 1,2,...,m
x∈P
ラグランジュ緩和
subject to
subject to
(P’)
(P)
for i = 1,2,...,m
for i = 1,2,...,m
x∈P
x∈P
P と P’ の最適解は同じである。
(P’’)
P’’ を P のラグランジュ緩和という
P の最適解 ≦ P’’ の最適解
subject to
x∈P
制約条件が不等式の場合
ラグランジュ緩和
subject to
非負の数
subject to
(P’)
(P)
for i = 1,2,...,m
x∈P
L(π)を P のラグランジュ緩和という
P の最適解 ≦ L(π) の最適解
for i = 1,2,...,m
x∈P
非負の数
(L(π))
subject to
x∈P
制約条件を破ったときの
罰金とみなすことができる
ラグランジュ緩和定理
(L(π))
subject to x ∈ P
C := { π∈Rm | π ≧ 0 }
a. 任意のπ∈C について、
(P)の最適解 ≦ (L(π)) の最適解
b. f は凸、区分的に線形。
～
～
～
c. π∈ C、x が (L(π)) の最適解、
～
h ∈ Rmを、
～
h :=
等号が成立するπは存在
～
～
とすると、h は f のπでの劣勾配となる。
f
この定理からいえること
f の最小値を求めれば、
(P)の最適解がわかる。
f は凸なので、劣勾配法が
使える。しかも、劣勾配は
簡単に求まる。
例題
P = { (x1, x2) | 0 ≦ x1, x2 ≦ 1}
z = max x1 + x2
(P)
subject to
3x1 – x2 ≦ 1
x1 + 3x2 ≦ 2
x∈P
P の最適解を求めるため、
ラグランジュ緩和問題 L(π1, π2) の
関数 f の最小値を求める
L(π1, π2)
f (π1, π2) = π1 + 2π2
+ max { (1 – 3π1 – π2) x1 + (1 + π1 – 3 π2) x2 }
subject to
x∈P
L(π1, π2)
P = { (x1, x2) | 0 ≦ x1, x2 ≦ 1}
f (π1, π2) = π1 + 2π2
+ max { (1 – 3π1 – π2) x1 + (1 + π1 – 3 π2) x2 }
subject to
x∈P
1 – 3π1 – π2 ≧ 0 のとき、x1 = 1 にすると f が最大になる
1 +π1 – 3π2 ≧ 0 のとき、x2 = 1 にすると f が最大になる
– 3π1 – π2 ≧ 0 かつ 1 +π1 – 3π2 ≧ 0 のとき、
f (π1, π2) = 2 – π1 – 2π2
π2
π1 + 2π2
したがって、 1
残り3通りも同様に計算をする
1 – 2π1 + π2
1 +π1 – 3π2 = 0
2/5
1 + 2π1 – π2
π1
2 – π1 – 2π2
1/5
1 – 3π1 – π2 = 0
L(π1, π2)
P = { (x1, x2) | 0 ≦ x1, x2 ≦ 1}
f (π1, π2) = π1 + 2π2
+ max { (1 – 3π1 – π2) x1 + (1 + π1 – 3 π2) x2 }
subject to
x∈P
この例では簡単に f の式が
求まったが、一般には劣勾配法で
f の最小値を求める
π2
π2
π1
f はπ1 = 1/5, π2 = 2/5 のとき、
最小値をとる
f(1/5, 2/5) = 1
これは (P) の最適解
π1
1 – 2π1 + π2
+ 2π2
1 +π1 – 3π2 = 0
2/5
1 + 2π1 – π2
π1
2 – π1 – 2π2
1/5
1 – 3π1 – π2 = 0
ラグランジュ緩和定理 c の確認
1 + 2π1 – π2
～ 0.8
π=
0.2
～
fは x=
～
=
1
2
=
2
-1
h :=
～
～
とすると、h は f のπでの劣勾配となる。
0
1
で最小値をとる
～
h :=
～
～
π∈ C、x ～
が (L(π)) の最適解、
～
h ∈ Rmを、
～
～
のとき、
–
3 -1 0
1 3 1
0.7 双対シンプレックス法
• 直接シンプレックス法を使うより、双対問題に対し、
シンプレックス法を使うほうが簡単なことが
あるという話。
• 1ページしかないので省略。
0.8 完全単模行列とグラフ
• ある種の組み合わせ最適化問題はLPで簡単に解ける
準備
単模行列 : det(A) = ±1 を満たす正方行列 A
完全単模行列 : 任意の部分正方行列の行列式が 0, 1, -1 の
いずれかになる行列
（正方でなくてもよい）
次ページに例
有向グラフの行列表現
単模行列 : det(A) = ±1 を満たす正方行列 A
完全単模行列 : 任意の部分正方行列の行列式が 0, 1, -1 の
いずれかになる行列
頂点・枝接続行列
e2
v2
e4
e5
e1 e2 e3 e4 e5 e6
v3
v1 e
1
e3
v5
e6
v4
v1
v2
v3
v4
v5
1
1
0
0
0
0
0 -1
0
1
1
0
0 -1
0
0
0
0
0
1
0 -1
1
0
0
0 -1
-1
0 -1
枝の始点に 1 、終点に -1
縦には 1 と -1 がひとつずつ並ぶ（他は0）
頂点・枝接続行列は完全単模行列である。
完全単模行列 : 任意の部分正方行列の行列式が 0, 1, -1 のいずれかになる行列
頂点・枝接続行列は完全単模行列
定理
頂点・枝接続行列は完全単模行列である。
部分正方行列のサイズ n についての帰納法
証明
頂点・枝接続行列
e1 e2 e3 e4 e5 e6
v1
v2
v3
v4
v5
1
1
0
0
0
0
0 -1
0
1
1
0
0 -1
0
0
0
0
0
1
0 -1
1
0
0
0 -1
-1
0 -1
n = 1 のときは明らか
ある行（列）のすべてが 0 なら det(B) = 0
ある行（列）に非0 が 1 個、残りが 0 のとき
行列式の展開、帰納法
それ以外のとき
すべての行、列に非0 が 2 つある
足し算で要素を１つ消す
詳細は省略
完全単模行列は何が嬉しいか？
• 定理 Ax ≦ b で表される多面体を P’ とする。
A が完全単模行列で、b の成分がすべて整数なら、
P’ のすべての extreme point （の成分）は整数である。
組み合わせ最適化問題
extreme point
整数計画法に定式化
完全単模行列になった！
整数条件を抜いた問題（線形計画法）を解く
それが元の問題の解になる
（厳密でない）証明
Ax ≦ b
1 0
-1 -1
1 1
0 -1
x
y
≦
2
3
-1
4
完全単模行列
x* を extreme point とする。
extreme point は 0 次の facet なので、
制約条件から適切に n 本とってきて、
x1*
x2*
1 0
-1 -1
extreme point
完全単模行列
改めて、これを
det (Ai) =
2
3
等号
が成り立つ。
i 列目
a11
b1
a1n
a21 ... b2 ... a2n
...
...
...
an1
bn
ann
=
A x* = b
クラメルの公式より、
xi* =
det (Ai)
とかく
整数
= 整数
det (A)
±1
定理の逆
• 定理 Ax ≦ b で表される多面体を P’ とする。
すべての整数ベクトル b について、
P’ のすべての extreme point （の成分）が整数なら、
A は完全単模行列である。
証明は略
：
Konig の定理
• 定理 G を2部グラフとする。G の最大マッチングの
枝数と、最小頂点被覆の数は等しい。
2 部グラフ
マッチング
最大マッチングは 2
頂点被覆
任意の枝は黄色の点に接続
最小頂点被覆は 2
定理
G の最大マッチングの枝数と、最小頂点被覆の数は等しい。
：
Konig の定理の証明
証明
最大マッチングを求める問題を整数計画法で定式化する。
x1
x2
x5
x3
x4
x1 + s1 = 1
x2 + x3 + x4 + s2 = 1
x5 + s3 = 1
x1 + x5 + s4 = 1
...
係数行列は完全単模である。
整数計画→線形計画に緩和してよい
定理
G の最大マッチングの枝数と、最小頂点被覆の数は等しい。
：
Konig の定理の証明
y4
y1
y5
y2
y6
y3
y1 + y4 ≧ 1
y2 + y5 ≧ 1
...
y7
双対をとる
これは、最小頂点被覆の
定式化になっている。
Hall の定理
• 定理 G を2部グラフ、各部の頂点集合を V1(G)、
V2(G) とする。
G は V1(G) をすべて含むマッチングをもつ
すべての W ⊂ V1(G) について、 | N(W) | ≧ |W|
N(W) は W から出る枝のもう一方の頂点
証明は略
連続1行列
• 連続1行列
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
• 定理
0
0
0
0
1
1
1
1
1
1
列が 000...0111...1000...0 と並ぶ行列
1
1
1
1
1
1
1
0
0
0
連続1行列は完全単模行列である。
証明部分正方行列の次数に関する帰納法で証明すればよい（略）
応用例
• シフト計画
シフト種類
シフトに入る人数
その時刻に必要なシフト人数
A B C D
1
2
3
4
5
時刻 6
7
8
9
10
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
x1
x2
x3
x4
≧
2
3
7
5
4
1
7
4
6
4
min c1x1 + c2x2 + c3 x3 + c4 x4
シフト種類の単価
連続1行列
0.9 Further Study
• 省略

Download Report