フリーの線形計画問題ソルバーの一つ、glpk を unstable にコミットしました。 これを使って最長片道きっぷの問題も解くことができます。

参考: 最長片道きっぷの経路を求める