Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

AMPL
AMPL (обложка учебника) .jpg
ПарадигмаМультипарадигма : декларативная , императивная
РазработаноРоберт Фурер
Дэвид Гей
Брайан Керниган
Bell Labs
РазработчикAMPL Optimization, Inc.
Впервые появился1985 ; 36 лет назад ( 1985 )
Стабильный выпуск
20131012/12 октября 2013 г . ; 7 лет назад ( 2013-10-12 )
Операционные системыКроссплатформенность : Linux , macOS , Solaris , AIX , Windows
ЛицензияСобственная (переводчик),
бесплатная и с открытым исходным кодом (AMPL Solver Library)
Расширения имени файла.mod, .dat, .run
Интернет сайтwww .ampl .com
Под влиянием
AWK , C
Под влиянием
Pyomo

AMPL ( математический язык программирования ) - это язык алгебраического моделирования для описания и решения задач высокой сложности для крупномасштабных математических вычислений (например, крупномасштабных задач оптимизации и планирования ). [1] Его разработали Роберт Фурер , Дэвид Гей и Брайан Керниган в Bell Laboratories . AMPL поддерживает десятки решателей , как с открытым исходным кодом, так и с коммерческим программным обеспечением , включая CBC, CPLEX , FortMP , Gurobi , MINOS , IPOPT ,СНОПТ , КНИТРО , ЛГО . Проблемы передаются решателям в виде файлов nl . AMPL используют более 100 корпоративных клиентов, а также правительственные учреждения и академические учреждения. [2]

Одним из преимуществ AMPL является сходство его синтаксиса с математической записью задач оптимизации . Это позволяет дать очень краткое и удобочитаемое определение проблем в области оптимизации . Многие современные решатели, доступные на сервере NEOS (ранее размещенном в Аргоннской национальной лаборатории , а в настоящее время - в Университете Висконсина, Мэдисон [3] ), принимают входные данные AMPL. Согласно статистике NEOS, AMPL - самый популярный формат для представления задач математического программирования.

Особенности [ править ]

AMPL представляет собой сочетание декларативного и императивного стилей программирования. Формулирование моделей оптимизации происходит с помощью элементов декларативного языка, таких как множества, скалярные и многомерные параметры, переменные решения, цели и ограничения , которые позволяют кратко описать большинство проблем в области математической оптимизации.

Процедуры и операторы потока управления доступны в AMPL для

  • обмен данными с внешними источниками данных, такими как электронные таблицы , базы данных , XML и текстовые файлы
  • задачи предварительной и постобработки данных вокруг моделей оптимизации
  • построение гибридных алгоритмов для типов задач, для которых нет прямых эффективных решателей.

Для поддержки повторного использования и упрощения построения крупномасштабных задач оптимизации AMPL позволяет разделить модель и данные.

AMPL поддерживает широкий спектр типов задач, среди которых:

  • Линейное программирование
  • Квадратичное программирование
  • Нелинейное программирование
  • Смешанное целочисленное программирование
  • Смешанно-целочисленное квадратичное программирование с выпуклыми квадратичными ограничениями или без них
  • Смешано-целочисленное нелинейное программирование
  • Программирование конуса второго порядка
  • Глобальная оптимизация
  • Задачи полуопределенного программирования с билинейными матричными неравенствами
  • Проблемы теории дополнительности (MPEC) в дискретных или непрерывных переменных
  • Программирование в ограничениях [4]

AMPL вызывает решатель в отдельном процессе, который имеет следующие преимущества:

  • Пользователь может в любой момент прервать процесс решения
  • Ошибки решателя не влияют на интерпретатор
  • 32-битная версия AMPL может использоваться с 64-битным решателем и наоборот.

Взаимодействие с решателем осуществляется через четко определенный интерфейс nl .

Доступность [ править ]

Статистика ввода NEOS за январь 2011 г.

AMPL доступен для многих популярных 32- и 64-разрядных операционных систем, включая Linux , macOS , Solaris , AIX и Windows . [5] Переводчик представляет собой проприетарное программное обеспечение, поддерживаемое AMPL Optimization LLC. Однако существует несколько онлайн-сервисов, предоставляющих бесплатные средства моделирования и решения с использованием AMPL. [6] [7] Также доступны бесплатная студенческая версия с ограниченной функциональностью и бесплатная полнофункциональная версия для академических курсов. [8]

AMPL можно использовать из Microsoft Excel через надстройку SolverStudio Excel.

Библиотека решателя AMPL (ASL), которая позволяет читать файлы nl и обеспечивает автоматическое различение, является открытым исходным кодом. Он используется во многих решателях для реализации AMPL-соединения.

