最長片道きっぷの経路を求める
[2-3] 整数計画法で(制約式編)

あらまし

 このページでは、LOP の最適解を求める問題を整数計画問題として定式化する際に、 どのような制約式を入れたらいいかをタイプ別に考えます。 変数の定義などは前ページを参照してください。
 LOP の最適解はタイプ Lee、タイプ Pe、タイプ Pn のどれかであることが分かっているため、 まずはそれぞれのタイプの中で最長の経路を1つずつ求めます。 すべてが出そろったら、各タイプの「代表」どうしを比較し、 3つのうちで最長のものを全体の解にしよう、というもくろみです。


本編の目次

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

タイプ Lee の定式化

 これまでに準備した変数などを用いて、タイプ Lee の経路の中で最長のものを見つける問題の定式化を行ってみましょう。
 目的関数は前ページの式 (2) で決まりですから、以下ではどんな制約式を入れるかを考えます。 式 (1) や、駅に対する従属変数 s の定義は暗黙のうちに制約式に含まれているとします。

終端駅を2回使う

 まず、タイプ Lee の特徴である「発着駅がともに終端駅」ということを表す制約式を書きます。
 これは単純で、以下のようになります。

Σ(すべての終端駅 i) si = 2 (3)

 i 番の頂点が終端駅なら si は0か1にしかならず、 0ならその駅は通らない、1ならその駅を通るという意味になるので、 路線図全体で終端駅の変数を合計して2であれば、 それは「いま考えている経路が通る終端駅はちょうど2つ」ということになります。

分岐駅は「1度通る」か「通らない」か

 次に、分岐駅に関して。 タイプ Lee は同じ駅を2度通らないので、これを表す制約式が必要です。
 ある分岐駅を通るか通らないかは自由で、 同じ分岐駅を2度以上通りさえしなければいいので、 以下のように書けば十分であるような気がします。

すべての分岐駅 i に対して
 si ≦ 2
(4)

 しかし、実はこれでは不完全です。 というのは、si = 1 が許されているからです。 si = 1 というのは「その駅に来るが、 そこから出ていかない」ということで、こういうことは発着駅でのみ起こります。 タイプ Lee では発着駅は終端駅と決まっているので、 分岐駅で si = 1 になっては困ります。 分岐駅では、si は0か2であってほしいのです。
 じゃあそうやって書けばいいじゃん、と思うかもしれませんが、 これがなかなか難しいのです。 整数計画問題では、制約式をすべて線形の等式や不等式(と、 「この変数は整数である」という制約) にしないと効率的に解けないからです。 直接「0または2」と宣言しようとすると「or」演算子が必要ですが、 これを使ってしまうと、ソルバーの計算スピードが極端に落ちます。 「1ではない」と宣言しようとしても同様です(「≠」演算子が原因)。

 この問題を解決するために、ちょっとトリッキーな不等式を作ることにしました。 たとえば i 番の駅が「3分岐」で、si = lp + lq + lr であるとするなら、 以下のような3本の不等式を制約式として加えるのです。

−lp + lq + lr ≧ 0 (5)
 lp − lq + lr ≧ 0 (6)
 lp + lq − lr ≧ 0 (7)

 もし lp、lq、lr のすべてが0なら、 この3つの式はすべて成り立ちます(左辺は全部0)。 もし lp、lq、lr のうち2つが1、 残り1つが0でも、3つの式はすべて成り立ちます。 しかし lp、lq、lr のうち1つが1、 残り2つが0だと、3つの式のうち1つは成り立たなくなります。 たとえば lp が1、そのほかが0だと式 (5) は成り立ちませんね。
 結果として、 この3式で「3つの枝のうち1つだけを使う」場合、 すなわち si = 1 となる場合は除去できます。 前に「不完全だ」とした (4) 式を、 分岐駅ごとに加えるこの3つの制約式と同時に使えば、 「許されるのは0と2だけ」という制約が実現します。
 4分岐以上でもだいじょうぶ。 たとえば4分岐なら、以下のようにすればいいですね。

−lp + lq + lr + ls ≧ 0 (8)
 lp − lq + lr + ls ≧ 0 (9)
 lp + lq − lr + ls ≧ 0 (10)
 lp + lq + lr − ls ≧ 0 (11)

 これで、タイプ Lee に対する一般的な制約式は終わりです。 あとは、頂点に対する変数 s の定義(路線の接続状況に相当する)と、 それぞれの枝の距離を与えてやれば、ソルバーで解くことができます。 さて、どんな結果が出ますやら…それは次のページのお楽しみ。


タイプ Pe の定式化

 残る2タイプのうち、タイプ Pe について、同様に制約式を加えていきます。

