インストール方法 : Concorde
巡回セールスマン問題 (Travelling salesman problem; TSP) を高速に解く Concorde のインストール方法のメモ.
環境は 18.04.1 LTS (Bionic Beaver), x86_64 です.
方法1. ソースコードからインストール
ここ の「Source Code」にある「gzipped tar file」から最新のものをダウンロードして README に従ってインストールをします.
$ tar xzvf co031219.tgz # co031219.tgz はダウンロードしたファイル $ cd concorde # 解凍したディレクトリ concorde に移動 $ ./configure $ make $ ./LINKERN/linkern -k 50 # 頂点数50の入力をランダムに生成してでLin-Kernighanで解く
厳密解法である concorde は TSPディレクトリ内にあり,整数計画ソルバーの QSopt か CPLEX を使用します.上の「./configure」のときにオプションで使用する整数計画ソルバーを設定する必要があるのですが,どうしても上手くいきません...
Lin_kernighanアルゴリズムは整形計画ソルバーを使用しないので上の通りにすると実行することができます.
方法2. 実行ファイルをダウンロード
ここ の「Executable Programs」にある「gzipped executable」から「concorde-linux」をダウンロードします.「linkern-linux」はLinKernighanアルゴリズムです.
TODO
- ソースコードからconcordeをビルドする