AMPL (язык программирования)
AMPL | |
---|---|
Класс языка | Мультипарадигма: Декларативный, Императивный |
Появился в | 1985; 39 лет назад (1985) |
Разработчик | AMPL Optimization, Inc. |
Расширение файлов | .mod , .dat или .run |
Выпуск | 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 поддерживает широкий спектр типов задач, в том числе:
- Линейное программирование
- Квадратичное программирование
- Нелинейное программирование
- Смешанное целочисленное программирование
- Смешанно-целочисленное квадратичное программирование с выпуклыми квадратичными ограничениями или без них
- Смешанно-целочисленное нелинейное программирование
- Программирование конуса второго порядка
- Глобальная оптимизация
- Задачи полуопределенного программирования с билинейными матричными неравенствами
- Задачи теории дополнительности (MPEC) в дискретных или непрерывных переменных
- Программирование с ограничениями [1]
- Пользователь может прервать процесс решения в любое время
- Ошибки решателя не влияют на интерпретатор
- 32-битную версию AMPL можно использовать с 64-битным решателем и наоборот.
Взаимодействие с решателем осуществляется через четко определенный интерфейс nl .
Доступность
![]() | ![]() |
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 | линейная и выпуклая квадратичная оптимизация и их смешанные целочисленные аналоги |
Карта экосистемы
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/AMPL_Ecosystem_Map.pdf/page1-930px-AMPL_Ecosystem_Map.pdf.jpg)
Нажмите на карту, чтобы открыть ее интерактивную версию
Смотрите также
- sol (format)
- GNU MathProg (ранее известный как GMPL) — это подмножество AMPL, поддерживаемое комплектом линейного программирования GNU [23] .
Примечания
- ↑ Fourer, Robert (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.
- ↑ Platforms (неопр.). AMPL Optimizations Inc.. Дата обращения: 14 мая 2022. Архивировано 14 мая 2022 года.
- ↑ NEOS Server for Optimization (неопр.). Дата обращения: 11 августа 2015. Архивировано 6 мая 2011 года.
- ↑ Try AMPL! (неопр.) Дата обращения: 11 августа 2015. Архивировано 18 июня 2011 года.
- ↑ AMPL Downloads (неопр.). Дата обращения: 11 августа 2015. Архивировано из оригинала 26 мая 2015 года.
- ↑ Ошибка: не задан параметр
|заглавие =
в шаблоне {{публикация}}. — 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. - ↑ Fourer, Robert (1990). "A Modeling Language for Mathematical Programming" (PDF). Management Science. 36 (5): 519–554–83. doi:10.1287/mnsc.36.5.519. Архивировано (PDF) 16 июля 2011. Дата обращения: 14 мая 2022.
- ↑ INFORMS. ICS - INFORMS (неопр.). Дата обращения: 11 августа 2015. Архивировано 7 октября 2006 года.
- ↑ Fourer, Robert (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.
- ↑ Google Groups (неопр.). Дата обращения: 14 мая 2022. Архивировано 26 мая 2013 года.
- ↑ INFORMS. INFORMS Impact Prize (неопр.). Дата обращения: 11 августа 2015. Архивировано из оригинала 22 октября 2013 года.
- ↑ Freely downloadable - AMPL: A Modeling Language for Mathematical Programming (неопр.). Дата обращения: 5 марта 2021. Архивировано 20 мая 2022 года.
- ↑ Google Groups (неопр.). Дата обращения: 11 августа 2015. Архивировано 31 мая 2019 года.
- ↑ Ошибка: не задан параметр
|заглавие =
в шаблоне {{публикация}}. — ISBN 978-1-4008-8417-9. - ↑ Solvers - AMPL (неопр.). Дата обращения: 21 января 2018. Архивировано 27 февраля 2014 года.
- ↑ Couenne (неопр.). Дата обращения: 27 октября 2013. Архивировано из оригинала 29 октября 2013 года.
- ↑ mp/solvers/ilogcp at master · ampl/mp · GitHub (неопр.). GitHub. Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
- ↑ mp/solvers/gecode at master · ampl/mp · GitHub (неопр.). GitHub. Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
- ↑ mp/solvers/jacop at master · ampl/mp · GitHub (неопр.). GitHub. Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
- ↑ LGO - AMPL (неопр.). Дата обращения: 11 августа 2015. Архивировано 11 августа 2015 года.
- ↑ Using lpsolve from AMPL (неопр.). Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
- ↑ mp/solvers/sulum at master · ampl/mp · GitHub (неопр.). GitHub. Дата обращения: 11 августа 2015. Архивировано 14 мая 2022 года.
- ↑ GLPK official site (неопр.). Дата обращения: 17 сентября 2020. Архивировано 30 мая 2022 года.
Внешние ссылки
- ampl.com — официальный сайт AMPL
- проф. Домашняя страница Фуре в Северо-Западном университете
Шаблон:Mathematical optimization software