AMPL (язык программирования)

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
AMPL
AMPL logo
Класс языка Мультипарадигма: Декларативный, Императивный
Появился в 1985; 39 лет назад (1985)
Разработчик AMPL Optimization, Inc.
Выпуск 20220323 (23 марта 2022; 2 года назад (2022-03-23))
Испытал влияние AWK, C
Повлиял на Pyomo
Лицензия Freemium (Транслятор),
Открытый исходный код (AMPL Библиотека Решателей)
Сайт ampl.com
ОС Cross-platform: Linux, macOS, Solaris, AIX, Windows

AMPL (аббревиатура от англ. A Mathematical Programming Language - язык математического программирования) — высокоуровневый язык алгебраического моделирования и представления крупномасштабных задач высокой сложности. AMPL разработан Робертом Фурером (Robert Fourer), Дэвидом Гэем(David Gay) и Брайаном Керниганом Brian Kernighan в Bell Laboratories в 1985 году для описания и решения сложных задач оптимизации и теории расписаний. Авторы AMPL в 1993 году были награждены премией Американского общества исследования операций (англ. Operations Research Society of America). AMPL не решает задачи непосредственно, а вызывает соответствующие внешние «решатели» как с открытым исходным кодом, так и коммерческого использования (CBC, CPLEX, FortMP, MINOS, IPOPT, SNOPT, KNITRO, and LGO). Задачи передаются решателям в виде nl-файлов. AMPL используется более чем 200 корпоративными клиентами, а также государственными учреждениями и академическими учреждениями. Одним из преимуществ AMPL является сходство его синтаксиса с математической записью задач оптимизации. Это позволяет дать очень краткое и легко читаемое определение задачи в области оптимизации. Многие современные решатели, доступные на NEOS Server (ранее размещенном в Аргонской национальной лаборатории (Argonne National Laboratory), в настоящее время размещенном в Университете Висконсина, Мэдисон University of Wisconsin, Madison[3]), принимают входные данные AMPL. Согласно статистике NEOS, AMPL является наиболее популярным форматом для представления задач математического программирования.

Функции

AMPL сочетает в себе декларативный и императивный стили программирования. Формулировка моделей оптимизации происходит с помощью элементов декларативного языка: наборов, скалярных и многомерных параметров, переменных решения, целевых функций и ограничений, которые позволяют кратко описать большинство задач в области математической оптимизации. Доступные в AMPL процедуры и операторы позволяют: - совершать обмен данными с внешними источниками данных, такими как электронные таблицы, базы данных, XML, CSV и текстовые файлы; - Выполнять предварительную и последующую обработку данных моделей оптимизации; - Развёртывать гибридные алгоритмы для решения типов задач, для которых нет прямых эффективных решателей; - Разделять модель и данные, что значительно упрощает повторное использование моделей и решений и упрощает построение крупномасштабных задач оптимизации;

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

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

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

Доступность

Информация о количестве задач, решаемых NEOS в период 2017-2021 гг.
Входная статистика NEOS за 2021 год.

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

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

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

История

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

