約３年ぶりに「全面的な再計算」を行うのにあたり、
３年前と同じでは芸がないので、新たな「計算戦略」を導入しました。
この戦略により、タイプ Lee の最長経路を求めてしまえば、タイプ Lee
以外のタイプに望みがないことを１回の計算で証明することが可能になりました。
このページで扱うのは、
整数計画法で最長片道きっぷの経路を求める場合の「新戦略」に関する話題です。
より具体的にいうと、タイプＬの最長経路をあらかじめ求めておけば、
「タイプＬ以外の経路はタイプＬの経路を上回れない」ということを、
１つの整数計画問題を解くだけで証明してしまえるというのが、
今回新たに考案した戦略です。
念のため、誤解のないように書いておきますが、
この戦略は問題の対象を「現在のＪＲの路線図のうち、
北海道・四国・九州を１本の枝にまとめて本州の路線図につなげたもの」、
すなわち「現在のＪＲの最長片道きっぷを求めるのに必要な路線図」に絞ったもので、
一般的な路線図すべてに適用できるものではありません。
2002年11月までの最長経路を見ると、2002年12月以降も、
前述の路線図ではタイプＬが最長であることが予想されます。
それなら、他のタイプの扱いをできるだけ簡略化すれば、
全体として計算が楽に済むだろう、という考えです。
整数計画法で最長経路を求めるには、まず北海道、四国、
九州の３島について「本州と出入りできる経路のうち最長のもの」を求めておき、
この「出入り可能な最長経路」と同じ長さを持つ枝（行き止まりの路線）を計３本、
本州の路線図に付け加えてやるのでした。以後は、この「気分的にはＪＲ全線」
の路線図のもとで整数計画問題をいくつか解いていきます。
（よく分からない人は [2-4]
により詳しい説明がありますので参考にしてください）。
この路線図上では、「北海道と九州の双方を通る経路」は必ずタイプＬとなるので、
３島のうちたかだか１つしか通れないタイプＰは圧倒的に不利です。
このことを利用すると、
「タイプＰのうちで最長のもの」を苦労して求める必要はなく、
以下のような順序で「全タイプを通じた最長経路」を求めることができるのでした。
さて、ここで「タイプＰ」と書いた経路は、発駅の性質により「タイプ
Pe」と「タイプ Pn」に分類され、さらに「タイプ Pn」は、
「１駅延長したときの形態」により「タイプＢ」と「タイプ
B8」に分類されます。つまり、タイプＰは Pe、B、B8
という３タイプに分類されます。
本編では、この３タイプを別々に扱い、
上記のような方法で３つのタイプをそれぞれ否定し、
タイプＬが最長であると結論づけました。
さて、共同研究者の宮代くんは、新たな最長ルートを求めるにあたって、 「タイプＬ以外の３タイプをひとまとめにする」方法を思いつきました。
Ｐ形の経路を定式化する際に生まれた３つのタイプは、 それぞれ以下のような性質を持っています （参考としてタイプＬについても書いておきます）。
| タイプ Pe | タイプ B | タイプ B8 | タイプＬ （参考） |
|
|---|---|---|---|---|
| 終端駅を何度通るか | １回 | ０回 | ０回 | ２回 |
| １つの駅に接続する枝を 同時に最大何本使うか |
３本 | ３本 | ４本 | ２本 |
| ただし、終端駅以外では 「１本だけ使う」ことを許さない |
||||
| 「１つの駅に接続する枝を３本同時に使う」 ことを何度許すか |
１回 | ２回 | ０回 | ０回 |
| 「１つの駅に接続する枝を４本同時に使う」 ことを何度許すか |
０回 | ０回 | １回 | ０回 |
このように、Pe、B、B8 の３タイプはそれぞれ性質が異なるので、
正直にこれを定式化すると各タイプで異なった制約式ができます。
だからこそ、本編ではこの３タイプを別物として扱い、
同じようなことを３回やったのです。
が、制約を緩くしてよいのなら、３タイプを同じ制約式で表現できます。
この部分が「新たな戦略」のキモです。
たとえば「終端駅を何度通るか」に関しては、
タイプ Pe が１回、その他が０回となっていますが、
これを「１回以下」と書けば３タイプに共通の制約式になります。
同様に、１つの駅に接続する枝を「４本以下」と書けば、
「同時使用本数」についても３タイプを１つの制約式で記述できることになります。
ちょっとややこしいのが「３本同時使用」「４本同時使用」ですが、 結論からいえば、「４本同時使用は１回だけ」という制約を 「３本同時使用は４回だけ」と書き換えることで、 ３タイプをまとめることができました。
「３本同時使用が１回だけ」という制約をどう定式化するかについては本編（[2-3]）でふれましたが、
もう一度おさらいしておきます。
「ある駅に接続する枝を３本同時に使うときだけ１になる変数」として0-1変数
fi を用意し、a、b、c の３本の枝が出ている駅 p に対して
| fp ≧ la ＋ lb ＋ lc − 2 | (A1) |
と定義します。ここで la は「a 番の枝を通る」ときに１、
「通らない」ときに０になる変数です。
d、e、f、g と４本の枝が出ている駅 q に対しては、
| fq1 ≧ ld ＋ le ＋ lf − 2 | (A2) |
| fq2 ≧ ld ＋ le ＋ lg − 2 | (A3) |
| fq3 ≧ ld ＋ lf ＋ lg − 2 | (A4) |
| fq4 ≧ le ＋ lf ＋ lg − 2 | (A5) |
のように「４本の枝から３本をとる組合せ」をすべて列挙してやればよく、最後に
| Σi fi ≦ 1 | (A6) |
という制約式を入れれば、
「１つの駅から出る枝を３本同時に使用する」回数はたかだか１回にできるのでした。
（５分岐以上の駅に対しても、３本ずつ取り出して列挙すれば同様に扱えます。）
いっぽう、タイプ B8において必要な「４本同時使用は１回だけ」
という制約の定式化については本編でふれませんでしたが、
「３本同時使用」とまったく同じ手法を使いました。
タイプ B8では「４本同時使用」は１回あるものの「３本同時使用」はないので、
fi は定義せず、かわりに「４本同時使用のときだけ１になる変数」
ei を定義していたのです。
さて、１つの駅から出る枝を４本同時に使用する場合に、 前述の fi が定義してあったら、その値はどうなるでしょうか？
たとえば、d、e、f、g
という４本の枝が出ている駅 q があって、これら４本の枝をすべて使うとすると、
ld、le、lf、lg
はいずれも１なので、式 (A2)〜(A5) により fq1〜fq4
はいずれも１となります。もし、この駅以外に「３本以上同時使用」がなければ、
Σi fi の値は４となります。
このことを利用して、タイプ B8でも ei を定義する代わりに
fi を定義し、
| Σi fi ≦ 4 | (A7) |
とすれば、ei を使って定式化するより制約が若干緩くなるものの、 「４本同時使用」を１回以下に抑えられます。
これでもうお分かりでしょう。 「４本同時使用が１回」という制約を「３本同時使用が４回」とみなせば、
となることから、 「３本同時使用は４回以下」という制約式で３タイプを総括できるのです。
長くなりましたが、タイプ Pe、タイプ B、タイプ B8の３タイプは、以下のような共通の制約（以下「PBB8 制約」と呼ぶ）を満たします。
PBB8 制約を満たす経路には、タイプ Pe、タイプ B、タイプ B8
の３タイプに属するすべての経路のほかに、「３タイプのどれにも属さない経路」、
つまり「ゴミ」も多く含まれています（図 A2）。
が、「PBB8 制約を満たすもののうちで最長のもの」、
すなわち「タイプ Pe とタイプ B とタイプ B8
とゴミの中で最長のもの」が「タイプＬで最長のもの」
より短いことがいえれば、Pe、B、B8
の任意の経路は「タイプＬの最長」より短いことになります。
そして実際、「PBB8 制約を満たすもののうちで最長のもの」を計算してみると、
その運賃計算キロは11339.1kmとなりました。
タイプＬの最長は11614.9kmでしたから、タイプ Pe、タイプ B、タイプ B8
のいずれも「真の最長経路」にはなり得ない、
ということが一気に証明できました。
← 図 A2 「PBB8 制約」の概念図です。
斜線部が「ゴミ」に相当します。Pe、B、B8
を別々に解いたときにも「ゴミ」は混じっていたのですが
（３タイプの外周にある右下がりの斜線部）、
今回は３つをひとまとめにすることで、
より多くの「ゴミ」が混じることになりました。ところで、PBB8 制約を満たす最長の「経路」ってどんな形だろう？ そんなことを考えたあなたのために、大サービスで地図を作ってみました（図 A3）。
← 図 A3 「PBB8 制約」を満たす最長経路です。
３島のうち北海道を通り、３分岐は盛岡、越後湯沢、長門市の３カ所に現れています。
孤立したループが無数にあることも分かるでしょう。見にくいと思った人は拡大版をどうぞ。
