最長片道きっぷの経路を求める
[2-1] 整数計画法で(準備編)

あらまし

 LOP の最適解を求める手段として整数計画法を使うことを考えます。LOP を整数計画法の問題に置き換えることができれば、 あとはソルバーというソフトウェアが機械的に解いてくれるので、 問題をいかに整数計画法に帰着するか、 ということを考えればよいことになります。
 このページでは、整数計画法と、グラフ理論のごくかんたんな用語(頂点、 枝など)について、まったく知らない人を対象にかんたんな説明をしています。 整数計画法やグラフ理論を知っている人は読み飛ばしてかまいません。


目次

  1. 問題の分析
  2. 整数計画法で
  3. 全探索で
  4. これが最長ルートだ!
  5. よくある質問と答え
  6. その他

整数計画法って?

 整数計画法、整数計画問題になじみのない人のために、 専門家に怒られない程度のかんたんな解説を最初にしておきます。

線形計画問題

 大学入試か何かで、以下のような数学の問題を見たことがないでしょうか?

という4つの条件を満たしながら x + y を最大にするには、 x と y をそれぞれ何にしたらいいか。

 この問題を解くには、与えられた4つの不等式をともに満たすような (x, y) の領域をグラフに図示し、直線 x + y = k(すなわち y = −x + k)がその領域と共有点を持つようになるまで k の値を減らしていけばいいんですよね(図10)。

図10図10 k を小さくしていくと直線 x + y = k は左下へ動き、 出っ張った点 (2, 0.5) で初めて斜線部に接触します。

 実際にそうやって解いてみると、 k = 2.5 のときに直線と領域ははじめて共有点を持つので、 x + y のとり得る最大値は2.5。その共有点の座標は (2, 0.5) であることがグラフから分かり、答えは x = 2、y = 0.5となります。

 気のきいた問題集なら、この問題には「線形計画」 なんてコメントがついていることでしょう。 そのとおり、線形計画問題とは、まさにこういった問題のことをさします。 「線形」とは、かんたんにいえば「1次式」のことです。
 この問題では変数は x と y の2つでしたが、変数はいくつあってもかまいません。 また、満たすべき等式や不等式(制約式といいます) がいくつあってもかまいません。 この問題では関数 x + y(目的関数といいます) を最大化したかったのですが、目的関数を最小化するような問題でもかまいません。 制約式と目的関数がすべて線形であれば、すなわち1次式で表されるなら、 それは線形計画問題です。
 線形計画問題については、うまく解く方法や応用法など、 いろいろと研究が進んでいます。ある問題を線形計画問題に帰着したり、 線形計画問題の解を求めたりといった、 線形計画問題に関連した問題の解法は線形計画法と呼ばれています。

 ちなみに、 得られる最大値(この場合2.5)のことを最適値、 目的関数が最適値をとるときの変数の値(この場合は (x, y) = (2, 0.5) の1組だけだが、 場合によっては複数ある)のことを最適解と呼びます。

 例題のように2変数、制約式4本という規模の小ささならともかく、 実用として線形計画問題を解くときには、 この問題のようにグラフを描いて解くことはほとんどありません (だいたい n 次元空間のグラフなんて描けない!)。
 ただ、グラフを用いた解法から得られる重要な発想、 すなわち「最適解は、制約式を満たす領域の端点しかあり得ない」 ということは実用的な線形計画問題の解法にも生きています。 前述の例題を見ても分かりますが、動かしていく直線の傾きがどうであれ、 まず最初に直線と領域が共有点を持つのは、領域の端点、 すなわち (2, 0.5) や (0, 0) などの「とがった点」ですよね。 制約式を満たす領域がどんなに広くても、 このような端点だけを見ればよいというのが、 線形計画問題がサイズのわりにすばやく解ける大きな理由です。

整数計画問題

 そして、LOP を解くのに用いようとしている整数計画法は、 前述の線形計画法の「整数計画問題」版で、線形計画法をうまく利用しています。 ここでいう整数計画問題とは、線形計画問題に「変数は整数値しかとらない」 という制約(整数制約)を加えたもののことをさします。
 たとえば、さっきの線形計画問題の最適解は (x, y) = (2, 0.5) のときでしたが、もし x と y が人数を表す変数だったとしたら、 この解は使えませんよね。「x と y は整数」という制約も加えなくてはなりません。 線形計画問題に、こういった整数制約を加えたものが整数計画問題です。

 整数計画問題と、それから整数制約のみを取り除いた線形計画問題では、 問題の難度がかなり異なります。整数計画問題のほうがはるかに難しいのです。 線形計画なら、制約式を満たす領域の端点だけをあたればいいのですが、 整数計画だとそうもいかず、組合せの問題にありがちな、 いろいろな値をあてはめる「トライ&エラー」をたくさんやることになります。
 が、整数計画法はただやみくもに変数に値をあてはめるのではなく、 対応する線形計画問題をうまく用いて、見込みのない領域を見極め、 探索する範囲を狭めていきます。 そのため、単純に値をあてはめるのとは比較にならないほど速く解けます。 それでも、前述のとおり、単なる線形計画問題よりはずっと難しいのです。

手計算? ノンノン!

 整数計画問題は線形計画問題よりずっと難しいらしい。 じゃあ、整数計画問題って常人には解けないんじゃないの?  とりあえずオレは計算が苦手だから一抜けた、っと…
 いや、そうじゃないんです。実は、線形計画問題や整数計画問題は、 ある程度までの規模ならコンピュータで解くことができます。 しかも、数式を理解してくれる専用のソフトウェアが存在するので、 自分でプログラムを書く必要もありません。 制約式や目的関数をそのまま与えれば、あとは「全自動」です。
 ですから、実際問題として大変なのは、整数計画問題を解くことではなく、 整数計画問題を作ること、 つまり解きたい問題を整数計画問題に直すことなのです。 もし、解きたい問題を適当な規模の整数計画問題にきちんと直すことができたら、 もう問題は解けたも同然です。


ちょこっとグラフ

 この先のページでは、JRの路線図を「グラフ」に見立てています。 ここでいうグラフとは、棒グラフや折れ線グラフ、 あるいはさっき出てきた x 軸と y 軸のあるグラフとはちょっとちがいます。 じゃあどんなものだ、 と言われると「路線図みたいなもの」と説明するしかないのですが、 とりあえず数学には「グラフ理論」という分野があって、 以下ではこの分野の用語をいくつか使うので、 ここではごくかんたんに説明しておきます。

頂点、枝、連結

 グラフは、いくつかの頂点と、 その頂点間を結ぶから成っています。 「頂点=駅」「枝=線路」だと思うと、グラフは路線図そのものです(図11)。

図11図11 黒丸が頂点、黒丸と黒丸を結ぶ線が枝です。 枝は曲線でも折れ線でもかまいません。 また、実際に平面上に描ける必要はなく、立体交差があってもかまいません。

 グラフのうち、 枝をたどることで任意の2頂点間を移動できるようなものを連結なグラフと呼びます(図12)。 たとえばJR6社の鉄道の路線図は連結ですが、 西武鉄道の路線図は連結なグラフではありません(多摩川線が孤立している)。

図12図12 このように、 任意の2頂点間を枝づたいに移動できないグラフは連結ではありません。

 専門家に怒られそうですが、この節の内容は以上です。



(c) SWA / KASAI TakayaSWA へメールを送る
最終更新: 2000年10月 9日
簡易包装にご協力ください。