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

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.

Транспортная задача от Джорджа Данцига используется для предоставления примера модели 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]

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

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

• ampl.com — официальный сайт AMPL
• проф. Домашняя страница Фуре в Северо-Западном университете

Шаблон:Mathematical optimization software