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次元 3次元 幾何学的な直感と一致 n 次元の多面体 P が n 次元空間にあるとき、 P を full dimensional という。

方程式の独立性 m 本の方程式 が線形独立であるとは、m 個の点 が 線形独立であることと定義する。 a11x1 + a12x2 + … + a1nxn = b1 ... am1x1 + am2x2 + … + amnxn = bn a11 a12 ... a1n b1 a21 a22 ... a2n b2 am1 am2 ... amn bm … 線形独立でない 線形独立である 2x + 3y = 4 4x + 6y = 8 x + 2y = 3 x – y = 4

次元定理 定理 n 次元空間にある多面体 P について、 dim(P) = n – e e は「P に属するすべての点が満たす線形独立な 方程式の個数の最大値」 例：2 次元（平面）上にある線分 P 例：2 次元上にある点 P 2x – 4y ≦ 3 2x – 4y = 3 点も多面体とみなす P P x + 2y ≧ 5 3x – 2y = 4 3x – 2y = 4 方程式の本数は 2 本なので、 dim(P) = 2 – 2 = 0 方程式の本数は 1 本なので、dim(P) = 2 – 1 = 1

次元定理の証明 X を P の頂点集合とする。 x1 x2 x3 1 y1 y2 y3 1 z1 z2 z3 1 G = dim(P) = n – e e は方程式の本数 次元定理の証明 X を P の頂点集合とする。 正確には P = conv(X) y X = {x, y, z, w} z x 行列を作る x1 x2 x3 1 y1 y2 y3 1 z1 z2 z3 1 w1 w2 w3 1 w G =

次元定理の証明 X を P の頂点集合とする。 dim(P) = rank(G) － 1 x1 x2 x3 1 y1 y2 y3 1 dim(P) = n – e e は方程式の本数 次元定理の証明 X を P の頂点集合とする。 正確には P = conv(X) y X = {x, y, z, w} P の定義より z x 行列を作る dim(P) = rank(G) － 1 x1 x2 x3 1 y1 y2 y3 1 z1 z2 z3 1 w1 w2 w3 1 w (x1, x2, x3) と (y1, y2, y3) が アフィン独立 ⇔　(x1, x2, x3, 1) と (y1, y2, y3, 1) が 線形独立 G = dim(P) はアフィン独立な点の個数 マイナス1 rank(G) は線形独立な行ベクトルの本数

次元定理の証明 X を P の頂点集合とする。 dim(P) = rank(G) － 1 x1 x2 x3 1 y1 y2 y3 1 dim(P) = n – e e は方程式の本数 次元定理の証明 X を P の頂点集合とする。 正確には P = conv(X) y X = {x, y, z, w} P の定義より z x 行列を作る dim(P) = rank(G) － 1 線形代数の rank-nullity 定理（次元定理）より x1 x2 x3 1 y1 y2 y3 1 z1 z2 z3 1 w1 w2 w3 1 w dim(Ker(G)) + rank(G) = n + 1 G = （G の列は n + 1 個なので） 2 式から dim(P) = n – dim(Ker(G)) α1 α2 α3 β α1 α2 α3 β ～ ～ ～ α1x1 + α2x2 + α3x3 + β’ = 0 ∈ Ker(G) なら G = 0 より、 Ker(G) の次元 = 線形独立な方程式の本数 e となる

次元定理の証明 X を P の頂点集合とする。 2t x1 + 3t x2 + 4t x3 + 5t = 0 ～ α1x1 + α2x2 + α3x3 + β = 0 x = λ1x + λ2y + λ3z + λ4w dim(P) = n – e e は方程式の本数 α1y1 + α2y2 + α3y3 + β = 0 次元定理の証明 λ1 + λ2 + λ3 + λ4 = 1 α1z1 + α2z2 + α3z3 + β = 0 α1w1 + α2w2 + α3w3 + β = 0 ～ 2t 3t 4t 5t なので、任意の x ∈P について α1x1 + α2x2 + α3x3 + β’ = 0 X を P の頂点集合とする。 ～ ～ ～ t は実数 Ker(G) = y X = {x, y, z, w} z の例で考えてみると、 x 行列を作る 2t x1 + 3t x2 + 4t x3 + 5t = 0 ⇔ 2 x1 + 3 x2 + 4 x3 + 5 = 0 x1 x2 x3 1 y1 y2 y3 1 z1 z2 z3 1 w1 w2 w3 1 w Ker(G) からは独立な方程式は１本しか作れない G = 2 式から dim(P) = n – dim(Ker(G)) α1 α2 α3 β α1 α2 α3 β ～ ～ ～ α1x1 + α2x2 + α3x3 + β’ = 0 ∈ Ker(G) なら G = 0 より、 Ker(G) の次元 = 線形独立な方程式の本数 e となる

