トップ 差分 一覧 ソース 検索 ヘルプ PDF RSS ログイン

NHC秋学校 Integer Programming の講義の復習2

整凸包の端点の個数

この章では、整凸包の端点の個数について考察する。前の章で述べたとおり、端点の場所がすべてわかれば、その整凸包を制約条件とする整数計画法の最適解が求まる。

端点の定義

後で必要になるので、端点の正確な定義を述べておく。直感的には明らかだが、きちんと定義しようとすると難しくなる。

多面体 P に属する点 y ∈ P が以下の条件を満たすとき、y を端点という。

以下のような不等式 ax <= b が存在する。
すべての x ∈ P について、ax <= b を満たし、かつ、
ax = b を満たす x ∈ P は y だけである。

この条件を図で表せば以下のようになる。点 y に対し、赤色のような直線(ax = b)が引ければ、y は端点である(左図)。端点でなければ、どんなにがんばってもそのような直線は引けない(右図)。

図の右上は、すべての x ∈ P について、ax <= b を満たしているが、ax = b を満たす x ∈ P は y' だけではない。右下は、ax <= b を満たさないx ∈ P が存在する。y' に対し、どのように線を引いても、2つのどちらかの状況になるので、y'は端点ではない。

ナップザック多面体の端点の個数

(Eisenbrand 先生のスライドの8,9ページ参照)

不等式

a_1 x_1 + a_2 x_2 + ... + a_n x_n <= b
x_i >= 0   for i = 1,2,...,n

を満たすような領域 P を考える。この領域の整凸包 P_I をナップザック多面体(polyhedron)と呼ぶ(上で見たように、ナップザック問題を定式化したときに表れる制約条件から作られる多面体なのでこう呼ばれる)。なぜ突然このようなものが出てきたかというと、いきなり一般の多面体について考えるのは難しいので、まずは、式で表したときに最も単純になるものを考えようということである。

この領域での端点の個数を見積もろう。2次元の場合で、端点の個数が多い例を作ってみようとすればわかるが、端点の個数が多くなるように線を引くのは難しい。直線1本だけで平面を複雑な形に切り、端点がたくさんできるようにするのは不可能そうなのはすぐにわかる。

特に、端点が近くに密集しているようなナップザック多面体の例を作ることはどうがんばっても無理そうである。

近く同士の2点が両方同時に P_I の端点とはならないことを示そう。例えば、上図の x,y は両方同時に P_I の端点となることはない。線分 xy を伸ばすと、下図のピンク色の点 z を通るので、x, z が端点になる(かもしれない)からである。「かもしれない」と書いたのは、実際には整凸包の面はもっと外側になるかもしれないからである。少なくとも、x, y は端点にはならない。

(ここで、z = 2y - x になっていることに気づけば、スライドの証明の意味が少し見えてくるだろう)。

「近く同士」といったが、これを厳密に定義しよう。ここでは、「各成分の2進数での桁数が等しい」2点を「近い」と定義する。

例えば、上の例で x = (4, 2) と y = (5, 3) は2進数で (100, 10) と (101, 11) であり、各成分の桁数が等しいので、x と y は近いといえる。

これを式で表したのが

\lfloor~log~~x_i~\rfloor~=~\lfloor~log~~y_i~\rfloor for i = 1,2,...,n (1)

である。改めて補題の形で述べよう。

補題

a_1 x_1 + a_2 x_2 + ... + a_n x_n <= b (2)
x_i >= 0   for i = 1,2,...,n
が作る領域を P、P の整凸包を P_I とする。
上の意味での「近い」2点 x, y の両方が同時に P_I の端点になることはない。

証明

スライドでは代数的に証明されているので、ここでは、幾何学的イメージだけ述べる。

x, y は P_I の端点と仮定する。

w = 2x - y、z = 2y - x とおく(上図参照)。

x, y は (1) を満たすので、w >= 0 (すなわち、各成分が 0 以上)、z >= 0 である。

4 点 w, x, y, z はこの順に1直線上に並ぶ(高校数学のベクトル演算レベル)。x, y はともに制約条件 (2) を満たすので、w, z の少なくとも一方は制約条件 (2) を満たす。ここでは z が満たすとしよう(w でも同じ議論)。

x, y の代わりに、z, y を端点にとれるので、x は端点として不要(この部分はもう少し詳しく述べる予定。工事中)。これは矛盾。(Q.E.D.)

例えば、点 (1024, 1024) が端点なら、(x_1, x_2), 1024 <= x_1 < 2047, 1024 <= x_2 < 2047 には端点が存在し得ない。

正直、私は最初に秋学校で講義を聞いたときこの部分でつまづいてしまった。x が vertex で矛盾というところの意味が分からなかったのである(単に英語のリスニング力がないせいかもしれないけど)。こんなところでつまづくのは私だけかと思っていたが、どうやらそうではないようだ。復習してみると、意外と難しい内容を含んでいることがわかった。

この補題から、以下の定理がいえる。

定理(工事中)