終端駅は1回だけ

 まず終端駅に関して。タイプ Pe は発駅が終端駅、着駅が分岐駅ですから、 終端駅は経路全体でちょうど1回だけ通ることになります。 したがって、以下のような制約式が入ります。

Σ(すべての終端駅 i) si = 1 (12)

分岐駅は「枝3本同時使用」も可

 次に分岐駅に関して。 タイプ Pe の着駅(分岐駅)では、そこに接続する枝のうち3本を通ります。 ですから、分岐駅に対する制約式はタイプ Lee のときよりも甘くなり、 以下のようになります。

すべての分岐駅 i に対して
 si ≦ 3
(13)

 この式で si の値は0、1、2、3のどれかに制約されます。 ここから si = 1 を除外する方法はタイプ Lee と同様です。

でも、「枝3本同時使用」は全国1カ所

 しかし、「接続する3本の枝を同時に使う駅」は着駅のみなので、 式 (13) はあまりにも甘すぎます。 このままでは全国で何カ所も「枝3本同時使用」が許されるので、 むちゃくちゃな経路が最適解として出てきかねません。
 そこで、「3本の枝を通っていいのは全国で1カ所だけ」 という制約を入れたくなりますが、これもまた、 線形の不等式で記述しようとするとやっかいです。 かなりトリッキーな方法を用いて、ようやくこれを書くことができました。

 まず、最も単純な3分岐の分岐駅を考えます。
 問題解決のために、i 番の分岐駅に対して、 新たな0-1変数 fi を導入します。 すべての分岐駅に対してこの f が定義されますが、 それらの総和は1以下であるとします。つまり以下のような制約式を加えます。

Σi fi ≦ 1 (14)

そして、各分岐駅ごとに制約式を追加します。 たとえば i 番の分岐駅が si = lp + lq + lr であるとするなら、 i 番の分岐駅に関しては以下のような制約式を加えます。

fi ≧ lp + lq + lr − 2 (15)

 これによって何が起こるか考えてみましょう。
 もしも p 番、q 番、r 番の枝を3つとも通るとすれば、式 (15) の右辺は1です。 fi は0-1変数でしたから、必然的に fi = 1 となります。 ここで式 (14) を考慮すると、このように「接続する3本の枝を同時に使う」 ことは全経路の中でたかだか1カ所でないといけません。
 いっぽう、 p 番、q 番、r 番の枝のうちに1つでも通らないものがあれば、 式 (15) の右辺は0以下となり、したがって fi は、 式 (15) を見る限りは0でも1でもよいことになります。 が、式 (14) があるので、おいそれと1になるわけにはいきません。 fi が1になる分岐駅は路線図全体でたかだか1つだけなので、 「0でも1でもいいんだけど、 気分的に1」なんていうイイカゲンな理由で1になることはまずありません。 自然と0に落ち着きます。
 結局、式 (14)(15) により、 「3本同時使用」を1つの経路の中でたかだか1カ所に押さえ込むことができました。

 では、i 番が「4分岐」だったら? ご安心ください。 たとえば、si = lp + lq + lr + ls であれば、以下のように4本の制約式を入れれば目的は達せられます。

fi1 ≧ lp + lq + lr − 2 (16)
fi2 ≧ lp + lq + ls − 2 (17)
fi3 ≧ lp + lr + ls − 2 (18)
fi4 ≧ lq + lr + ls − 2 (19)

 4本の枝から3本を選び出し、 「その3本を同時に使うことは全体でたかだか1回」というふうに書いています。 4本の枝から3本を取り出す組合せは4通りなので、制約式は4本。 5分岐なら10本、6分岐なら20本の制約式がいりますが、 幸い、全国で最も分岐の多い駅(仙台)でも6分岐なので、 制約式が爆発的に増えることはありません。


タイプ Pn の定式化

 さて、最後はタイプ Pn です。疲れてきたから、ってことはないんですが、 これに関しては具体的な定式化をちょっと端折って (タイプ Pe の延長でできますから)、 最もやっかいな問題の解決法だけを取り上げておきます。

分岐駅のとなりの駅…ないぞ?

 タイプ Pn は、発駅が「分岐駅のとなりの駅」です。 が、これは路線図をグラフに直すときにあっさり削ってしまっていて、 「分岐駅の隣接駅」は、グラフ上には頂点として存在しません。 さて、どうしよう。
 そこで、問題を少し変形することにしました。 発駅である「分岐駅の隣接駅」から、そのとなりの「分岐駅」まで、 経路を1駅ぶん延長するのです。 延長後は「タイプ B」「タイプ B8」などと呼びましょう(図17〜19)。

