インストール方法 : 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