コンコルドTSPソルバー

コンコルド
原作者	デヴィッド・アップルゲイト、ロバート・ビクスビー、ヴァーツラフ・シュヴァータル、ウィリアム・J・クック
初回リリース	1997年8月27日; 27年前
安定版リリース	03.12.19 / 2003年12月19日; 20年前
リポジトリ	www.math.uwaterloo.ca/tsp/concorde/downloads/downloads.htm
書かれた	Ｃ
オペレーティング·システム	Linux、Oracle Solaris、Microsoft Windows（Cygwin付き）
サイズ	1.3MB
利用可能	英語
タイプ	数理最適化ソフトウェア
ライセンス	ソース利用可能、学術研究には無料
Webサイト	www.math.uwaterloo.ca/tsp/concorde.html

Concorde TSP ソルバーは巡回セールスマン問題を解くプログラムです。David Applegate、Robert E. Bixby、Vašek Chvátal、William J. CookによってANSI Cで書かれており、学術的な使用には無料で利用できます。

コンコルドは、遺伝子マッピング、^[1]、タンパク質機能予測、^[2]、車両ルーティング、^[3]、ビットマップ画像から連続線画への変換、^[4]、地震調査のための船舶移動のスケジュール、^[5]、および組合せ最適化問題のスケーリング特性の研究などの問題に適用されています。^[6]

Mulder & Wunsch (2003) によると、コンコルドは「現在存在する大規模インスタンス用の最速の TSP ソルバーとして広く認められています。」2001 年、コンコルドはCMG が 1996 年に提起した車両ルーティング問題を解決したことで、CMGから5000ギルダーの賞金を獲得しました^。[7]

Concordeは線形計画法ソルバーを必要とし、QSopt ^[8]とCPLEX 8.0のみをサポートしています。

注記

^ ヒッテら（2003年）。
^ ジョンソン＆リュー（2006年）。
^ Applegateら（2002年）。
^ ボッシュ＆ハーマン（2004年）。
^ グティンら（2005）
^ アルダス＆パーカス（2003年）。
^ Whizzkids '96 車両ルーティング、コンコルドの Web サイトから、2008 年 8 月 26 日に取得。
^ 「QSopt 線形計画法ソルバー」。ウォータールー大学。 2023年10月28日閲覧。

参考文献

Aldous, David; Percus, Allon G. (2003)、「連続長組み合わせ最適化におけるスケーリングと普遍性」、Proc. Natl. Acad. Sci. USA、100 (20): 11211–11215、arXiv : cond-mat/0301035、Bibcode :2003PNAS..10011211A、doi : 10.1073/pnas.1635191100、PMC 208736、PMID 14504403。
Applegate, David; Cook, William; Dash, Sanjeeb; Rohe, André (2002)、「最小最大車両ルーティング問題の解決」、INFORMS Journal on Computing、14 (2): 132–143、doi :10.1287/ijoc.14.2.132.118。
ボッシュ、ロバート、ハーマン、エイドリアン (2004)、「巡回セールスマン問題による連続線描画」(PDF)、オペレーションズ・リサーチ・レター、32 (4): 302–303、doi :10.1016/j.orl.2003.10.001。
Gutin, Gregory; Jakubowicz, Helmut; Ronen, Shuki; Zverovitch, Alexei (2005)、「地震探査船問題」(PDF)、Communications in DQM、8 : 13–20。
Hitte, C.; Lorentzen, TD; Guyon, R.; Kim, L.; Cadieu, E.; Parker, HG; Quignon, P.; Lowe, JK; et al. (2003)、「放射線ハイブリッドマップの構築における MultiMap と TSP/CONCORDE の比較」、Journal of Heredity、94 (1): 9–13、doi : 10.1093/jhered/esg012、PMID 12692156。
ジョンソン、オリン、リュー、ジン (2006)、「タンパク質機能を予測するための巡回セールスマンアプローチ」、生物医学のためのソースコード、1 :3、doi : 10.1186/1751-0473-1-3、PMC 1636333、PMID 17147783。
Mulder, Samuel A.; Wunsch, Donald C., II (2003)、「適応共鳴ニューラルネットワークによる分割統治クラスタリングによる百万都市巡回セールスマン問題の解決」、Neural Networks、16 (5–6): 827–832、doi :10.1016/S0893-6080(03)00130-8、PMID 12850040{{citation}}: CS1 maint: 複数の名前: 著者リスト (リンク)。

外部リンク

コンコルドのウェブサイト
アリゾナ州立大学のコンコルドソルバーへのオンラインアクセス

[1] ヒッテら（2003年）。

[2] ジョンソン＆リュー（2006年）。

[3] Applegateら（2002年）。

[4] ボッシュ＆ハーマン（2004年）。

[5] グティンら（2005）

[6] アルダス＆パーカス（2003年）。

[7] Whizzkids '96 車両ルーティング、コンコルドの Web サイトから、2008 年 8 月 26 日に取得。

[8] 「QSopt 線形計画法ソルバー」。ウォータールー大学。 2023年10月28日閲覧。