← 図17 ふつうは、タイプ Pe を１駅延長するとこうなる。
← 図18 しかし場合によってはこうなるかも。
このタイプは図17と同じ定式化でＯＫ。
← 図19 さらにこうなる場合も。
これは図17とはちょっと異なる定式化がいるので、独立したタイプを定義。
このページでは、LOP の最適解を求める問題を整数計画問題として定式化する際に、
どのような制約式を入れたらいいかをタイプ別に考えます。
変数の定義などは前ページを参照してください。
LOP の最適解はタイプ Lee、タイプ Pe、タイプ Pn
のどれかであることが分かっているため、
まずはそれぞれのタイプの中で最長の経路を１つずつ求めます。
すべてが出そろったら、各タイプの「代表」どうしを比較し、
３つのうちで最長のものを全体の解にしよう、というもくろみです。
これまでに準備した変数などを用いて、タイプ Lee
の経路の中で最長のものを見つける問題の定式化を行ってみましょう。
目的関数は前ページの式 (2)
で決まりですから、以下ではどんな制約式を入れるかを考えます。
式 (1) や、駅に対する従属変数 s
の定義は暗黙のうちに制約式に含まれているとします。
まず、タイプ Lee
の特徴である「発着駅がともに終端駅」ということを表す制約式を書きます。
これは単純で、以下のようになります。
| Σ(すべての終端駅 i) si ＝ 2 | (3) |
i 番の頂点が終端駅なら si は０か１にしかならず、 ０ならその駅は通らない、１ならその駅を通るという意味になるので、 路線図全体で終端駅の変数を合計して２であれば、 それは「いま考えている経路が通る終端駅はちょうど２つ」ということになります。
次に、分岐駅に関して。
タイプ Lee は同じ駅を２度通らないので、これを表す制約式が必要です。
ある分岐駅を通るか通らないかは自由で、
同じ分岐駅を２度以上通りさえしなければいいので、
以下のように書けば十分であるような気がします。
| すべての分岐駅 i に対して si ≦ 2 |
(4) |
しかし、実はこれでは不完全です。
というのは、si ＝ 1 が許されているからです。
si ＝ 1 というのは「その駅に来るが、
そこから出ていかない」ということで、こういうことは発着駅でのみ起こります。
タイプ Lee では発着駅は終端駅と決まっているので、
分岐駅で si ＝ 1 になっては困ります。
分岐駅では、si は０か２であってほしいのです。
じゃあそうやって書けばいいじゃん、と思うかもしれませんが、
これがなかなか難しいのです。
整数計画問題では、制約式をすべて線形の等式や不等式（と、
「この変数は整数である」という制約）
にしないと効率的に解けないからです。
直接「０または２」と宣言しようとすると「or」演算子が必要ですが、
これを使ってしまうと、ソルバーの計算スピードが極端に落ちます。
「１ではない」と宣言しようとしても同様です（「≠」演算子が原因）。
この問題を解決するために、ちょっとトリッキーな不等式を作ることにしました。 たとえば i 番の駅が「３分岐」で、si ＝ lp ＋ lq ＋ lr であるとするなら、 以下のような３本の不等式を制約式として加えるのです。
| −lp ＋ lq ＋ lr ≧ 0 | (5) |
| lp − lq ＋ lr ≧ 0 | (6) |
| lp ＋ lq − lr ≧ 0 | (7) |
もし lp、lq、lr のすべてが０なら、
この３つの式はすべて成り立ちます（左辺は全部０）。
もし lp、lq、lr のうち２つが１、
残り１つが０でも、３つの式はすべて成り立ちます。
しかし lp、lq、lr のうち１つが１、
残り２つが０だと、３つの式のうち１つは成り立たなくなります。
たとえば lp が１、そのほかが０だと式 (5) は成り立ちませんね。
結果として、
この３式で「３つの枝のうち１つだけを使う」場合、
すなわち si ＝ 1 となる場合は除去できます。
前に「不完全だ」とした (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 について、同様に制約式を加えていきます。
まず終端駅に関して。タイプ Pe は発駅が終端駅、着駅が分岐駅ですから、 終端駅は経路全体でちょうど１回だけ通ることになります。 したがって、以下のような制約式が入ります。
| Σ(すべての終端駅 i) si ＝ 1 | (12) |
次に分岐駅に関して。 タイプ Pe の着駅（分岐駅）では、そこに接続する枝のうち３本を通ります。 ですから、分岐駅に対する制約式はタイプ Lee のときよりも甘くなり、 以下のようになります。
| すべての分岐駅 i に対して si ≦ 3 |
(13) |
この式で si の値は０、１、２、３のどれかに制約されます。 ここから si ＝ 1 を除外する方法はタイプ Lee と同様です。
しかし、「接続する３本の枝を同時に使う駅」は着駅のみなので、
式 (13) はあまりにも甘すぎます。
このままでは全国で何カ所も「枝３本同時使用」が許されるので、
むちゃくちゃな経路が最適解として出てきかねません。
そこで、「３本の枝を通っていいのは全国で１カ所だけ」
という制約を入れたくなりますが、これもまた、
線形の不等式で記述しようとするとやっかいです。
かなりトリッキーな方法を用いて、ようやくこれを書くことができました。
まず、最も単純な３分岐の分岐駅を考えます。
問題解決のために、i 番の分岐駅に対して、
新たな0-1変数 fi を導入します。
すべての分岐駅に対してこの f が定義されますが、
それらの総和は１以下であるとします。つまり以下のような制約式を加えます。
| Σi fi ≦ 1 | (14) |
そして、各分岐駅ごとに制約式を追加します。 たとえば i 番の分岐駅が si ＝ lp ＋ lq ＋ lr であるとするなら、 i 番の分岐駅に関しては以下のような制約式を加えます。
| fi ≧ lp ＋ lq ＋ lr − 2 | (15) |
これによって何が起こるか考えてみましょう。
もしも p 番、q 番、r 番の枝を３つとも通るとすれば、式 (15) の右辺は１です。
fi は0-1変数でしたから、必然的に fi ＝ 1 となります。
ここで式 (14) を考慮すると、このように「接続する３本の枝を同時に使う」
ことは全経路の中でたかだか１カ所でないといけません。
いっぽう、 p 番、q 番、r 番の枝のうちに１つでも通らないものがあれば、
式 (15) の右辺は０以下となり、したがって fi は、
式 (15) を見る限りは０でも１でもよいことになります。
が、式 (14) があるので、おいそれと１になるわけにはいきません。
fi が１になる分岐駅は路線図全体でたかだか１つだけなので、
「０でも１でもいいんだけど、
気分的に１」なんていうイイカゲンな理由で１になることはまずありません。
自然と０に落ち着きます。
結局、式 (14)(15) により、
「３本同時使用」を１つの経路の中でたかだか１カ所に押さえ込むことができました。
では、i 番が「４分岐」だったら？ ご安心ください。 たとえば、si ＝ lp ＋ lq ＋ lr ＋ ls であれば、以下のように４本の制約式を入れれば目的は達せられます。
| fi1 ≧ lp ＋ lq ＋ lr − 2 | (16) |
| fi2 ≧ lp ＋ lq ＋ ls − 2 | (17) |
| fi3 ≧ lp ＋ lr ＋ ls − 2 | (18) |
| fi4 ≧ lq ＋ lr ＋ ls − 2 | (19) |
４本の枝から３本を選び出し、 「その３本を同時に使うことは全体でたかだか１回」というふうに書いています。 ４本の枝から３本を取り出す組合せは４通りなので、制約式は４本。 ５分岐なら10本、６分岐なら20本の制約式がいりますが、 幸い、全国で最も分岐の多い駅（仙台）でも６分岐なので、 制約式が爆発的に増えることはありません。
さて、最後はタイプ Pn です。疲れてきたから、ってことはないんですが、 これに関しては具体的な定式化をちょっと端折って （タイプ Pe の延長でできますから）、 最もやっかいな問題の解決法だけを取り上げておきます。
タイプ Pn は、発駅が「分岐駅のとなりの駅」です。
が、これは路線図をグラフに直すときにあっさり削ってしまっていて、
「分岐駅の隣接駅」は、グラフ上には頂点として存在しません。
さて、どうしよう。
そこで、問題を少し変形することにしました。
発駅である「分岐駅の隣接駅」から、そのとなりの「分岐駅」まで、
経路を１駅ぶん延長するのです。
延長後は「タイプ B」「タイプ B8」などと呼びましょう（図17〜19）。
← 図17 ふつうは、タイプ Pe を１駅延長するとこうなる。
← 図18 しかし場合によってはこうなるかも。
このタイプは図17と同じ定式化でＯＫ。
← 図19 さらにこうなる場合も。
これは図17とはちょっと異なる定式化がいるので、独立したタイプを定義。
こうすれば、発駅も着駅も分岐駅となり、グラフ上に存在します。
これでめでたく制約式が書けるようになります。
ちょっと待て、これじゃ発売条件を満たさないじゃないか！ …そのとおりです。
最適解が求まったら、１駅ぶん短縮してタイプ Pn に戻し、
それでもなおほかのタイプ Pn の解よりも長いぞ、
ということを示さないといけません。けっこうやっかいです。
しかし、実際にはこのめんどうな作業は不要でした。
どうしてかな？ それは次ページのお楽しみ。
以上で、各タイプについて具体的に制約式を作り、
各タイプの中でもっとも長い経路を求める整数計画問題を記述することができました。
ですから、あとはこれをソルバーに与えて解かせるだけ、のはずです。
ところが実際には、
ソルバーの返す最適解は発売条件を満たしていないことがほとんどです。
つまりこれは、与えた制約式が不十分だったということです。
じゃあ十分な制約式を与えればいいじゃないか、と思うかもしれませんが、
実際にはそれが困難なことがあります。しかたがないので、
これは後述するような場当たり的な対処でカバーすることにします。
制約式が不十分な例を挙げましょう。タイプ Lee に関してです。
前のページで列挙した制約式を全部ソルバーに与えると、ソルバーはたいてい、 「本筋とは独立したループ」を含んだ経路を解として返してきます（図20）。 もちろん、これは発売条件を満たしません。
← 図20 １本道の上に小さなループが。
一見「だれがこんな経路を作れと言った！」と文句を言いたくなりますが、実は…
何だこれは、と制約式を読み返してみると、
タイプ Lee の経路１つに、それとは接続しないタイプＯの経路が１つ以上あっても、
制約式をすべてクリアしてしまうことが分かります。
つまり制約式が十分でなかったのです。
この「独立なループ」を除去するには、「解となる経路は連結なグラフである」
ということを表す制約式があればよさそうですが、
これを適当な数の（＝多すぎない）線形の等式、不等式で書くのは非常に困難です。
少なくとも私たちがぱっと思いつくことはなさそうでした。
このように、発売条件を満たさない解を事前に与える制約式で除去しきれない場合、
出てきた解を見て、
場当たり的に制約式を追加していくという手があります。
たとえば、タイプ Lee の最適解を求めた結果、
p 番、q 番、r 番 の３本の枝から成る独立なループが解に混入していたとしましょう。
こんなときには、以下のような制約式を追加して、再度ソルバーを動かします。
| lp ＋ lq ＋ lr ≦ 2 | (20) |
この制約式は、名指しで「p、q、r
を同時に全部使うのはダメ」と直接的に宣言しています。
このような制約式を入れれば、
さっき出てきた解はこの制約式に引っかかるので、もはや出てきません。
p、q、r のどれかを使わない「次善の経路」が出てきます。
いっぽう、タイプ Lee のまっとうな経路では、p 番、q 番、
r 番の枝をすべて同時に使うということはありません（同時に使ったら、
同じ駅を２度通る経路になってしまう！）。
ですから、このような制約式を入れても、
独立なループを含まない、真にタイプ Lee の経路にはまったく影響しません。
つまり、式 (20)
によって条件を満たす経路まで除去してしまうことはないわけです。
もちろん、式 (20) のようなものを１本入れただけでは、
おそらく解はまともになりません。
「p、q、r を同時に使いさえしなければいいんだろ」とばかりに、
ソルバーは別のループを見つけてくるはずです。
そうしたら、私たちはその解を見て、
また同じように「これとこれを同時に使うのはダメ」という制約式を追加します。
そして解き直します。
そうしているうちに、いつかは「ループを加えて距離をかせぐより、ループなしで、
タイプ Lee の経路だけを作ったほうが距離が長くなる」という状態になります。
そうなるとようやく、タイプ Lee の「使いものになる解」が出てきます。
こうして得られた最適解が「タイプ Lee で最も長い経路」となります。
何度も解を見て解き直すのがいやだから、 グラフ上のすべてのループを事前に列挙し、 それらすべてを禁止する制約式を入れてから解く、 という方法もないではありませんが、 ループの数はグラフの規模とともに指数関数的に増えるので、 実際には役に立ちません。
同様の問題、すなわち「制約式が不十分」という問題は他のタイプにもあります。
が、これらについてはまじめに考えないことにします。
そんなことでいいのか？ 「いーんです！」
次のページを読めば、
なぜこんな一見いいかげんなことが許されるのかが分かります。