AMPL
 | |
| Парадигма | Мультипарадигмальность : декларативная , императивная. |
|---|---|
| Разработано | Роберт Фурер Дэвид Гей Брайан Керниган Белл Лаборатории |
| Разработчик | AMPL Оптимизация, Inc. |
| Впервые появился | 1985 год |
| Стабильная версия | 20230430
/ 30 апреля 2023 г |
| ТЫ | Кроссплатформенность : Linux , macOS , Solaris , AIX , Windows. |
| Лицензия | Собственный (переводчик), бесплатный и с открытым исходным кодом (библиотека решателей AMPL) |
| Расширения имен файлов | .mod, .dat, .run |
| Веб-сайт | www |
| Под влиянием | |
| АВК , С | |
| Под влиянием | |
| Пёмо | |
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 поддерживает широкий спектр типов задач, среди них:
- Линейное программирование
- Квадратичное программирование
- Нелинейное программирование
- Смешанно-целочисленное программирование
- Смешанно-целочисленное квадратичное программирование с выпуклыми квадратичными ограничениями или без них
- Смешанно-целочисленное нелинейное программирование
- Программирование конуса второго порядка
- Глобальная оптимизация
- Задачи полуопределенного программирования с билинейными матричными неравенствами
- Проблемы теории дополнительности (MPEC) в дискретных или непрерывных переменных
- Программирование ограничений [4]
AMPL вызывает решатель в отдельном процессе, который имеет следующие преимущества:
- Пользователь может прервать процесс решения в любой момент
- Ошибки решателя не влияют на интерпретатор
- 32-битную версию AMPL можно использовать с 64-битным решателем и наоборот.
Взаимодействие с решателем осуществляется через четко определенный интерфейс nl .
Наличие [ править ]
AMPL доступен для многих популярных 32- и 64-разрядных операционных систем, включая Linux , macOS , Solaris , AIX и Windows . [5] Переводчик является проприетарным программным обеспечением, поддерживаемым ООО «АМПЛ Оптимизация». Однако существует несколько онлайн-сервисов, предоставляющих бесплатные средства моделирования и решения с использованием 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 становится бесплатной в Интернете [13] |
| 2013 | Становится доступной новая кроссплатформенная интегрированная среда разработки (IDE) для AMPL. [14] |
Пример модели [ править ]
Транспортная задача Джорджа Данцига используется для создания примера модели AMPL. Эта задача позволяет найти наименее затратный график поставок, отвечающий потребностям рынков и поставкам на заводах. [15]
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: [16]
| Решатель | Поддерживаемые типы проблем |
|---|---|
| АПОПТ | смешанное целочисленное нелинейное программирование |
| Артелис Книтро | линейное, квадратичное и нелинейное программирование |
| Бонмин | смешанное целочисленное нелинейное программирование |
| БПМПД | линейное и квадратичное программирование |
| МОНЕТА-ИЛИ CBC | смешанное целочисленное программирование |
| МОНЕТА-ИЛИ CLP | линейное программирование |
| КОНОПТ | нелинейное программирование |
| Ринд [17] | смешанное целочисленное нелинейное программирование (MINLP) |
| Комплексный комплекс | линейное, квадратичное, конусное программирование второго порядка и смешанное целочисленное программирование |
| CPLEX CP Оптимизатор [18] | программирование ограничений |
| ФИЛЬТР | нелинейное программирование |
| ФортМП | линейное, квадратичное и смешанное целочисленное программирование |
| Закодированный [19] | программирование ограничений |
| ИПОРТ | нелинейное программирование |
| ДаКоП [20] | программирование ограничений |
| ЛГО [21] | глобальная и локальная нелинейная оптимизация |
| lp_solve [22] | линейное и смешанное целочисленное программирование |
| МИНОС | линейное и нелинейное программирование |
| МИНТО | смешанное целочисленное программирование |
| МОИСЕЙ | линейное, смешанное целочисленное линейное, квадратичное, смешанное целочисленное, квадратичное, квадратично ограниченное , коническое и выпуклое нелинейное программирование |
| Октерактовый движок | Все типы задач оптимизации без дифференциальных или интегральных членов, включая разрывные задачи с минимальными и максимальными элементарными функциями. |
| SCIP | смешанное целочисленное программирование |
| СНОПТ | нелинейное программирование |
| Каждый раз [23] | линейное и смешанное целочисленное программирование |
| ВОРХП | нелинейное программирование |
| ШАХ | линейное и смешанное целочисленное программирование |
| Экспресс | линейная и выпуклая квадратичная оптимизация и их смешанные целочисленные аналоги |
См. также [ править ]
- соль (формат)
- GNU MathProg (ранее известный как GMPL) — это подмножество AMPL, поддерживаемое GNU Linear Programming Kit. [24]
Ссылки [ править ]
- ^ Перейти обратно: а б Фурер, Роберт ; Гей, Дэвид М; Керниган, Брайан В. (2003). AMPL: язык моделирования для математического программирования . США: Duxbury Press/Brooks/Cole Publishing Company. ISBN 978-0-534-38809-6 .
- ^ «Доступная позиция» . Архивировано из оригинала 11 сентября 2011 года . Проверено 29 июля 2011 г.
- ^ "О" . Проверено 11 августа 2015 г.
- ^ Перейти обратно: а б Фурер, Роберт ; Гей, Дэвид М. (2002). «Расширение языка алгебраического моделирования для поддержки программирования с ограничениями» . ИНФОРМС Журнал по вычислительной технике . 14 (4): 322–344. CiteSeerX 10.1.1.8.9699 . дои : 10.1287/ijoc.14.4.322.2825 .
- ^ «Платформы» . AMPL Optimizations Inc. Архивировано из оригинала 14 мая 2022 года . Проверено 1 ноября 2019 г.
- ^ «Сервер NEOS для оптимизации» . Проверено 11 августа 2015 г.
- ^ «Попробуй AMPL!» . Проверено 11 августа 2015 г.
- ^ «Загрузки AMPL» . Архивировано из оригинала 26 мая 2015 года . Проверено 11 августа 2015 г.
- ^ Фурер, Роберт ; Гей, Дэвид М.; Керниган, Брайан В. (1990). «Язык моделирования для математического программирования» (PDF) . Наука управления . 36 (5): 519–554–83. дои : 10.1287/mnsc.36.5.519 .
- ^ ИНФОРМ. «ИКС-ИНФОРМС» (PDF) . Архивировано из оригинала (PDF) 7 октября 2006 года . Проверено 11 августа 2015 г.
- ^ «Группы Google» .
- ^ ИНФОРМ. «Приз ИНФОРМС Импакт» . Архивировано из оригинала 22 октября 2013 года . Проверено 11 августа 2015 г.
- ^ «Книга AMPL: комплексное руководство по построению моделей оптимизации для начинающих и опытных пользователей» . Проверено 5 марта 2021 г.
- ^ «Группы Google» . Проверено 11 августа 2015 г.
- ^ Данциг, Джордж (2016) [1963]. «3. Формулирование модели линейного программирования» . Линейное программирование и расширения . Издательство Принстонского университета. стр. 32–62. ISBN 978-1-4008-8417-9 .
- ^ «Решатели – AMPL» . Архивировано из оригинала 27 февраля 2014 года . Проверено 21 января 2018 г.
- ^ «Куэнн» . Архивировано из оригинала 29 октября 2013 года . Проверено 27 октября 2013 г.
- ^ «mp/solvers/ilogcp в мастере · ampl/mp · GitHub» . Гитхаб . Проверено 11 августа 2015 г.
- ^ «mp/solvers/gecode at master · ampl/mp · GitHub» . Гитхаб . Проверено 11 августа 2015 г.
- ^ «mp/solvers/jacop at master · ampl/mp · GitHub» . Гитхаб . Проверено 11 августа 2015 г.
- ^ «ЛГО-АМПЛ» . Проверено 11 августа 2015 г.
- ^ «Использование lpsolve из AMPL» . Проверено 11 августа 2015 г.
- ^ «mp/solvers/sulum at master · ampl/mp · GitHub» . Гитхаб . Проверено 11 августа 2015 г.
- ^ «Официальный сайт ГЛПК» . Проверено 17 сентября 2020 г.
Внешние ссылки [ править ]
- программное обеспечение 1990 года
- Системы компьютерной алгебры
- Математическое моделирование
- Программное обеспечение для математической оптимизации
- Языки числового программирования
- Языки сценариев
- Текстоориентированные языки программирования
- Языки программирования, созданные в 1985 году.
- Собственное кроссплатформенное программное обеспечение.