face （フェイス） と facet （ファセット） 　　　　　　　　が多面体 P に対し有効であるとは、 P に属するすべての点がこの不等式を満たすこと。 有効な不等式は face を描く。 例：2 次元（平面）上にある多角形 P 2x – 4y ≦ 3 6x – 3y ≦2 face (extreme point) 有効な不等式 有効な不等式 P P face 0 次元の face を extreme point、 (facet) dim(P) – 1 次元の face を facet と呼ぶ

face を表す式 2x – 4y ≦ 3 2x – 4y ≦ 3 2x – 4y = 3 P : 3x + 4y ≦ 5 F : 有効な不等式 x + 2y ≦ 3 x + 2y ≦ 3 P 3x + 4y ≦ 5 face (facet) x + 2y ≦ 3

ミンコフスキーの定理 定理 かつ、P が有界のとき、P は多面体である。 証明 X を P の extreme point の集合とする。明らかに conv(X) ⊂ P である。 ～ となる x が存在すると仮定して 矛盾を示す。 P conv(X)

ミンコフスキーの定理の証明 X = { x1, x2, x3 } y = λx1 x1 + λx2 x2 + λx3 x3 X は extreme point の集合 ミンコフスキーの定理の証明 x2 y conv(X) X = { x1, x2, x3 } x1 なので、 x3 成分にわけてかくと conv(X) の中の点は y = λx1 x1 + λx2 x2 + λx3 x3 λx1 + λx2 + λx3 = 1 とかける を満たすような λx は存在しない。 を満たすような λx は存在しない。

ミンコフスキーの定理の証明 (I) (II) X は extreme point の集合 Farkas の定理 を満たす t 、c は存在する。

ミンコフスキーの定理の証明 X は extreme point の集合 ≧ －t x は P <－t x ≧ －t ≧ －t ～ ≧ －t x は P ～ <－t x ≧ －t ≧ －t を満たすような λx は存在しない。 Farkas の定理より、 の実行可能解で、値は －t 未満となるが、 すべての extreme point での値は －t 以上 となるので、矛盾。 を満たす t 、c は存在する。

余分な不等式の定理 定理 P の dim(P) – 1 次元未満の face を描く 有効な不等式は余分である。 6x – 3y ≦2 2x – 4y ≦ 3 face 余分である 余分ではない 0 次元 P P face 1 次元 jump 20

余分な不等式の定理の証明 定理 P の dim(P) – 1 次元未満の face を描く有効な不等式は余分である。 P を表す式を 線形独立 とすると、 とする。 を満たす　 　が存在する。 が成り立つ。 次元定理より、dim(P) = n – k である。

定理の証明の続き 一般性を失うことなく、face F を描く不等式を x と x1 を結んだ線分上に x2 が存在。 とする。 が成り立つ。 定理　　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 を表すのに必要 定理の証明 線形独立

ファセットの一意性 定理 （Unique Description Theorem） Ｐ ⊂ 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 0.6 ラグランジュ緩和 f を Rm → R なる凸関数とする。 ～ ～ が成り立つとき、h ∈ Rm を f の π における劣勾配とよぶ。 f ～ 傾き h f がπで微分可能なら 劣勾配は一意に定まる （勾配と同じ） ～ π π

0.6 ラグランジュ緩和 f を Rm → R なる凸関数とする。 が成り立つとき、h ∈ Rm を f の π における劣勾配とよぶ。 f 0.6 ラグランジュ緩和 f を Rm → R なる凸関数とする。 ～ ～ が成り立つとき、h ∈ Rm を f の π における劣勾配とよぶ。 f ～ 傾き h 微分不可能なとき、 劣勾配は複数の値をとりうる ～ π π

劣勾配法 凸関数 f の最小化を考える 劣勾配法 k := 0 にし、π0 ∈Rm を選ぶ。 πk での劣勾配 hk を計算する（1つ選ぶ） πk+1 := πk – λk hk 終了条件（hk = 0）を満たさないならステップ2へ ～ ～ ～ ～ ～ ～ ～ f ステップサイズλk の選び方は いろいろある λ1 h1 ～ λ0 h0 ～ ～ ～ ～ π2 π1 π0 π

凸関数 f の最小化 劣勾配法 k := 0 にし、π0 ∈Rm を選ぶ。 πk での劣勾配 hk を計算する（1つ選ぶ） πk+1 := πk – λk hk 終了条件（hk = 0）を満たさないならステップ2へ ～ ～ ～ ～ ～ ～ ～ 勾配ベクトルの 逆向き λ1 h1 ～ λ0 h0 ～ ～ π0 ～ ～ π2 π1

