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

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

イントロダクション

整数計画法とは

そもそも、Integer Programming (整数計画法)についてほとんど何も知らないので、この講義で紹介されているアルゴリズムがどのくらい有難いものなのか、その有用性が実感できにくい。

さすがに、Linear Programming(線形計画法)の知識はあると仮定しよう。そうでなければ話が進まない。

線形計画法は、変数 (x_1, x_2,...,x_n) が制約条件

a_11 x_1 + a_12 x_2 + ... + a_1n x_n <= b_1
a_21 x_1 + a_22 x_2 + ... + a_2n x_n <= b_2
...
a_m1 x_1 + a_m2 x_2 + ... + a_mn x_n <= b_n

を満たすとき、

c_1 x_1 + c_2 c_2 + ... + c_n x_n

の値を最大にするような (x_1, x_2,...,x_n) の組と、その最大値を求めよ、という問題であった。a_11 や b_1、c_1 などは(与えられた)定数である。

整数計画法は、制約条件として

「x_1, x_2,...,x_n はすべて整数である」

を加えたものである(正確には線形整数計画法と呼ばれる)。

重要なのは、線形計画法は変数の数 n に対して多項式時間で解け、整数計画法は、(P != NP を仮定する限り*)多項式時間では解けないということである。「変数が整数でなければならない」という条件を付けるだけで、問題は飛躍的に難しくなる。

(*)以下では、P != NP の仮定はいちいち断らない。

具体例

2次元の場合(n = 2)を考えてみよう。x_1 を x、x_2 を y と書くことにする。制約条件

x~+~2y~\le~7

2x~+~y~\le~9

x~\ge~0

y~\ge~0

x, y は整数

の元で、2x + 2y を最大化する問題を考える。4つの不等式は xy 平面上に図示できる(下図の黄色の領域)。

この領域を P と表すことにする。

4つの不等式は、以下のように行列の形で表すと便利である。

\(\array{\\1\qquad~2\\2\qquad~1\\-1\qquad~0\\0\qquad~-1}\)~\(\array{\\x\\y}\)~\le~\(\array{\\7\\9\\0\\0}\)

この式の不等号は、各成分について '<=' が成り立つことを意味する。

不等式の領域内にあるすべての格子点(整数の点)による凸包(すべての格子点を含む最小の多角形で凸なもの)を整凸包(integer hull)と呼び、P_I で表す(下図の赤で囲まれた領域)。P_I の「かど」を端点(extreme point または単に vertex)と呼ぶ(下図の水色の点)。

(Eisenbrand 先生のスライドの絵がいまいちよく分かりません。なぜ格子点がずれて並んでいるのでしょうか? 追記:foxit Reader という adobe 純正でないリーダだとおかしくなるようです。)

整数計画法の最適な解

2x + 2y の最大値(一般に c_1 x + c_2 y の最大値)をとる (x, y) は、integer hull の「かど」に存在する。

上の例では、(x, y) = (2, 2) や (3, 1) で最大値をとることはありえない。

証明は難しくない(自明?)ので、練習問題としておこう。

したがって、P_I のすべての「かど」を調べれば、最大値が求まる。この辺りは線形計画法と雰囲気が似ている。しかし、大きく異なるのは、この「かど」を求めるのが容易ではないということである。

おまけ 整数計画法が多項式時間で解けない理由

整数計画法が多項式時間では解けないのは、ナップザック問題(代表的な NP 完全問題)が整数計画法で表せることから分かる(厳密な証明は教科書参照)。

ナップザック問題は、n 種類のアイテムを、重さ制限のある袋にどれだけ詰め込めるかを考える問題である。i 種類目のアイテムには重さ a_i、価値 c_i がつけられており、重さの制限内で価値を最大にするのが目標である。i 種類目のアイテムを袋に入れる個数を x_i とすると、

a_1 x_1 + a_2 x_2 + ... + a_n x_n <= (袋の重さ制限)
x_i >= 0   for i = 1,2,...,n

が成り立つのは容易に分かる。この条件の下で、

c_1 x_1 + c_2 c_2 + ... + c_n x_n

を最大にすればよい。これは上で見た整数計画法であり、ナップザック問題が整数計画法で定式化できることが分かった。もし、整数計画法が多項式時間で解けると仮定するなら、上記の定式化によってナップザック問題も多項式時間で解ける。実際はナップザック問題は多項式時間で解けない(証明は教科書参照)ので、仮定が間違っていることになり、整数計画法は多項式時間で解けない。

講義のゴール

整数計画法の入門コースでは、この後、切除平面法や分枝限定法など、整数計画問題を解くためのアルゴリズムを解説するはずだが、Eisenbrand 先生の講義ではそんな言葉は一切出てこない。それどころか、たぶん講義の内容は、Eisenbrand 先生本人が 2005 年に出した論文の紹介である。ということは、それは最先端の研究であり、いきなりそれを理解するのは無茶ではないかと思うのである。でも、NHC秋学校の主旨の一つに、特定の分野の内容を深く理解するというのがあるので、講義のレベルとしては適切なのか。