Период Основные события
1985 г. AMPL был разработан и реализован [6]
1990 г. Статья с описанием языка моделирования AMPL была опубликована в журнале Management Science [7] .
1991 г. AMPL поддерживает нелинейное программирование и автоматическое дифференцирование
1993 г. Роберт Фурер, Дэвид Гей и Брайан Керниган были награждены премией ORSA/CSTS [8] Американским обществом исследования операций за работы по проектированию систем математического программирования и языка моделирования AMPL.
1995 г. Расширения для представления кусочно-линейных и сетевых структур
1995 г. Скриптовые конструкции
1997 г. Расширенная поддержка нелинейных решателей
1998 г. AMPL поддерживает проблемы теории дополнительности
2000 г. Доступ к реляционной базе данных и электронным таблицам
2002 г. Поддержка программирования ограничений [9]
2003 г. Компания AMPL Optimization LLC была основана изобретателями AMPL Робертом Фурером, Дэвидом Гэем и Брайаном Керниганом. Новая компания взяла на себя разработку и поддержку языка моделирования AMPL от Lucent Technologies, Inc.
2005 г. Открыта группа Google по языку моделирования AMPL [10]
2008 г. Kestrel: представлен интерфейс AMPL для сервера NEOS
2011 г. AMPL для курсов
2012 г. Роберт Фурер, Дэвид Гей и Брайан Керниган были удостоены премии INFORMS Impact Prize 2012 как создатели одного из самых важных языков алгебраического моделирования.[11]
2012 г. AMPL-книга становится бесплатным онлайн [12]
2012 г. AMPL «Логика» и расширения программирования с ограничениями
2013 г. Становится доступна новая кроссплатформенная интегрированная среда разработки (IDE) для AMPL [13]
2015 г. AMPL API для MATLAB
2016 г. AMPL-API для C++
2017 г. AMPL-API для Python
2018 г. AMPL-API для R
2020 г. Новый интерфейс электронных таблиц AMPL Direct
2022 г. Развертывание оптимизации в облачных средах и контейнерах

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

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

 set Plants;
 set Markets;

 # Capacity of plant p in cases
 param Capacity{p in Plants};

 # Demand at market m in cases
 param Demand{m in Markets};

 # Distance in thousands of miles
 param Distance{Plants, Markets};

 # Freight in dollars per case per thousand miles
 param Freight;

 # Transport cost in thousands of dollars per case
 param TransportCost{p in Plants, m in Markets} :=
   Freight * Distance[p, m] / 1000;

 # Shipment quantities in cases
 var shipment{Plants, Markets} >= 0;

 # Total transportation costs in thousands of dollars
 minimize cost:
   sum{p in Plants, m in Markets} TransportCost[p, m] * shipment[p, m];

 # Observe supply limit at plant p
 s.t. supply{p in Plants}: sum{m in Markets} shipment[p, m] <= Capacity[p];

 # Satisfy demand at market m
 s.t. demand{m in Markets}: sum{p in Plants} shipment[p, m] >= Demand[m];

 data;

 set Plants := seattle san-diego;
 set Markets := new-york chicago topeka;

 param Capacity :=
   seattle  350
   san-diego 600;

 param Demand :=
   new-york 325
   chicago 300
   topeka  275;

 param Distance : new-york chicago topeka :=
   seattle    2.5   1.7   1.8
   san-diego   2.5   1.8   1.4;

 param Freight := 90;

Решатели

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

Решатель Поддерживаемые типы проблем
APOPT смешанное целочисленное нелинейное программирование
Artelys Knitro линейное, квадратичное и нелинейное программирование
Bonmin смешанное целочисленное нелинейное программирование
BPMPD линейное и квадратичное программирование
COIN-OR CBC смешанное целочисленное программирование
COIN-OR CLP линейное программирование
CONOPT нелинейное программирование
Couenne [16] смешанное целочисленное нелинейное программирование (MINLP)
CPLEX линейное, квадратичное, конусное второго порядка и смешанное целочисленное программирование
CPLEX CP Optimizer [17] программирование ограничений
FILTER нелинейное программирование
FortMP линейное, квадратичное и смешанное целочисленное программирование
Gecode [18] программирование ограничений
IPOPT нелинейное программирование
JaCoP [19] программирование ограничений
LGO [20] глобальная и локальная нелинейная оптимизация
lp_solve [21] линейное и смешанное целочисленное программирование
MINOS линейное и нелинейное программирование
MINTO смешанное целочисленное программирование
MOSEK линейное, смешанное целочисленное линейное, квадратичное, смешанное целочисленное квадратичное, квадратично ограниченное, коническое и выпуклое нелинейное программирование
Octeract Engine Все типы задач оптимизации без дифференциальных или интегральных членов, включая разрывные задачи с min и max элементарными функциями.
SCIP смешанное целочисленное программирование
SNOPT нелинейное программирование
Sulum [22] линейное и смешанное целочисленное программирование
WORHP нелинейное программирование
XA линейное и смешанное целочисленное программирование
Xpress линейная и выпуклая квадратичная оптимизация и их смешанные целочисленные аналоги

