最短経路問題をあえてLPで解いてみる

ちょっと一度，自分でシンプレックス法を実装してみるかなーと思っていろいろ調べてたら，最短経路問題が線形計画問題に緩和して簡単に解ける（最適解が小数にならない）ということを知った．よく考えれば確かにそうなのだけど，せっかくなので基本の基本なのかもしれないけど，試してみた．

とりあえず，GLPKを使ってみた．まず定式化して.modに記述する．たいした問題じゃないので（面倒なので）最短経路を求めるグラフは描画しないが，頂点はv1からv6からなる有向グラフにおいて，v1から，v6の最短経路を求める．その最短経路問題の定式化を以下に示す．

var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;
var x5 >= 0;
var x6 >= 0;
var x7 >= 0;
var x8 >= 0;
var x9 >= 0;
var x10 >= 0;

minimize profit: 8*x1 + 4*x2 + 6*x3 + 5*x4 + 3*x5 + 9*x6 + x7 + 7*x8 + x9 + 2*x10;
s.t. v1: - x1 - x2                                          = -1;
s.t. v2:   x1      - x3 - x4 + x5                           =  0;
s.t. v3:        x2           - x5 - x6                      =  0;
s.t. v4:             x3                - x7 - x8 + x9       =  0;
s.t. v5:                  x4      + x6 + x7      - x9 - x10 =  0;
s.t. v6:                                      x8      + x10 =  1;

結果は，以下の通りちゃんと整数で出力された．

Problem:    path
Rows:       7
Columns:    10
Non-zeros:  30
Status:     OPTIMAL
Objective:  profit = 14 (MINimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 profit       B             14
     2 v1           NS            -1            -1             =            -4
     3 v2           NS             0            -0             =             3
     4 v3           B              0            -0             =
     5 v4           NS             0            -0             =             7
     6 v5           NS             0            -0             =             8
     7 v6           NS             1             1             =            10

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           NL             0             0                           1
     2 x2           B              1             0
     3 x3           NL             0             0                           2
     4 x4           B              1             0
     5 x5           B              1             0
     6 x6           NL             0             0                           1
     7 x7           B              0             0
     8 x8           NL             0             0                           4
     9 x9           NL             0             0                           2
    10 x10          B              1             0
（以下略）