ラグランジュ緩和 subject to subject to (P) (P’) for i = 1,2,...,m x ∈ P x ∈ P P と P’ の最適解は同じである。

ラグランジュ緩和 subject to subject to subject to (P) (P’) for i = 1,2,...,m x ∈ P x ∈ P P と P’ の最適解は同じである。 (P’’) subject to P’’ を P のラグランジュ緩和という x ∈ P P の最適解 ≦ P’’ の最適解

ラグランジュ緩和 subject to subject to subject to 制約条件が不等式の場合 非負の数 (P) (P’) for i = 1,2,...,m for i = 1,2,...,m 非負の数 x ∈ P x ∈ P L(π)を P のラグランジュ緩和という (L(π)) P の最適解 ≦ L(π) の最適解 subject to 制約条件を破ったときの 罰金とみなすことができる x ∈ P

ラグランジュ緩和定理 a. 任意のπ∈C について、 (P)の最適解 ≦ (L(π)) の最適解 b. f は凸、区分的に線形。 c. π∈ C、x が (L(π)) の最適解、 h ∈ Rmを、 とすると、h は f のπでの劣勾配となる。 subject to x ∈ P C := { π∈Rm | π ≧ 0 } 等号が成立するπは存在 f ～ ～ ～ この定理からいえること f の最小値を求めれば、 (P)の最適解がわかる。 f は凸なので、劣勾配法が 使える。しかも、劣勾配は 簡単に求まる。 ～ ～ ～ h := ～

例題 P = { (x1, x2) | 0 ≦ x1, x2 ≦ 1} z = max x1 + x2 subject to ラグランジュ緩和問題 L(π1, π2) の 関数 f の最小値を求める x ∈ P L(π1, π2) f (π1, π2) = π1 + 2π2 + max { (1 – 3π1 – π2) x1 + (1 + π1 – 3 π2) x2 } subject to x ∈ P

+ max { (1 – 3π1 – π2) x1 + (1 + π1 – 3 π2) x2 } 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 が最大になる したがって、 1 – 3π1 – π2 ≧ 0 かつ 1 +π1 – 3π2 ≧ 0 のとき、 f (π1, π2) = 2 – π1 – 2π2 π2 π1 + 2π2 残り3通りも同様に計算をする 1 – 2π1 + π2 1 +π1 – 3π2 = 0 2/5 1 + 2π1 – π2 2 – π1 – 2π2 π1 1/5 1 – 3π1 – π2 = 0

+ max { (1 – 3π1 – π2) x1 + (1 + π1 – 3 π2) x2 } 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 + 2π2 π1 1 – 2π1 + π2 1 +π1 – 3π2 = 0 f はπ1 = 1/5, π2 = 2/5 のとき、 最小値をとる f(1/5, 2/5) = 1 2/5 1 + 2π1 – π2 これは (P) の最適解 2 – π1 – 2π2 π1 1/5 1 – 3π1 – π2 = 0

ラグランジュ緩和定理 c の確認 1 + 2π1 – π2 h := h := ～ 0.8 0.2 π = のとき、 ～ 1 f は x = 1 f は x = で最小値をとる ～ ～ h := ～ ～ ～ π∈ C、x が (L(π)) の最適解、 h ∈ Rmを、 とすると、h は f のπでの劣勾配となる。 ～ 1 2 3 -1 1 3 1 = – ～ ～ h := 2 -1 ～ = ～

0.7 双対シンプレックス法 直接シンプレックス法を使うより、双対問題に対し、 シンプレックス法を使うほうが簡単なことが あるという話。 0.7 双対シンプレックス法 直接シンプレックス法を使うより、双対問題に対し、 シンプレックス法を使うほうが簡単なことが あるという話。 1ページしかないので省略。

0.8 完全単模行列とグラフ ある種の組み合わせ最適化問題はLPで簡単に解ける 準備 0.8 完全単模行列とグラフ ある種の組み合わせ最適化問題はLPで簡単に解ける 準備 単模行列 :　det(A) = ±1 を満たす正方行列 A 完全単模行列 : 任意の部分正方行列の行列式が 0, 1, -1 の 　　　　　　　　　　 いずれかになる行列 次ページに例 （正方でなくてもよい）

有向グラフの行列表現 e1 e2 e3 e4 e5 e6 v1 v3 e1 v1 v2 e3 e2 v5 e4 v3 e6 v4 v2 e5 単模行列 :　det(A) = ±1 を満たす正方行列 A 完全単模行列 : 任意の部分正方行列の行列式が 0, 1, -1 の 　　　　　　　　　　 いずれかになる行列 頂点・枝 接続行列 e1 e2 e3 e4 e5 e6 v1 v3 e1 v1 1 1 0 0 0 0 v2 e3 0 -1 0 1 1 0 e2 v5 e4 v3 -1 0 -1 0 0 0 e6 v4 0 0 1 0 -1 1 v2 e5 v5 0 0 0 -1 0 -1 v4 枝の始点に 1 、終点に -1 縦には 1 と -1 がひとつずつ並ぶ（他は0） 頂点・枝 接続行列は完全単模行列である。