切除平面法や分枝限定法などの整数計画法の基礎は教科書を参照してください。

参考サイト(情報量は少ない):

次元を固定した整数計画法

本講義の中心テーマは、変数の個数 n (次元)を固定した場合の整数計画法である。例えば、n = 2 なら、変数は x, y とし、xy 平面上で考えればよい。平面上なら、最大値を取るような点は見つけやすく、したがって、高速に最適解を見つけるアルゴリズムの存在が期待できるというわけである。

実際、次元を固定すると「かなり速い」アルゴリズムが存在する。しかも、この講義で紹介する(Eisenbrand 先生の論文の)アルゴリズムは「最も速い」アルゴリズムである(あるパラメータの線形時間で計算できる)。

n を定数としたのだから、計算量を調べるのに n 以外の他のパラメータを考える必要がある。すぐに思いつくのは制約条件の個数(不等式の個数) m である。

同じ制約条件の個数でも計算時間が異なる可能性はあるだろうか。例えば、2つの問題を考えてみる。以下では変数を x, y (整数)であるとする。

2x + 4y <= 5
3x + 2y <= 4
x >= 0
y >= 0
201x + 405y <= 328
302x + 201y <= 428
x >= 0
y >= 0

似たような不等式であるが、明らかに後者のほうが探索範囲が広くて時間がかかりそうである。(*少し考察が足りないので加筆予定)

というわけで係数の大きさが重要なファクターになる。この論文では最も大きな係数の桁数 \varphi (と m)で計算量を測っている。

  • 岡本吉央です.こんばんは.私もコメントなど書いてよいですか? あんまり邪魔はしないつもりです. ちなみに,私の手元ではスライドの格子点がずれて並んでるようには見えません.該当スライドが何ページ目のものか教えてもらえますか? - okamoto7 (2007年10月12日 21時51分10秒)
  • こんばんは。秋学校ではお世話になりました。コメントは大歓迎です(wikiなので、本文の書き換えもできます)。間違いなどをどんどんつっこんでもらえるとありがたいです。今、スライドを別のpcで見てみたら正しく表示されていました。 - kawahara (2007年10月13日 17時00分24秒)
  • 格子点の件,了解しました. - okamoto7 (2007年10月15日 10時58分57秒)
  • どうでもいいことを書きますが,この「Eisenbrand先生本人が2005年に出した論文」ですが,会議録バージョンはISAAC2003です.そう,京都で開かれたISAACです.なので,京都はよく理解していることが期待されます.冗談ですが. - okamoto7 (2007年10月12日 22時28分01秒)
  • そうだったのですか。僕が今の研究室に入ったのは2004年なので、ISAAC2003には参加してないですね。先輩なら知っているかもしれません。 - kawahara (2007年10月13日 16時54分57秒)
  • 「2003年」というのがそんなに昔のことだとは!驚きました. - okamoto7 (2007年10月15日 10時55分10秒)
  • スライドを見ていて講義構成が分かりにくいと思ったので,私の思う講義構成を書いておきます. - okamoto7 (2007年10月15日 11時22分09秒)
  • (1)イントロ:pp. 1〜12.IPの定義,次元固定のときP_Iの端点数は入力サイズの多項式. - okamoto7 (2007年10月15日 11時22分29秒)
  • (2)固定次元IPの多項式時間アルゴリズム (講義では2次元の場合のみ証明?):pp. 13〜35.「IP=combinatorics+number theory」という図式.多面体のwidth.Khinchineのflatness theorem.三角形のwidthとshortest vectorの関係.Lenstraのアルゴリズム. - okamoto7 (2007年10月15日 11時22分48秒)
  • (3)2次元IPの線形時間アルゴリズム:pp. 36〜76.MegiddoのPrune&SearchアルゴリズムをIPに適用.私もまだ詳細追ってません.Eisenbrand&Laueのアルゴリズム (2005). - okamoto7 (2007年10月15日 11時23分11秒)
  • (4)固定次元IPの高速化:pp. 77〜117.ClarksonのアルゴリズムをIPに適用.Bell&Scarfの定理.Eisenbrandのアルゴリズム (2003) おわり - okamoto7 (2007年10月15日 11時23分31秒)
  • ありがとうございます。こうして見てみると内容が盛りだくさんですね。本当に全部消化し切れるのか… (2)でさえ理解していないので、これを目標にがんばってみます。 - kawahara (2007年10月15日 12時15分18秒)
  • ちなみに私のこの書き込みも思いついたまま書いているので、後で整理します。 - kawahara (2007年10月15日 12時20分59秒)

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