АМПЛ
Язык алгебраического моделирования

АМПЛ
ПарадигмаМультипарадигма : декларативная , императивная
РазработаноРоберт Фурер
Дэвид Гей
Брайан Керниган
Bell Labs
РазработчикAMPL Optimization, Inc.
Впервые появился1985 ; 40 лет назад ( 1985 )
Стабильный релиз
20230430 / 30 апреля 2023 г. ; 20 месяцев назад ( 2023-04-30 )
ОСКроссплатформенность : Linux , macOS , Solaris , AIX , Windows
ЛицензияЗапатентованная (транслятор),
бесплатная и с открытым исходным кодом (библиотека решателя AMPL)
Расширения имени файла.mod, .dat, .run
Веб-сайтwww.ampl.com
Под влиянием
АВК , С
Под влиянием
JuMP , Пиомо

AMPL ( язык математического программирования ) — это алгебраический язык моделирования для описания и решения сложных задач для крупномасштабных математических вычислений (например, крупномасштабных задач оптимизации и планирования ). [1] Он был разработан Робертом Фурером , Дэвидом Гэем и Брайаном Керниганом в Bell Laboratories . AMPL поддерживает десятки решателей , как с открытым исходным кодом , так и коммерческих , включая CBC, CPLEX , FortMP , MOSEK , MINOS , IPOPT , SNOPT , KNITRO и LGO. Задачи передаются решателям в виде файлов nl . AMPL используют более 100 корпоративных клиентов, а также государственные учреждения и академические институты. [2]

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

Функции

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

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

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

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

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

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

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

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

Доступность

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

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

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

История статусов

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

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

Образец модели

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

 установить Растения ; установить Рынки ;    # Мощность завода p в случаях параметр Мощность { p в ​​Растения };     # Спрос на рынке m в случаях param Demand { m in Markets };     # Расстояние в тысячах миль param Distance { Plants , Markets };    # Стоимость перевозки в долларах за ящик на тысячу миль param Freight ;   # Стоимость транспортировки в тысячах долларов за случай param TransportCost { p в ​​Plants , m в Markets } : = Груз * Расстояние [ p , m ] / 1000 ;               # Количество отгрузки в случаях var shipment { Plants , Markets } >= 0 ;      # Общие транспортные расходы в тысячах долларов минимизируем стоимость : сумма { p в Plants , m в Markets } TransportCost [ p , m ] * shipment [ p , m ];              # Соблюдайте лимит поставок на заводе p ст. поставка { p в ​​Заводах }: сумма { m в Рынках } отгрузка [ p , m ] <= Мощность [ p ];            # Удовлетворить спрос на рынке m ст. спрос { m в Рынках }: сумма { p в ​​Заводах } отгрузка [ p , m ] >= Спрос [ m ];            данные ; установить Растения : = Сиэтл Сан - Диего ; установить Рынки : = Нью - Йорк Чикаго Топика ;           параметр Вместимость : = сиэтл 350 сан - диего 600 ;       параметр Спрос : = нью - йорк 325 чикаго 300 топика 275 ;         param Расстояние : нью - йорк чикаго топика : = сиэтл 2,5 1,7 1,8 сан - диего 2,5 1,8 1,4 ;               параметр Грузовые перевозки : = 90 ;

Решатели

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

РешательПоддерживаемые типы проблем
АПОПТсмешанное целочисленное нелинейное программирование
Артелис Книтролинейное, квадратичное и нелинейное программирование
Бонминсмешанное целочисленное нелинейное программирование
БПМПДлинейное и квадратичное программирование
МОНЕТА-ИЛИ CBCсмешанное целочисленное программирование
МОНЕТА-ИЛИ CLPлинейное программирование
КОНОПТнелинейное программирование
Куэнн [17]смешанное целочисленное нелинейное программирование (MINLP)
CPLEXлинейное, квадратичное, конусное программирование второго порядка и смешанное целочисленное программирование
CPLEX CP-оптимизатор [18]программирование ограничений
ФИЛЬТРнелинейное программирование
ФортМПлинейное, квадратичное и смешанное целочисленное программирование
Гекод [19]программирование ограничений
ИПОПТнелинейное программирование
ЯКоП [20]программирование ограничений
ЛГО [21]глобальная и локальная нелинейная оптимизация
lp_solve [22]линейное и смешанное целочисленное программирование
МИНОСлинейное и нелинейное программирование
МИНТОсмешанное целочисленное программирование
МОСЭКлинейное, смешанное целочисленное линейное, квадратичное, смешанное целочисленное квадратичное, квадратично ограниченное , коническое и выпуклое нелинейное программирование
Двигатель OcteractВсе типы задач оптимизации без дифференциальных или интегральных членов, включая разрывные задачи с минимальными и максимальными элементарными функциями.
СКИПсмешанное целочисленное программирование
СНОПТнелинейное программирование
Сулум [23]линейное и смешанное целочисленное программирование
WORHPнелинейное программирование
ХАлинейное и смешанное целочисленное программирование
Экспресслинейная и выпуклая квадратичная оптимизация и их смешанные целочисленные аналоги

