Язык алгебраического моделирования - Algebraic modeling language

Языки алгебраического моделирования (AML) на высоком уровне компьютер языки программирования для описания и решения задач высокой сложности в больших масштабах математический вычисление (т.е. крупномасштабные оптимизация типа проблемы).[1] Одно из особых преимуществ некоторых языков алгебраического моделирования, таких как ЦЕЛИ,[1] AMPL,[2] GAMS,[1]MathProg,Мозель,[1][3] иOPL это сходство их синтаксиса с математической записью задач оптимизации. Это позволяет дать очень краткое и удобочитаемое определение проблем в области оптимизации, которое поддерживается определенными языковыми элементами, такими как наборы, индексы, алгебраические выражения, мощные разреженные переменные индекса и обработки данных, ограничения с произвольными именами. Алгебраическая формулировка модели не содержит подсказок, как ее обрабатывать.

AML не решает эти проблемы напрямую; вместо этого он вызывает соответствующие внешние алгоритмы для получения решения. Эти алгоритмы называются решатели и может справиться с определенными математические задачи подобно:

Основные элементы

Основные элементы AML:

Принципы дизайна

Большинство AML следуют определенным принципам дизайна:

  • сбалансированное сочетание декларативных и процедурных элементов
  • открытая архитектура и интерфейсы с другими системами
  • разные слои с разделением:

Создание модели на основе данных

Большинство языков моделирования используют сходство между структурированными моделями и реляционными базами данных. [4] путем предоставления уровня доступа к базе данных, который позволяет системе моделирования напрямую обращаться к данным из внешних источников данных (например, этих[5]настольные обработчики для AMPL). По мере совершенствования аналитических технологий, применяемых к бизнес-процессам, модели оптимизации становятся неотъемлемой частью систем поддержки принятия решений; Модели оптимизации могут быть структурированы и разбиты на уровни для представления и поддержки сложных бизнес-процессов. В таких приложениях многомерная структура данных, типичная для систем OLAP, может быть напрямую сопоставлена ​​с моделями оптимизации, а типичные операции MDDB могут быть преобразованы в операции агрегирования и дезагрегации в базовой модели. [6]

История

Языки алгебраического моделирования берут свое начало в программах генератора матриц и составителя отчетов (MGRW), разработанных в конце семидесятых годов. Некоторые из них - MAGEN, MGRW (IBM), GAMMA.3, DATAFORM и MGG / RWG. Эти системы упростили передачу экземпляров проблемы в алгоритмы решения и создание удобочитаемого отчета о результатах.

Первый матричный генератор для LP был разработан примерно в 1969 году в Mathematisch Centrum (ныне CWI) в Амстердаме.[7]Его синтаксис был очень близок к обычной математической нотации с использованием индексов и сигм. Вход для генератора состоял из отдельных разделов для модели и данных. Он нашел пользователей в университетах и ​​в промышленности. Основным промышленным потребителем стали производитель стали Hoogovens (ныне Tata Steel), где она использовалась почти 25 лет.

Большой шаг к современным языкам моделирования сделан в UIMP.[8], где структура математическое программирование модели, взятые из реальной жизни, анализируются впервые, чтобы выделить естественное группирование переменных и ограничений, возникающих из таких моделей. Это привело к появлению функций структуры данных, поддерживающих структурированное моделирование; В этой парадигме все входные и выходные таблицы вместе с переменными решения определены в терминах этих структур, что сопоставимо с использованием индексов и наборов. Это, вероятно, единственная наиболее примечательная особенность, общая для всех современных AML. и позволил со временем разделить структуру модели и ее данные, а также установить соответствие между объектами в модели MP и данными в реляционных базах данных. Таким образом, модель может быть наконец создана и решена для различных наборов данных, просто изменив ее наборы данных.

Соответствие между модельными объектами и реляционные модели данных,[4] Это стало возможным для беспрепятственного создания экземпляров моделей путем извлечения данных из корпоративных баз данных. Эта функция теперь в значительной степени упрощает оптимизацию в реальных приложениях и поддерживается большинством известных языков моделирования.

Рекомендации

  1. ^ а б c d Каллрат, Джозеф (2004). Языки моделирования в математической оптимизации. Kluwer Academic Publishing. ISBN  978-1-4020-7547-6.
  2. ^ Роберт Фурер; Дэвид М. Гей; Брайан В. Керниган (1990). «Язык моделирования для математического программирования». Наука управления. 36 (5): 519–554–83. Дои:10.1287 / mnsc.36.5.519.
  3. ^ Гере, Кристель; Принс, Кристиан; Сево, Марк (2002). Приложения оптимизации с Xpress-MP. Dash Optimization Limited. ISBN  0-9543503-0-8.
  4. ^ а б Гаутам Митра; Кормак Лукас; Ширли Муди; Бьярни Кристьянссон (1995). «Множества и индексы в моделировании линейного программирования и их интеграция с реляционными моделями данных». Вычислительная оптимизация и приложения. 4 (3): 262–283.
  5. ^ [1] Обработчики таблиц базы данных и электронных таблиц для AMPL
  6. ^ Koutsoukis, N .; Mitra, G .; Лукас, К. (1999). «Адаптация оперативной аналитической обработки для моделирования решений: взаимодействие информации и технологий принятия решений». Системы поддержки принятия решений. 26 (1): 1–30. Дои:10.1016 / S0167-9236 (99) 00021-4. Получено 22 ноября, 2017.
  7. ^ Jac. М. Антонисс, Система ввода для задач линейного программирования, Statistica Neerlandica 24 (1970), 143-153.
  8. ^ Фрэнсис Д. Эллисон; Гаутам Митра (1982). «UIMP: пользовательский интерфейс для математического программирования» (PDF). Транзакции ACM на математическом ПО. 8 (3): 229–255. Дои:10.1145/356004.356005. Архивировано из оригинал (PDF) на 2014-01-18. Получено 2014-01-16.