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.
Роберт Фурер, Дэвид Гей и Брайан Керниган были награждены премией ORSA/CSTS [8] Американским обществом исследования операций за работы по проектированию систем математического программирования и языка моделирования AMPL.
1995 г.
Расширения для представления кусочно-линейных и сетевых структур
1995 г.
Скриптовые конструкции
1997 г.
Расширенная поддержка нелинейных решателей
1998 г.
AMPL поддерживает проблемы теории дополнительности
2000 г.
Доступ к реляционной базе данных и электронным таблицам
Компания AMPL Optimization LLC была основана изобретателями AMPL Робертом Фурером, Дэвидом Гэем и Брайаном Керниганом. Новая компания взяла на себя разработку и поддержку языка моделирования AMPL от Lucent Technologies, Inc.
2005 г.
Открыта группа Google по языку моделирования AMPL [10]
2008 г.
Kestrel: представлен интерфейс AMPL для сервера NEOS
2011 г.
AMPL для курсов
2012 г.
Роберт Фурер, Дэвид Гей и Брайан Керниган были удостоены премии INFORMS Impact Prize 2012 как создатели одного из самых важных языков алгебраического моделирования.[11]
Развертывание оптимизации в облачных средах и контейнерах
Образец модели
Транспортная задача от Джорджа Данцига используется для предоставления примера модели AMPL. Эта задача находит наименее затратный график отгрузки, который удовлетворяет требованиям на рынках и поставкам на заводах.[14]
setPlants;setMarkets;# Capacity of plant p in casesparamCapacity{pinPlants};# Demand at market m in casesparamDemand{minMarkets};# Distance in thousands of milesparamDistance{Plants,Markets};# Freight in dollars per case per thousand milesparamFreight;# Transport cost in thousands of dollars per caseparamTransportCost{pinPlants,minMarkets}:=Freight*Distance[p,m]/1000;# Shipment quantities in casesvarshipment{Plants,Markets}>=0;# Total transportation costs in thousands of dollarsminimizecost:sum{pinPlants,minMarkets}TransportCost[p,m]*shipment[p,m];# Observe supply limit at plant ps.t.supply{pinPlants}:sum{minMarkets}shipment[p,m]<=Capacity[p];# Satisfy demand at market ms.t.demand{minMarkets}:sum{pinPlants}shipment[p,m]>=Demand[m];data;setPlants:=seattlesan-diego;setMarkets:=new-yorkchicagotopeka;paramCapacity:=seattle350san-diego600;paramDemand:=new-york325chicago300topeka275;paramDistance:new-yorkchicagotopeka:=seattle2.51.71.8san-diego2.51.81.4;paramFreight:=90;
Решатели
Вот неполный список решателей, поддерживаемых AMPL:[15]