История статуса [ править ]

В этой таблице представлены важные шаги в истории AMPL.

ГодОсобенности
1985 г.AMPL был разработан и реализован [1]
1990 г.Статья с описанием языка моделирования AMPL была опубликована в Management Science [9].
1991 г.AMPL поддерживает нелинейное программирование и автоматическое дифференцирование
1993 г.Роберт Форер , Дэвид Гей и Брайан Керниган были награждены ORSA / CSTS премии [10] от Исследовательского общества операций Америки , для сочинения по проектированию математических систем программирования и моделирования языка AMPL
1995 г.Расширения для представления кусочно-линейных и сетевых структур
1995 г.Скриптовые конструкции
1997 г.Расширенная поддержка нелинейных решателей
1998 г.AMPL поддерживает проблемы теории дополнительности
2000 г.Доступ к реляционной базе данных и электронным таблицам
2002 г.Поддержка программирования ограничений [4]
2003 г.Компания AMPL Optimization LLC была основана изобретателями AMPL Робертом Фурером, Дэвидом Гей и Брайаном Керниганом. Новая компания взяла на себя разработку и поддержку языка моделирования AMPL от Lucent Technologies, Inc .
2005 г.Открыта группа Google по языку моделирования AMPL [11]
2008 г.Kestrel: представлен интерфейс AMPL для сервера NEOS
2012 г.Роберт Фурер , Дэвид Гей и Брайан Керниган были удостоены премии INFORMS Impact Prize 2012 года как создатели одного из важнейших языков алгебраического моделирования. [12]
2012 г.Книга AMPL стала доступной онлайн
2013Доступна новая кросс-платформенная интегрированная среда разработки (IDE) для AMPL [13]

Образец модели [ править ]

Проблема транспортировки от Джорджа Данцига используется для предоставления образца модели AMPL. Эта задача позволяет найти график отгрузки с наименьшими затратами, который соответствует требованиям на рынках и поставкам на заводах. [14]

 набор  растений ; установить рынки ;   # Производительность установки p в случаях param Capacity { p in Plants };     # Спрос на рынке m в случаях param Demand { m in Markets };     # Расстояние в тысячах миль param Distance { Plants , Markets };    # Фрахт в долларах за ящик за тысячу миль param Freight ;   # Транспортные расходы в тысячах долларов за ящик param TransportCost { p на заводах , м на рынках } : = фрахт * расстояние [ p , м ] / 1000 ;               # Количество отгрузки в случаях var shipment { Plants , Markets } > = 0 ;      # Общие затраты на транспортировку в тысячах долларов минимизируют затраты : сумма { p в заводах , m в рынках } TransportCost [ p , m ] * отгрузка [ p , m ];              # Соблюдайте лимит подачи на заводе p s.t. поставка { p на заводах }: сумма { m на рынках } отгрузка [ p , m ] <= мощность [ p ];            # Удовлетворение спроса на рынке m s.t. спрос { m на рынках }: сумма { p на заводах } отгрузка [ p , m ] > = спрос [ m ];            данные ; набор  Plants : = сиэтл сан - диего ; set Markets : = new - york chicago topeka ;          param  Вместимость : = сиэтл 350 сан - диего 600 ;      param  Спрос : = new - york 325 chicago 300 topeka 275 ;        param  Расстояние : нью - йорк чикаго топика : = сиэтл 2,5 1,7 1,8 сан - диего 2,5 1,8 1,4 ;              param  Freight : = 90 ;

Решатели [ править ]

Вот неполный список решателей, поддерживаемых AMPL: [15]

