Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
SAMPL
Парадигмамультипарадигма : декларативная , императивная
РазработаноГаутам Митра, Энза Мессина, Валенте Патрик
Впервые появился2001 ; 20 лет спустя ( 2001 )
Стабильный выпуск
20120523/23 мая 2013 г . ; 7 лет назад ( 2013-05-23 )
Операционные системыКроссплатформенность (мультиплатформенность)
ЛицензияПроприетарный
Расширения имени файла.mod .dat .run .sampl
Веб-сайтwww .optirisk-systems .com
Под влиянием
AMPL

SAMPL , что означает «стохастический AMPL » , представляет собой язык алгебраического моделирования, полученный в результате расширения известного языка AMPL с помощью расширенного синтаксиса и ключевых слов. Он разработан специально для представления задач стохастического программирования [1] и, с помощью недавних расширений, задач со случайными ограничениями, интегрированными случайными ограничениями и проблемами робастной оптимизации . Он может генерировать детерминированную эквивалентную версию экземпляров, используя все решатели, к которым подключается AMPL, [2] или генерировать представление SMPS и использовать специализированные решатели на основе декомпозиции, такие как FortSP.

Особенности языка [ править ]

SAMPL разделяет все языковые функции с AMPL и добавляет некоторые конструкции, специально разработанные для выражения стохастического программирования на основе сценариев и надежной оптимизации .

Возможности и конструкции стохастического программирования [ править ]

Чтобы выразить основанные на сценарии проблемы SP, дополнительные конструкции описывают древовидную структуру и группируют переменную решения по этапам. Более того, можно указать, какой параметр хранит вероятности для каждой ветви дерева, а какой набор представляет собой набор сценариев. Также доступны другие конструкции для простого определения случайных ограничений и интегрированного случайного ограничения в задаче SP. Использование этих языковых конструкций позволяет сохранить структуру проблемы, тем самым делая ее доступной для решателей, которые могут использовать ее с помощью специализированных методов декомпозиции, таких как разложение Бендерса, для ускорения решения.

Надежные конструкции оптимизации [ править ]

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

  • Сойстер [3]
  • Берцимас и Сим [4]
  • Бен-Тал и Немировский [5]

Доступность [ править ]

SAMPL в настоящее время доступен как часть программного обеспечения AMPLDev (распространяется www.optirisk-systems.com ). Он поддерживает множество популярных 32- и 64-битных платформ , включая Windows , , Linux и Mac OS X . Доступна бесплатная ознакомительная версия с ограниченной функциональностью. [6]

Пример модели стохастического программирования [ править ]

Ниже приводится SAMPL-версия простой задачи (Дакота [7] ), демонстрирующая конструкции, связанные с SP. Он не включает файл данных, который следует обычному синтаксису AMPL (см. Пример, приведенный на странице AMPL Wikipedia для получения дополнительной информации).

set Prod;set Resource;# Scenarios (future possible realizations)набор сценариев Scen;# Definition of the problem as a two-stage problemдерево Дерево: = двухступенчатое ;# Demand for each product in each scenarioслучайный параметр Demand {Prod, Scen};# Probability of each scenarioвероятность P {Scen};# Cost of each unit of resourceparam Cost{Resource};# Requirement in terms of resources units to produce one unit of each productparam ProdReq{Resource,Prod};# Selling price of each productparam Price{Prod};# Initial budgetparam Budget;# Amount of resources to buyvar buy{r in Resource} >= 0, суффикс ступень 1;# Amount of each product to producevar amountprod{p in Prod, s in Scen} >= 0, суффикс ступень 2;# Amount of each product to sellvar amountsell{p in Prod, s in Scen} >= 0, суффикс ступень 2;# Total final wealth, as expected total income from sales minus costs for the resourcesmaximize wealth: sum{s in Scen} P[s] * (sum{p in Prod} Price[p] * amountsell[p,s] - sum{r in Resource} Cost[r] * buy[r]);subject to# Make sure you have enough resources to produce what we intend tobalance{r in Resource, s in Scen}: buy[r] >= sum{p in Prod} ProdReq[r,p] * amountprod[p, s];# Make sure we do not sell what we did not produceproduction{p in Prod, s in Scen}: amountsell[p,s] <= amountprod[p,s];# Make sure we do not sell more than the market demandsales{p in Prod, s in Scen}: amountsell[p,s] <= Demand[p,s];# Respect initial budgetbudgetres: sum{r in Resource} Cost[r] * buy[r] <= Budget;

Связь с решателями [ править ]

Формат уровня экземпляра SAMPL для проблем SP - SMPS, и поэтому проблема может быть решена любым решателем, который поддерживает этот стандарт. Один из таких решателей (FortSP) входит в стандартный дистрибутив SAMPL. Что касается задач робастной оптимизации, необходимый решатель зависит от конкретной используемой формулировки, так как формулировка Бен-Тала и Немировского требует решателя второго порядка с конусом .

См. Также [ править ]

  • Язык алгебраического моделирования
  • ЦЕЛИ
  • AMPL
  • FortSP
  • GAMS - Общая система алгебраического моделирования
  • GLPK - бесплатная система с открытым исходным кодом, основанная на подмножестве AMPL
  • MPS (формат)
  • Надежная оптимизация
  • Стохастическое программирование

Ссылки [ править ]

  1. ^ Кристиан Валенте, Гаутам Митра, Мустафа Садки и Роберт Фурер (2009). «Расширение языков алгебраического моделирования для стохастического программирования» . ИНФОРМС Журнал по вычислительной технике . 21 (1): 107–122. DOI : 10.1287 / ijoc.1080.0282 .CS1 maint: несколько имен: список авторов ( ссылка )
  2. ^ http://www.ampl.com/solvers.html
  3. ^ Аллен Л. Сойстер (1974). «Техническое примечание - Выпуклое программирование с ограничениями, включающими набор, и приложения к неточному линейному программированию» . Исследование операций . 21 (5): 1154–1157. DOI : 10.1287 / opre.21.5.1154 .
  4. ^ Берцимас, Димитрис; Сим, Мелвин (2004). «Цена надежности». Исследование операций . 52 (1): 35–53. DOI : 10.1287 / opre.1030.0065 .
  5. ^ Арон Бен-Tal & Аркади Немировский (1998). «Робастная выпуклая оптимизация». Математика исследования операций . 23 (4): 769–805. CiteSeerX 10.1.1.135.798 . DOI : 10.1287 / moor.23.4.769 . 
  6. ^ http://optirisk-systems.com/products_ampldevSP.asp
  7. ^ Higle, Julia L, Уоллес, Stein W (2003). «Анализ чувствительности и неопределенности в линейном программировании» (PDF) . Интерфейсы . 33 (4): 53–60. DOI : 10.1287 / inte.33.4.53.16370 . CS1 maint: несколько имен: список авторов ( ссылка )

Внешние ссылки [ править ]

  • Домашняя страница AMPL
  • Домашняя страница OptiRisk Systems