Смотрите также

Ссылки

  1. ^ ab Fourer, Robert ; Gay, David M; Kernighan, Brian W (2003). AMPL: язык моделирования для математического программирования . США: Duxbury Press/Brooks/Cole Publishing Company. ISBN 978-0-534-38809-6.
  2. ^ "Position Available". Архивировано из оригинала 11 сентября 2011 года . Получено 29 июля 2011 года .
  3. ^ "О нас" . Получено 11 августа 2015 г.
  4. ^ ab Fourer, Robert ; Gay, David M. (2002). «Расширение языка алгебраического моделирования для поддержки программирования в ограничениях». INFORMS Journal on Computing . 14 (4): 322– 344. CiteSeerX 10.1.1.8.9699 . doi :10.1287/ijoc.14.4.322.2825. 
  5. ^ "Платформы". AMPL Optimizations Inc. Архивировано из оригинала 14 мая 2022 г. Получено 1 ноября 2019 г.
  6. ^ "NEOS Server for Optimization" . Получено 11 августа 2015 г. .
  7. ^ "Попробуйте AMPL!" . Получено 11 августа 2015 г.
  8. ^ "AMPL Downloads". Архивировано из оригинала 26 мая 2015 г. Получено 11 августа 2015 г.
  9. ^ Фоурер, Роберт ; Гей, Дэвид М.; Керниган, Брайан В. (1990). «Язык моделирования для математического программирования» (PDF) . Наука управления . 36 (5): 519–554–83. doi :10.1287/mnsc.36.5.519.
  10. ^ ИНФОРМ. "ICS - INFORMS" (PDF) . Архивировано из оригинала (PDF) 7 октября 2006 года . Получено 11 августа 2015 года .
  11. ^ «Группы Google».
  12. ^ INFORMS. "INFORMS Impact Prize". Архивировано из оригинала 22 октября 2013 года . Получено 11 августа 2015 года .
  13. ^ "Книга AMPL: Полное руководство по построению моделей оптимизации для начинающих и опытных пользователей" . Получено 5 марта 2021 г.
  14. ^ "Google Groups" . Получено 11 августа 2015 г.
  15. ^ Данциг, Джордж (2016) [1963]. "3. Формулирование модели линейного программирования". Линейное программирование и расширения . Princeton University Press. стр.  32–62 . ISBN 978-1-4008-8417-9.
  16. ^ "Solvers - AMPL". Архивировано из оригинала 27 февраля 2014 года . Получено 21 января 2018 года .
  17. ^ "Couenne". Архивировано из оригинала 29 октября 2013 года . Получено 27 октября 2013 года .
  18. ^ "mp/solvers/ilogcp at master · ampl/mp · GitHub". GitHub . Получено 11 августа 2015 г. .
  19. ^ "mp/solvers/gecode at master · ampl/mp · GitHub". GitHub . Получено 11 августа 2015 г. .
  20. ^ "mp/solvers/jacop at master · ampl/mp · GitHub". GitHub . Получено 11 августа 2015 г. .
  21. ^ "LGO - AMPL" . Получено 11 августа 2015 г. .
  22. ^ "Использование lpsolve из AMPL" . Получено 11 августа 2015 г.
  23. ^ "mp/solvers/sulum at master · ampl/mp · GitHub". GitHub . Получено 11 августа 2015 г. .
  24. ^ "Официальный сайт GLPK" . Получено 17 сентября 2020 г.
Взято с "https://en.wikipedia.org/w/index.php?title=AMPL&oldid=1250201002"