РешательПоддерживаемые типы проблем
APOPTсмешанное целочисленное нелинейное программирование
Artelys Knitroлинейное, квадратичное и нелинейное программирование
Бонминсмешанное целочисленное нелинейное программирование
BPMPDлинейное и квадратичное программирование
МОНЕТА-ИЛИ CBCсмешанное целочисленное программирование
МОНЕТА-ИЛИ CLPлинейное программирование
КОНОПТнелинейное программирование
Куэнн [16]смешанное целочисленное нелинейное программирование (MINLP)
CPLEXлинейное, квадратичное, конусное программирование второго порядка и смешанное целочисленное программирование
Оптимизатор CPLEX CP [17]программирование в ограничениях
ФИЛЬТРнелинейное программирование
FortMPлинейное, квадратичное и смешанное целочисленное программирование
Gecode [18]программирование в ограничениях
Гуробилинейное, квадратичное, конусное программирование второго порядка и смешанное целочисленное программирование
IPOPTнелинейное программирование
JaCoP [19]программирование в ограничениях
LGO [20]глобальная и локальная нелинейная оптимизация
lp_solve [21]линейное и смешанное целочисленное программирование
МИНОСлинейное и нелинейное программирование
MINTOсмешанное целочисленное программирование
МОСЕКлинейное, смешанное целочисленное линейное, квадратичное, смешанное целочисленное квадратичное, квадратично ограниченное , коническое и выпуклое нелинейное программирование
Octeract EngineВсе типы задач оптимизации без дифференциальных или интегральных членов, включая разрывные задачи с минимальными и максимальными элементарными функциями.
SCIPсмешанное целочисленное программирование
СНОПТнелинейное программирование
Сулум [22]линейное и смешанное целочисленное программирование
WORHPнелинейное программирование
XAлинейное и смешанное целочисленное программирование
Xpressлинейная и выпуклая квадратичная оптимизация и их смешанные целочисленные аналоги

См. Также [ править ]

  • sol (формат)
  • GNU MathProg (ранее известный как GMPL) - это подмножество AMPL, поддерживаемое GNU Linear Programming Kit [23]

Ссылки [ править ]

  1. ^ a b Фурер, Роберт ; Гей, Дэвид М ; Керниган, Брайан В. (2003). AMPL: язык моделирования для математического программирования . США: Duxbury Press / Brooks / Cole Publishing Company. ISBN 978-0-534-38809-6.
  2. ^ «Доступная позиция» . Проверено 29 июля 2011 года .
  3. ^ "О" . Дата обращения 11 августа 2015 .
  4. ^ a b Фурер, Роберт ; Гей, Дэвид М. (2002). «Расширение языка алгебраического моделирования для поддержки программирования с ограничениями» . ИНФОРМС Журнал по вычислительной технике . 14 (4): 322–344. CiteSeerX 10.1.1.8.9699 . DOI : 10.1287 / ijoc.14.4.322.2825 . 
  5. ^ «Платформы» . AMPL Оптимизация Inc .
  6. ^ «Сервер NEOS для оптимизации» . Дата обращения 11 августа 2015 .
  7. ^ "Попробуйте AMPL!" . Дата обращения 11 августа 2015 .
  8. ^ "Загрузки AMPL" . Архивировано из оригинального 26 мая 2015 года . Дата обращения 11 августа 2015 .
  9. ^ Фурер, Роберт ; Гей, Дэвид М .; Керниган, Брайан В. (1990). «Язык моделирования для математического программирования» (PDF) . Наука управления . 36 (5): 519–554–83. DOI : 10.1287 / mnsc.36.5.519 .
  10. ^ ИНФОРМАЦИЯ. «ИКС - ИНФОРМС» (PDF) . Дата обращения 11 августа 2015 .
  11. ^ "Группы Google" .
  12. ^ ИНФОРМАЦИЯ. «Приз INFORMS Impact» . Архивировано из оригинального 22 октября 2013 года . Дата обращения 11 августа 2015 .
  13. ^ "Группы Google" . Дата обращения 11 августа 2015 .
  14. ^ Данциг, Джордж (2016) [1963]. «3. Формулировка модели линейного программирования» . Линейное программирование и расширения . Издательство Принстонского университета. С. 32–62. ISBN 978-1-4008-8417-9.
  15. ^ "Решатели - AMPL" . Проверено 21 января 2018 .
  16. ^ "Couenne" . Архивировано из оригинального 29 октября 2013 года . Проверено 27 октября 2013 года .
  17. ^ "mp / solvers / ilogcp at master · amp / mp · GitHub" . GitHub . Дата обращения 11 августа 2015 .
  18. ^ "mp / solvers / gecode at master · amp / mp · GitHub" . GitHub . Дата обращения 11 августа 2015 .
  19. ^ "mp / solvers / jacop at master · amp / mp · GitHub" . GitHub . Дата обращения 11 августа 2015 .
  20. ^ "LGO - AMPL" . Дата обращения 11 августа 2015 .
  21. ^ "Использование lpsolve из AMPL" . Дата обращения 11 августа 2015 .
  22. ^ "mp / solvers / sulum at master · amp / mp · GitHub" . GitHub . Дата обращения 11 августа 2015 .
  23. ^ "Официальный сайт ГЛПК" . Проверено 17 сентября 2020 года .

Внешние ссылки [ править ]

  • Официальный веб-сайт
  • Домашняя страница профессора Фурера в Северо-Западном университете