…の式で表される領域 P の整凸包の端点の個数は高々 O(\varphi^n) 個である。ここで、\varphi は…である。

単体が作る整凸包

(スライド10ページ)

ナップザック多面体は、2次元なら直角三角形の整凸包である。今度は少し一般化して、直角とは限らない三角形の整凸包を考えよう。2次元なら三角形、3次元なら四面体、これを一般の次元に拡張した図形を単体という。

もう少し詳しく言うと、単体とは、2次元の場合は3本の1次式(直線)に囲まれた図形のことである。正確に言うと、3本の一次不等式

a_11 x_1 + a_12 x_2 <= b_1
a_21 x_1 + a_22 x_2 <= b_2
a_31 x_1 + a_32 x_2 <= b_3

を満たす領域である。3次元の場合は4本の1次式(平面)、n 次元の場合は n + 1 本の1次式に囲まれた図形である。

この節では、単体の整凸包(の端点の個数)について考える。

例として、2次元の単体を考える。以降、2つの変数を x, y と表すのは止めて、x_1, x_2 と表すことにする。

2 x_1 - x_2 >= 0
-x_1 + 3 x_2 >= 0          (3)
10 x_1 + 12 x_2 <= 79

で表される領域 P は単体である。

P の整凸包 P_I の端点の個数を見積もりたい。アイデアは、上で述べたナップザック多面体の場合に帰着することである。そのために、領域 P を一次変換する。P を一次変換した図形を Q とする。

上図のような一次変換は簡単に求まる。そのために、(3) 式を行列で表す。

\(\array{\\2\qquad~-1\\-1\qquad~3}\)~\(\array{\\x_1\\x_2}\)~\ge~\(\array{\\0\\0}\) (4)

(10\qquad~12)~\(\array{\\x_1\\x_2}\)~\le~79

ここで、

B~=~\(\array{\\2\qquad~-1\\-1\qquad~3}\),x~=~\(\array{\\x_1\\x_2}\),\alpha~=~\(\array{\\10\\12}\),\beta~=~79

とすると、

Bx~\ge~0, \alpha^T~x~\le~\beta (5)

と表せる。この B を用いて作った一次変換

y = Bx

は、上図のようになっている(青と水色の矢印が直角になるように移される)。理由は簡単で、(5)式を変数 y で書き直すと、

y~\ge~0, \alpha^T~B^{-1}~y~\le~\beta

となるからである(後者の式は x~=~B^{-1}~y を用いた)。

具体的な値で計算すると、

y~\ge~0, \frac{42}{5}y_1~+~\frac{34}{5}y_2~\le~78

である。

さて、この一次変換によって、P の整凸包 P_I がどのように移るかを考えてみよう。

元の空間の整数点が一次変換 y = Bx によって、どのような点に移されるかを考える。

(x_1, x_2) = (0, 0) は (y_1, y_2) = (0, 0) へ、
(x_1, x_2) = (1, 0) は (y_1, y_2) = (2, -1) へ、
(x_1, x_2) = (2, 0) は (y_1, y_2) = (4, -2) へ、
(x_1, x_2) = (0, 1) は (y_1, y_2) = (-1, 3) へ、
(x_1, x_2) = (0, 2) は (y_1, y_2) = (-2, 6) へ、

移される。移された点は斜めに並ぶ。このような点を格子点と呼ぶことにする(格子点の集合の正確な定義は {y | y = Bx, x は整数点} である。この集合を \Lambda(B) と表すらしい)。

P の整凸包は、Q(P を一次変換したもの)の、「格子凸包」に移される。格子凸包は Q に含まれるすべての格子点が作る凸包である。このことは直感的には明らかであろう。厳密な証明は省略する。

というわけで、単体の整凸包の端点の個数を見積もるには、単体を一次変換してできた直角三角形(*)の格子凸包の端点の個数を考えればよい。

(*)a_1x_1 + ... <= b, x_i >= 0 を満たす領域のこと。一般の次元ではどう呼ぶか知らないのでこのように書いた。「直角多面体」というのも変だろう。

直角三角形の格子凸包の端点の個数は、前の節で求めた、直角三角形の整凸包(ナップザック多面体)の場合を少し応用すればよい(ほとんど同じであるが)。これはスライド10ページに書かれているexercize になっているので、答えはここには書かない。

以上より、以下の定理が得られる。

定理(工事中)

…の式で表される領域 P の整凸包の端点の個数は高々 O(\varphi^n) 個である。ここで、\varphi は…である。

一般の多面体の場合

(スライド11,12ページ)

Ax <= b が表す領域(で有界なもの)は一般には多面体となる。多面体の整凸包の端点の個数を評価するには、多面体を単体に分割すればよい。2次元なら多角形を三角形に分割すればよい。

分割の個数などを議論する必要があるが、工事中

定理(工事中)

Ax <= b の式で表される領域 P の整凸包の端点の個数は高々 O(m^n~\varphi^n) 個である。ここで、m は制約条件の数、\varphi は…である。n を固定すればこれは m, \varphi の多項式である。

NHC秋学校2007サポートページトップに戻る