頂点・枝 接続行列は完全単模行列 定理 頂点・枝 接続行列は完全単模行列である。 e1 e2 e3 e4 e5 e6 v1 v2 v3 v4 完全単模行列 : 任意の部分正方行列の行列式が 0, 1, -1 のいずれかになる行列 頂点・枝 接続行列は完全単模行列 定理 頂点・枝 接続行列は完全単模行列である。 部分正方行列のサイズ n についての帰納法 証明 n = 1 のときは明らか 頂点・枝 接続行列 ある行（列）のすべてが 0 なら det(B) = 0 e1 e2 e3 e4 e5 e6 ある行（列）に非0 が 1 個、残りが 0 のとき v1 1 1 0 0 0 0 行列式の展開、帰納法 v2 0 -1 0 1 1 0 それ以外のとき 　すべての行、列に非0 が 2 つある v3 -1 0 -1 0 0 0 v4 0 0 1 0 -1 1 足し算で要素を１つ消す v5 0 0 0 -1 0 -1 詳細は省略

完全単模行列は何が嬉しいか？ 定理 Ax ≦ b で表される多面体を P’ とする。 A が完全単模行列で、b の成分がすべて整数なら、 P’ のすべての extreme point （の成分）は整数である。 組み合わせ最適化問題 整数計画法に定式化 完全単模行列になった！ extreme point 整数条件を抜いた問題（線形計画法）を解く それが元の問題の解になる

（厳密でない）証明 det (Ai) xi* = det (A) Ax ≦ b 1 0 -1 -1 1 1 0 -1 2 3 -1 4 1 0 -1 -1 1 1 0 -1 2 3 -1 4 x* を extreme point とする。 x y ≦ extreme point は 0 次の facet なので、 制約条件から適切に n 本とってきて、 完全単模行列 1 0 -1 -1 x1* x2* 2 3 = extreme point 等号 が成り立つ。 完全単模行列 改めて、これを A x* = b とかく 整数 クラメルの公式より、 i 列目 det (Ai) a11 a21 an1 b1 b2 bn a1n a2n ann xi* = = 整数 ... ... det (A) det (Ai) = ... ... ... ±1

定理の逆 定理 Ax ≦ b で表される多面体を P’ とする。 すべての整数ベクトル b について、 P’ のすべての extreme point （の成分）が整数なら、 A は完全単模行列である。 証明は略

Konig の定理 定理 G を2部グラフとする。G の最大マッチングの枝数と、最小頂点被覆の数は等しい。 ： 2 部グラフ マッチング 任意の枝は黄色の点に接続 最大マッチングは 2 最小頂点被覆は 2

Konig の定理の証明 ： 定理 G の最大マッチングの枝数と、最小頂点被覆の数は等しい。 証明 最大マッチングを求める問題を整数計画法で定式化する。 x1 x2 x3 x4 x5 x1 + s1 = 1 x2 + x3 + x4 + s2 = 1 x5 + s3 = 1 x1 + x5 + s4 = 1 ... 係数行列は完全単模である。 整数計画→線形計画に緩和してよい

Konig の定理の証明 ： 定理 G の最大マッチングの枝数と、最小頂点被覆の数は等しい。 y4 y1 y5 y2 y6 y3 y7 ... 双対をとる これは、最小頂点被覆の 定式化になっている。

Hall の定理 定理 G を2部グラフ、各部の頂点集合を V1(G)、V2(G) とする。 すべての W ⊂ V1(G) について、 | N(W) | ≧ |W| N(W) は W から出る枝のもう一方の頂点 証明は略

連続1行列 連続1行列 列が 000...0111...1000...0 と並ぶ行列 定理 連続1行列は完全単模行列である。 1 1 1 1 連続1行列　　列が 000...0111...1000...0 と並ぶ行列 定理　　連続1行列は完全単模行列である。 1 1 1 1 証明　部分正方行列の次数に関する帰納法で証明すればよい（略）

応用例 シフト計画 シフトに入る人数 シフト種類 その時刻に必要なシフト人数 A B C D 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 2 3 7 5 4 1 6 x1 x2 x3 x4 ≧ 時刻 min c1x1 + c2x2 + c3 x3 + c4 x4 シフト種類の単価 連続1行列

0.9 Further Study 省略