Карта экосистемы

AMPL Ecosystem Map.pdf

Нажмите на карту, чтобы открыть ее интерактивную версию

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

  • sol (format)
  • GNU MathProg (ранее известный как GMPL) — это подмножество AMPL, поддерживаемое комплектом линейного программирования GNU [23] .

Рекомендации

Примечания

  1. ↑ Fourer (2002). «Extending an Algebraic Modeling Language to Support Constraint Programming». INFORMS Journal on Computing 14 (4): 322–344. doi:10.1287/ijoc.14.4.322.2825.
  2. ↑ Platforms. AMPL Optimizations Inc.. Дата обращения: 14 мая 2022. Архивировано 14 мая 2022 года.
  3. ↑ NEOS Server for Optimization. Дата обращения: 11 августа 2015. Архивировано 6 мая 2011 года.
  4. ↑ Try AMPL!. Дата обращения: 11 августа 2015. Архивировано 18 июня 2011 года.
  5. ↑ AMPL Downloads. Дата обращения: 11 августа 2015. Архивировано 26 мая 2015 года.
  6. ↑ Ошибка: не задан параметр |заглавие= в шаблоне {{публикация}}. — ISBN 978-0-534-38809-6.Fourer, Robert; Gay, David M; Kernighan, Brian W (2003). AMPL: a modeling language for mathematical programming. USA: Duxbury Press/Brooks/Cole Publishing Company. ISBN 978-0-534-38809-6.
  7. ↑ Fourer (1990). «A Modeling Language for Mathematical Programming». Management Science 36 (5): 519–554–83. doi:10.1287/mnsc.36.5.519.
  8. ↑ INFORMS. ICS - INFORMS. Дата обращения: 11 августа 2015. Архивировано 7 октября 2006 года.
  9. ↑ Fourer (2002). «Extending an Algebraic Modeling Language to Support Constraint Programming». INFORMS Journal on Computing 14 (4): 322–344. doi:10.1287/ijoc.14.4.322.2825.Fourer, Robert; Gay, David M. (2002). "Extending an Algebraic Modeling Language to Support Constraint Programming". INFORMS Journal on Computing. 14 (4): 322–344. CiteSeerX 10.1.1.8.9699. doi:10.1287/ijoc.14.4.322.2825.
  10. ↑ Google Groups. Дата обращения: 14 мая 2022. Архивировано 26 мая 2013 года.
  11. ↑ INFORMS. INFORMS Impact Prize. Дата обращения: 11 августа 2015. Архивировано 22 октября 2013 года.
  12. ↑ Freely downloadable - AMPL: A Modeling Language for Mathematical Programming. Дата обращения: 5 марта 2021. Архивировано 20 мая 2022 года.
  13. ↑ Google Groups. Дата обращения: 11 августа 2015. Архивировано 31 мая 2019 года.
  14. ↑ Ошибка: не задан параметр |заглавие= в шаблоне {{публикация}}. — ISBN 978-1-4008-8417-9.
  15. ↑ Solvers - AMPL. Дата обращения: 21 января 2018. Архивировано 27 февраля 2014 года.
  16. ↑ Couenne. Дата обращения: 27 октября 2013. Архивировано 29 октября 2013 года.
  17. ↑ mp/solvers/ilogcp at master · ampl/mp · GitHub. GitHub. Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
  18. ↑ mp/solvers/gecode at master · ampl/mp · GitHub. GitHub. Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
  19. ↑ mp/solvers/jacop at master · ampl/mp · GitHub. GitHub. Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
  20. ↑ LGO - AMPL. Дата обращения: 11 августа 2015. Архивировано 11 августа 2015 года.
  21. ↑ Using lpsolve from AMPL. Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
  22. ↑ mp/solvers/sulum at master · ampl/mp · GitHub. GitHub. Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
  23. ↑ GLPK official site. Дата обращения: 17 сентября 2020. Архивировано 30 мая 2022 года.

Внешние ссылки

Шаблон:Mathematical optimization software

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=AMPL_(язык_программирования)&oldid=3122500