Решатель Concorde TSP
| Оригинальный автор(ы) | Дэвид Эпплгейт , Роберт Биксби , Вацлав Хватал , Уильям Дж. Кук |
|---|---|
| Первоначальный выпуск | 27 августа 1997 г |
| Стабильная версия | 03.12.19 / 19 декабря 2003 г |
| Репозиторий | www |
| Написано в | С |
| Операционная система | Linux , Oracle Solaris , Microsoft Windows (с Cygwin ) |
| Размер | 1,3 МБ |
| Доступно в | Английский |
| Тип | Программное обеспечение для математической оптимизации |
| Лицензия | Исходный код доступен , бесплатен для академических исследований. |
| Веб-сайт | www |
Concorde TSP Solver — это программа для решения задачи коммивояжера . Он был написан Дэвидом Эпплгейтом , Робертом Э. Биксби , Вашеком Хваталом и Уильямом Дж. Куком на языке ANSI C и находится в свободном доступе для академического использования.
Concorde применялся к проблемам картирования генов . [1] прогнозирование функции белка , [2] маршрутизация транспортных средств , [3] преобразование растровых изображений в непрерывные линейные рисунки, [4] планирование движения судов для сейсмических исследований, [5] и при изучении масштабирующих свойств задач комбинаторной оптимизации. [6]
По данным Mulder & Wunsch (2003) , Concorde «широко считается самым быстрым решателем TSP для крупных случаев из существующих в настоящее время». В 2001 году Concorde выиграла приз в размере 5000 гульденов от CMG за решение проблемы маршрутизации транспортных средств, которую компания поставила в 1996 году. [7]
Concorde требует решателя линейного программирования и поддерживает только QSopt. [8] и КПЛЕКС 8.0.
Примечания
[ редактировать ]- ^ Хитте и др. (2003) .
- ^ Джонсон и Лю (2006) .
- ^ Эпплгейт и др. (2002) .
- ^ Босх и Герман (2004) .
- ^ Гутин и др. (2005)
- ^ Олдос и Перкус (2003) .
- ^ Маршрут автомобиля Whizzkids '96 , с веб-сайта Concorde, получено 26 августа 2008 г.
- ^ «Решатель линейного программирования QSopt» . Университет Ватерлоо . Проверено 28 октября 2023 г.
Ссылки
[ редактировать ]- Олдос, Дэвид; Перкус, Аллон Г. (2003), «Масштабирование и универсальность в комбинаторной оптимизации непрерывной длины», Proc. Натл. акад. наук. США , 100 (20): 11211–11215, arXiv : cond-mat/0301035 , Bibcode : 2003PNAS..10011211A , doi : 10.1073/pnas.1635191100 , PMC 208736 , PMID 14504403 .
- Эпплгейт, Дэвид; Кук, Уильям; Дэш, Санджиб; Роэ, Андре (2002), «Решение задачи минимального и максимального выбора маршрута транспортного средства», журнал INFORMS Journal on Computing , 14 (2): 132–143, doi : 10.1287/ijoc.14.2.132.118 .
- Босх, Роберт; Герман, Адрианна (2004), «Непрерывные линейные рисунки с помощью задачи коммивояжера» (PDF) , Operations Research Letters , 32 (4): 302–303, doi : 10.1016/j.orl.2003.10.001 .
- Гутин, Григорий; Якубович, Гельмут; Ронен, Шуки; Зверович, Алексей (2005), «Проблема сейсмического судна» (PDF) , Коммуникации в DQM , 8 : 13–20 .
- Хитте, К.; Лоренцен, Т.Д.; Гийон, Р.; Ким, Л.; Кадье, Э.; Паркер, Х.Г.; Киньон, П.; Лоу, Дж. К.; и др. (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 .
- Малдер, Сэмюэл А.; Вунш, Дональд К., II (2003), «Решение проблемы коммивояжера в миллион городов путем кластеризации «разделяй и властвуй» с помощью адаптивных резонансных нейронных сетей», Neural Networks , 16 (5–6): 827–832, doi : 10.1016/S0893- 6080(03)00130-8 , ПМИД 12850040
{{citation}}: CS1 maint: несколько имен: список авторов ( ссылка ) .