図17図17 ふつうは、タイプ Pe を1駅延長するとこうなる。
図18図18 しかし場合によってはこうなるかも。 このタイプは図17と同じ定式化でOK。
図19図19 さらにこうなる場合も。 これは図17とはちょっと異なる定式化がいるので、独立したタイプを定義。

 こうすれば、発駅も着駅も分岐駅となり、グラフ上に存在します。 これでめでたく制約式が書けるようになります。
 ちょっと待て、これじゃ発売条件を満たさないじゃないか! …そのとおりです。 最適解が求まったら、1駅ぶん短縮してタイプ Pn に戻し、 それでもなおほかのタイプ Pn の解よりも長いぞ、 ということを示さないといけません。けっこうやっかいです。
 しかし、実際にはこのめんどうな作業は不要でした。 どうしてかな? それは次ページのお楽しみ。


定式化は完全か?

 以上で、各タイプについて具体的に制約式を作り、 各タイプの中でもっとも長い経路を求める整数計画問題を記述することができました。 ですから、あとはこれをソルバーに与えて解かせるだけ、のはずです。
 ところが実際には、 ソルバーの返す最適解は発売条件を満たしていないことがほとんどです。 つまりこれは、与えた制約式が不十分だったということです。
 じゃあ十分な制約式を与えればいいじゃないか、と思うかもしれませんが、 実際にはそれが困難なことがあります。しかたがないので、 これは後述するような場当たり的な対処でカバーすることにします。

タイプ Lee の「独立なループ」問題

 制約式が不十分な例を挙げましょう。タイプ Lee に関してです。

 前のページで列挙した制約式を全部ソルバーに与えると、ソルバーはたいてい、 「本筋とは独立したループ」を含んだ経路を解として返してきます(図20)。 もちろん、これは発売条件を満たしません。

図20図20 1本道の上に小さなループが。 一見「だれがこんな経路を作れと言った!」と文句を言いたくなりますが、実は…

 何だこれは、と制約式を読み返してみると、 タイプ Lee の経路1つに、それとは接続しないタイプOの経路が1つ以上あっても、 制約式をすべてクリアしてしまうことが分かります。 つまり制約式が十分でなかったのです。
 この「独立なループ」を除去するには、「解となる経路は連結なグラフである」 ということを表す制約式があればよさそうですが、 これを適当な数の(=多すぎない)線形の等式、不等式で書くのは非常に困難です。 少なくとも私たちがぱっと思いつくことはなさそうでした。

 このように、発売条件を満たさない解を事前に与える制約式で除去しきれない場合、 出てきた解を見て、 場当たり的に制約式を追加していくという手があります。
 たとえば、タイプ Lee の最適解を求めた結果、 p 番、q 番、r 番 の3本の枝から成る独立なループが解に混入していたとしましょう。 こんなときには、以下のような制約式を追加して、再度ソルバーを動かします。

lp + lq + lr ≦ 2 (20)

 この制約式は、名指しで「p、q、r を同時に全部使うのはダメ」と直接的に宣言しています。 このような制約式を入れれば、 さっき出てきた解はこの制約式に引っかかるので、もはや出てきません。 p、q、r のどれかを使わない「次善の経路」が出てきます。
 いっぽう、タイプ Lee のまっとうな経路では、p 番、q 番、 r 番の枝をすべて同時に使うということはありません(同時に使ったら、 同じ駅を2度通る経路になってしまう!)。 ですから、このような制約式を入れても、 独立なループを含まない、真にタイプ Lee の経路にはまったく影響しません。 つまり、式 (20) によって条件を満たす経路まで除去してしまうことはないわけです。

 もちろん、式 (20) のようなものを1本入れただけでは、 おそらく解はまともになりません。 「p、q、r を同時に使いさえしなければいいんだろ」とばかりに、 ソルバーは別のループを見つけてくるはずです。 そうしたら、私たちはその解を見て、 また同じように「これとこれを同時に使うのはダメ」という制約式を追加します。 そして解き直します。
 そうしているうちに、いつかは「ループを加えて距離をかせぐより、ループなしで、 タイプ Lee の経路だけを作ったほうが距離が長くなる」という状態になります。 そうなるとようやく、タイプ Lee の「使いものになる解」が出てきます。 こうして得られた最適解が「タイプ Lee で最も長い経路」となります。

 何度も解を見て解き直すのがいやだから、 グラフ上のすべてのループを事前に列挙し、 それらすべてを禁止する制約式を入れてから解く、 という方法もないではありませんが、 ループの数はグラフの規模とともに指数関数的に増えるので、 実際には役に立ちません。

Pe、Pn にも問題はあるが…

 同様の問題、すなわち「制約式が不十分」という問題は他のタイプにもあります。 が、これらについてはまじめに考えないことにします。
 そんなことでいいのか? 「いーんです!」
 次のページを読めば、 なぜこんな一見いいかげんなことが許されるのかが分かります。



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