最小コストな路線ネットワーク

次のような問題を考えよう。

まだ鉄道が敷かれていない複数の駅を連結するような最小の路線ネットワークを作る。このとき、それぞれの駅間を線路でつなぐためのコストが与えられているとして、最小のコストで実現できる路線ネットワークは何か？

駅を頂点、線路を辺とするグラフを考えると、コストは辺に重みが与えられていると考えられ、最小の路線ネットワークとはグラフの最小全域木（Minimum Spanning Tree）であるから、最小全域木の全体で、それを構成する辺の重みの和を最小化するものを求める問題になる。

グラフの最小全域木は、いわゆるマトロイドの代表例である。この問題はマトロイドの最適化の問題に帰着される。マトロイドを計算するようなプログラムはまだ少ないのだけれど、この種類の問題をとくことができるものが COIN-OR に紹介されていた。

https://projects.coin-or.org/MOCHA

抽象化されたマトロイドに対して最適化を解けるわけではなく、グラフとベクトルからなるマトロイドについて、計算できるというものだが、問題そのものをこれらのどちらかに帰着すればよいので、使い道はありそう。