← 図A3-1 Ａのような解が出てきても、
右下の孤立ループを単純に禁止することはできません。
真の最長経路がＢのようになる可能性があるからです。
この「付録３」は、 最長片道きっぷの経路を求める方法を記した「本編」に付随するもので、 「これまでに得られた数学的な知見をまとめる」 「無料で利用できるソフトウェアだけで最長経路を求める」というのが内容の２本柱です。
2005年春、特に最長経路に変化があったわけではありません。しかし LOP
を取り巻く状況は着実に変わりつつあります。
無料で利用できる整数計画ソルバーの性能が格段に上がったうえ、
ＰＣ自体の性能も着実に上がっています。さらに LOP
研究者の性能も上が…ったかどうかは分かりませんが、
長いこと数式をにらんでいると新たな発見もあるもので、
制約式の面でも多少の進歩がありました。これらの進歩により、
商用のソルバーを利用できない環境でも、
ＪＲ全線を対象とした最長経路を計算することが現実的になってきました。
そこで、この「付録３」では、まず制約式の改善（あるいは、
これまで説明していなかった事項）についてまとめます。
次に、無料で利用できるソフトウェアだけで最長経路を求める方法について説明し、
興味のある人が自ら最長経路を計算できるような環境を提供します。
この文書は、「本編」をすでに読み、
それなりに理解していることを前提にしています。
必要なソフトウェアをインストールして、
出来合いのデータで最長経路の計算を追体験するだけなら、
制約式に関して理解していなくても何とかなります。
が、それでは単なる「体験」で終わってしまい、
自分の思いどおりに「計算」することはできません。
もし、「○○という条件で最長経路を求めてみたい」といった目標があるのであれば、
少々取っつきにくい見かけではありますが、ぜひ、
制約式の理解に努めてほしいと思います。
整数計画法自体について深く理解することは難しいかもしれませんが
（私も表面的にしか理解していません）、
こうした問題を解くためのツールだと割り切れば、
パズル感覚で取り組めるはずです。
まず最初に、 2000年当時にすでに知っていながら今まで文書として公開していなかった、 「タイプＬ以外の孤立ループ禁止法」について説明します。
どのタイプにも共通の問題として、
整数計画法を用いて最長経路を求めようとすると、
「本筋」のルート（タイプＬなら一本道、タイプＰなら６の字）のほかに、
本筋と接点を持たない「孤立したループ」が含まれる可能性があります（詳しくは本編の「[2-3] 整数計画法で（制約式編） -
定式化は完全か？」を参照）。
本編では、タイプＬについて、この孤立したループを禁止する制約式を紹介しましたが、
タイプＰ（実際に解く場合には Pe、B、B8）では同じ制約式は使えません。
なぜなら、タイプＰの経路は、それ自体がループを１つ含んでいるからです。
たとえば、タイプＰの最長経路を求めるとき、本筋の経路のほかに、p、q、r
という３本の枝から成る孤立ループが解に含まれていたとします。
しかし、ここで「p、q、r の３本を同時に使うことはない」という制約式を追加すると、
真の最長経路の芽を摘んでしまう恐れがあります。
タイプＰの最長経路にはループがちょうど１つ含まれていますが、
その１つのループが「pqr」かもしれないのです。
← 図A3-1 Ａのような解が出てきても、
右下の孤立ループを単純に禁止することはできません。
真の最長経路がＢのようになる可能性があるからです。
ピンとこない人は、p が「肥前山口→早岐」、q が「早岐→諫早」、r が「諫早→肥前山口」だと思ってください。p、q、r の３本を同時に使うとループになります。だから、問題を解く過程で pqr が孤立ループとして現れる可能性もあります。しかし、そこで「pqr 同時使用不可」という制約式を入れてしまったら、 「あの」最長経路は絶対に出てこなくなるのです。
この問題の解決法はいくつか考えられますが、今回紹介するのは、 以下で説明する「孤立したループだけを禁止する制約式」です。
タイプＰの経路の一部を形成するループと、単なるゴミの孤立ループ。
そのちがいは文字どおり「孤立しているか否か」です。
この「孤立している」という特徴を少し言いかえると、
「ループ上の駅から分岐する枝を１本も使っていない」ということができます。
そこで、図 A3-2 のような「孤立したループ」が現れた場合、以下のような制約式
(A3-1) を加えることで、孤立したループだけを禁止します。
（参考までに、タイプＬの場合に用いた、
「ループを禁止する制約式」を式 (A3-2) に示します。）
← 図A3-2 孤立したループの例
| ループ禁止制約式 for タイプＰ： | |
| eab ＋ ebc ＋ eca − ea1 − ea2 − eb1 − ec1 ≦ 2 | (A3-1) |
| ループ禁止制約式 for タイプＬ： | |
| eab ＋ ebc ＋ eca ≦ 2 | (A3-2) |
この「付録３」では、枝（＝線路）を表す変数を「e123」、 頂点（＝駅）を表す変数を「v456」と表記します。 それぞれ「edge（枝）」「vertex（頂点）」の頭文字です。
以前は枝変数が「line」の頭文字をとって「l123」、 頂点変数が「station」の頭文字をとって「s456」だったのですが、 「l」が数字の「1」とまぎらわしいうえ、 筆者が「edge」「vertex」という言葉に慣れ、 制約式生成ツールなどもすべて「e」「v」で作ってしまったので、 今後はこの表記で統一したいと思います。 「付録２」以前の文書もそのうち書き換えたいと思いますが、 当面は「l→e」「s→v」と読み替えてください。
タイプＬ用のループ除去制約式 (A3-2)
に、マイナスのついている４変数を追加したのが式
(A3-1) です。eab、ebc、eca
の３本をすべて使っても、ea1 や eb1
といった「ループ上から分岐する枝」を同時に使っていれば、
左辺は２以下になります（本物のタイプＰはこれに該当します）。
逆に言うと、左辺が３以上になるのは「eab、ebc、eca
の３本をすべて使い、なおかつ ea1、ea2、eb1、
ec1 の４本をどれも使わない場合」、つまり、A-B-C
というループが他の経路から孤立している場合に限られます。
上の例ではマイナスのついた枝変数は４つでしたが、
これが何個になるかは場合によります。
禁止したい孤立ループ上から分岐する枝をもれなく列挙し、
それらに対応する枝変数全部にマイナスをつけて制約式に加えないと、
解の厳密さを損ねます。
この制約式はタイプＰ一族（Pe、B、B8）のどれにでも適用できます。
タイプＬでこの制約式を使っても（メリットはありませんが）問題ありません。
細かい話ですが、「日」形の外周をたどるような孤立ループが出てきた場合、 これを禁止するための制約式に「日」の真ん中を横切る枝を加えるかどうか、 という問題があります。たとえば図 A3-3 のような状況で、 「−eab」を制約式に加えるかどうか、ということです。
← 図A3-3 「日」形の真ん中を横切る枝の取り扱いについて。
図の右側の経路はまっとうなタイプＢの経路なので、
タイプＢでは eab を考慮する必要があります。
結論からいえば、タイプＢでは「真ん中の枝」を加えることが必須です。「[2-3] 整数計画法で（制約式編） - タイプ Pn
の定式化」に書いたとおり、
タイプＢには「□＿□」という一般的な形（ループ２つを１本線で結んだ形）のほか、
「日」形のものも含まれるので、孤立したループを禁止したい一方で、
それに枝を１本加えた「日」形は禁止してはいけないのです。
いっぽう、タイプ Pe やタイプ B8
では「日」形の「真ん中の枝」を加える必要はありません。
その理由はタイプＢの逆、すなわち「日」形の経路がタイプ Pe やタイプ B8
とは呼べない（ので、「日」形を禁止する制約式を加えてもかまわない）からです。
ただ、「真ん中の枝」を制約式に加えることは、
加えない場合と比較すると制約を弱める方向にはたらくので、
「真ん中の枝」を加えた制約式をタイプ Pe やタイプ B8
に適用しても、厳密さを損ねることはありません（が、
計算時間が長くなるなどのデメリットはあるかもしれません）。
タイプ Pe・B・B8 では、「ある１駅に接続する枝を同時に３本使ってもよい、 しかしそれは全国で１回だけ」という制約を表現するために、新たな変数 fi を定義します（「f」は「fork」の意）。この「fork 変数」の定義を見直し、制約式の本数の削減を図りました。
もともとの fi の定義については、「[2-3] 整数計画法で（制約式編） - タイプ Pe
の定式化」に書いたとおりで、
３分岐の駅に対しては fork
変数を１つ、４分岐の駅に対しては（4Ｃ3＝）４個、
５分岐なら（5Ｃ3＝）10個…と、
多くの枝が出ている駅では多数の変数を定義しなければなりませんでした。
そのぶん制約式の数も増えます。
このときは fork 変数 fi を0-1変数と定義していて、
そのために「枝数が増えると fork 変数の個数も増える」ということになったのですが、
あらためて考えてみると、fork 変数が２以上の値をとっても、
制約式を書くうえで問題はありません。
そこで、fork 変数の定義を以下のように見直しました。式 (A3-3)
は、駅 s から５本の枝 e1〜e5 が出ている場合の例です。
新しい定義では、ある駅からどれだけ多くの枝が出ていようと、その駅に対する fork 変数は１つです。右辺は「出ている枝変数の合計−２」となります。 この駅 s から出ている枝を２本使うだけなら fs は０以上（の任意の整数）、同様に３本使うなら１以上、 ４本使うなら２以上となります。より詳細に書くと表 A3-1 のとおりです。
| 駅 s から出る枝を 何本使うか |
式 (A3-3) による fs の下限 |
式 (A3-4) による fs の下限 |
fs の下限 | |
|---|---|---|---|---|
| ０本 （駅 s を通らない） |
−2 | 0 | 0 | |
| １本 （駅 s は終端駅） |
終端駅には fork 変数を定義しない 分岐駅では「１本だけ使用」はあり得ない |
|||
| ２本 （駅 s を１度通過） |
0 | 0 | 0 | |
| ３本 （駅 s はタイプ Pe の終点 or タイプＢの起終点） |
1 | 0 | 1 | |
| ４本 （駅 s はタイプ B8 の起終点） |
2 | 0 | 2 | |
式 (A3-3) と式 (A3-4) では fork
変数の下限を決めただけで、上限は決めていないので、
別に上限を決める必要があります。
たとえばタイプ Pe
であれば、以前と同じように「すべての（全駅の）fork
変数の総和は１以下」という制約式（[2-3] の式 (14)）を別に入れてやります。これで
fork 変数の値が必要以上に大きくなる（たとえば、まったく通らない駅の
fork 変数の値が１や２になる）ことは防げますし、
「３本同時使用」の駅がいくつも出てくるようなことを抑えられます。
式 (14) はタイプ Pe の場合なので fork 変数の総和は１となっていますが、
総和を変えることで他のタイプにも対応できます。
まずタイプＢなら、スタートとゴールの２駅が「３本同時使用」となるので、
fork 変数の総和はどうしても２以上になります。
そこで、fork 変数の総和を２以下に制限する制約式（式 (14)
の右辺を２にしたもの）を入れてやります。
タイプ B8 も同様で、表 A3-1 によると「４本同時使用」の場合には fork
変数が２以上となるので、fork 変数の総和を２以下として、
「４本同時使用」を全国１カ所に抑えます。
これは結果的にタイプＢと同一の制約式になります。
以上のように fork 変数の定義を変えたところ、解答時間が短くなりました。 問題にもよるので一概に何％短縮とはいえませんが、 たとえば「ＪＲ西日本の最長経路」を求めようとしたとき、タイプ Pe の解答時間（ループ除去制約式の追加をして解き直す過程の計算時間の総和）は、 もともと15分ほどかかっていたものが３分で解けるようになりました。 これは効果が顕著に出た例ですが、 「かえって遅くなった」という事例は多くないと考えています。
タイプＢ８は、ＪＲ全線を対象とした最長経路を求めるとき、
解き始めてすぐに「最長になる望みがない」と判明したため、
最後までまじめに解いたことがありませんでした。より正確に言うと、
ループ除去を繰り返して「ちゃんとしたタイプＢ８の最長経路」が出てくるまで解き直す、
という作業を怠っていました。
しかし、たとえば「本州だけの最長片道きっぷ」を考えたときには、
タイプＢ８が最長にならないとも限りませんし、
そうでないにしても、タイプＢ８の中で最長のものはどういう経路なのか、
興味もあります。
そこで、あらためてタイプＢ８について考えてみることにしました。
タイプＢ８は、全国で１カ所だけ「ある駅から出る枝を４本使う」ことがあり、 あとはすべての駅が「０本 or ２本使用」です。 つまり「ある駅から出る枝をちょうど３本だけ使う」ということはありません。 このことを制約式として表現する必要があります。
まず、枝がちょうど３本出ている駅では、 「４本同時使用」があり得ないので、 「使う枝は２本以下」という制約式を入れればＯＫです。たとえば駅 s から３本の枝 e1〜e3 が出ている場合、 以下のような制約式 (A3-5) を入れます。
| e1 ＋ e2 ＋ e3 ≦ 2 | (A3-5) |
次に、４本以上の枝が出ている駅に関しては、 「３本同時使用だけは不可」という制約式を入れます。たとえば駅 s から４本の枝 e1〜e4 が出ている場合、 以下のような制約式 (A3-6)〜(A3-9) を入れます。
| e1 ＋ e2 ＋ e3 − e4 ≦ 2 | (A3-6) |
| e1 ＋ e2 − e3 ＋ e4 ≦ 2 | (A3-7) |
| e1 − e2 ＋ e3 ＋ e4 ≦ 2 | (A3-8) |
| −e1 ＋ e2 ＋ e3 ＋ e4 ≦ 2 | (A3-9) |
発想は「タイプＰのループ除去」、
あるいは「枝を１本だけ使うのは不可」（詳細は「[2-3] 整数計画法で（制約式編） - タイプ Lee
の定式化」参照）というのと同じです。
４本のうちちょうど３本だけを使うと、(A3-6)〜(A3-9)
のどれかは左辺が３になり、「≦２」を満たさなくなります。いっぽう
e1〜e4
の４本すべてを使えば、すべての式で左辺が２となり、制約を満たします。
５分岐以上の駅に対しては、すべての枝を列挙して、
そのうち３つに＋、残りに−の符号をつけます。
そしてすべての符号の組合せ（ｎ分岐で nＣ3通り）を網羅すれば、
同様に「３本同時使用」だけを禁止する制約式を書くことができます。
以上のような制約式を入れて問題を解いてみると、 たしかにタイプＢ８のルート（＋０個以上の孤立ループ）が出てきます。 そして多くの場合、総距離はかなり短くなります。 もともと、３分岐にくらべると４分岐以上の駅はそれほど多くないため（たとえば本州では、 ３分岐の駅が約150あるのに対し４分岐は約40駅、５分岐以上は約10駅しかない）、 「必ず４分岐以上の駅がスタート・ゴールになる」というタイプＢ８の特徴を満たすことは意外に厳しいようです。