ロットサイズ決定問題と最短路問題

こちらの OR Wiki にも解説されているように、ロットサイズ決定問題は最短路問題に変換して解くことができるので、試しに最短路問題に変換して最短路ソルバーで解いてみた。ロットサイズ決定問題のデータは添付図の数値を用いる。

○ dimacs format graph file
c Shortest Paths : Lotsizing Problem
c
p sp 6 15
c
c
a 1 2 13
a 1 3 22
a 1 4 50
a 1 5 55
a 1 6 79
a 2 3 6
a 2 4 20
a 2 5 23
a 2 6 39
a 3 4 24
a 3 5 28
a 3 6 48
a 4 5 6
a 4 6 22
a 5 6 7

○ query ファイル
c Shortest Paths : Lotsizing Problem
c
p aux sp p2p 1
q 1 6

以下が実行結果となるが、 1 → 2 → 5 → 6 と進むのが最短路（つまり 1, 2, 5 日目に生産を行う)であり、最短路長（ロットサイズ決定問題のコスト）は 43 となる。

c fixed source destination solution
c -----------------------------------------------------------
c 0 1 6 43