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), принимают входные данные AMPL. Согласно статистике NEOS, AMPL является наиболее популярным форматом для представления задач математического программирования.
Функции AMPL сочетает в себе декларативный и императивный стили программирования. Формулировка моделей оптимизации происходит с помощью элементов декларативного языка: наборов, скалярных и многомерных параметров, переменных решения, целевых функций и ограничений, которые позволяют кратко описать большинство задач в области математической оптимизации. Доступные в AMPL процедуры и операторы позволяют: - совершать обмен данными с внешними источниками данных, такими как электронные таблицы, базы данных, XML, CSV и текстовые файлы; - Выполнять предварительную и последующую обработку данных моделей оптимизации; - Развёртывать гибридные алгоритмы для решения типов задач, для которых нет прямых эффективных решателей; - Разделять модель и данные, что значительно упрощает повторное использование моделей и решений и упрощает построение крупномасштабных задач оптимизации;
AMPL поддерживает широкий спектр типов задач, в том числе: Линейное программирование Квадратичное программирование Нелинейное программирование Смешанное целочисленное программирование Смешанно-целочисленное квадратичное программирование с выпуклыми квадратичными ограничениями или без них Смешанно-целочисленное нелинейное программирование Программирование конуса второго порядка Глобальная оптимизация Задачи полуопределенного программирования с билинейными матричными неравенствами Задачи теории дополнительности (MPEC) в дискретных или непрерывных переменных Программирование с ограничениями
Пользователь может прервать процесс решения в любое время Ошибки решателя не влияют на интерпретатор 32-битную версию AMPL можно использовать с 64-битным решателем и наоборот.
Взаимодействие с решателем осуществляется через четко определенный интерфейс nl .
Доступность
AMPL доступен для многих популярных 32- и 64-разрядных операционных систем, включая Linux, macOS, Solaris, AIX и Windows . Переводчик является проприетарным программным обеспечением, поддерживаемым AMPL Optimization LLC. Однако существует несколько онлайн-сервисов, предоставляющих бесплатные средства моделирования и решения с использованием AMPL. Также доступны бесплатная студенческая версия с ограниченной функциональностью и бесплатная полнофункциональная версия для академических курсов.
AMPL можно использовать из Microsoft Excel через надстройку SolverStudio Excel.
Библиотека AMPL Solver (ASL), которая позволяет читать nl-файлы и обеспечивает автоматическую дифференциацию, имеет открытый исходный код. Он используется во многих решателях для реализации соединения AMPL.
История В этой таблице представлены важные этапы в истории AMPL. Период Основные события 1985 г. AMPL был разработан и реализован 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. 1990 г. Статья с описанием языка моделирования AMPL была опубликована в журнале Management Science . 1991 г. AMPL поддерживает нелинейное программирование и автоматическое дифференцирование 1993 г. Роберт Фурер, Дэвид Гей и Брайан Керниган были награждены премией ORSA/CSTS Американским обществом исследования операций за работы по проектированию систем математического программирования и языка моделирования AMPL. 1995 г. Расширения для представления кусочно-линейных и сетевых структур 1995 г. Скриптовые конструкции 1997 г. Расширенная поддержка нелинейных решателей 1998 г. AMPL поддерживает проблемы теории дополнительности 2000 г. Доступ к реляционной базе данных и электронным таблицам 2002 г. Поддержка программирования ограничений 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. 2003 г. Компания AMPL Optimization LLC была основана изобретателями AMPL Робертом Фурером, Дэвидом Гэем и Брайаном Керниганом. Новая компания взяла на себя разработку и поддержку языка моделирования AMPL от Lucent Technologies, Inc. 2005 г. Открыта группа Google по языку моделирования AMPL 2008 г. Kestrel: представлен интерфейс AMPL для сервера NEOS 2011 г. AMPL для курсов 2012 г. Роберт Фурер, Дэвид Гей и Брайан Керниган были удостоены премии INFORMS Impact Prize 2012 как создатели одного из самых важных языков алгебраического моделирования. 2012 г. AMPL-книга становится бесплатным онлайн 2012 г. AMPL «Логика» и расширения программирования с ограничениями 2013 г. Становится доступна новая кроссплатформенная интегрированная среда разработки (IDE) для AMPL 2015 г. AMPL API для MATLAB 2016 г. AMPL-API для C++ 2017 г. AMPL-API для Python 2018 г. AMPL-API для R 2020 г. Новый интерфейс электронных таблиц AMPL Direct 2022 г. Развертывание оптимизации в облачных средах и контейнерах
Образец модели Транспортная задача от Джорджа Данцига используется для предоставления примера модели AMPL. Эта задача находит наименее затратный график отгрузки, который удовлетворяет требованиям на рынках и поставкам на заводах. 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: Решатель Поддерживаемые типы проблем APOPT смешанное целочисленное нелинейное программирование Artelys Knitro линейное, квадратичное и нелинейное программирование Bonmin смешанное целочисленное нелинейное программирование BPMPD линейное и квадратичное программирование COIN-OR CBC смешанное целочисленное программирование COIN-OR CLP линейное программирование CONOPT нелинейное программирование Couenne смешанное целочисленное нелинейное программирование (MINLP) CPLEX линейное, квадратичное, конусное второго порядка и смешанное целочисленное программирование CPLEX CP Optimizer программирование ограничений FILTER нелинейное программирование FortMP линейное, квадратичное и смешанное целочисленное программирование Gecode программирование ограничений IPOPT нелинейное программирование JaCoP программирование ограничений LGO глобальная и локальная нелинейная оптимизация lp_solve линейное и смешанное целочисленное программирование MINOS линейное и нелинейное программирование MINTO смешанное целочисленное программирование MOSEK линейное, смешанное целочисленное линейное, квадратичное, смешанное целочисленное квадратичное, квадратично ограниченное, коническое и выпуклое нелинейное программирование Octeract Engine Все типы задач оптимизации без дифференциальных или интегральных членов, включая разрывные задачи с и элементарными функциями. SCIP смешанное целочисленное программирование SNOPT нелинейное программирование Sulum линейное и смешанное целочисленное программирование WORHP нелинейное программирование XA линейное и смешанное целочисленное программирование Xpress линейная и выпуклая квадратичная оптимизация и их смешанные целочисленные аналоги
Карта экосистемы
Нажмите на карту, чтобы открыть ее интерактивную версию
См. также
sol (format) GNU MathProg (ранее известный как GMPL) — это подмножество AMPL, поддерживаемое комплектом линейного программирования GNU .
Примечания
Внешние ссылки
проф. Домашняя страница Фуре в Северо-Западном университете
Категория:Проприетарное кроссплатформенное программное обеспечение Категория:Языки программирования, появившиеся в 1985 году Категория:Скриптовые языки Категория:Математическое моделирование Категория:Системы компьютерной алгебры Категория:Программное обеспечение, разработанное в 1990 году