ОБРАЗЕЦ

ОБРАЗЕЦ
Парадигма	мультипарадигмальность : декларативный , императивный
Разработано	Гаутам Митра , Энца Мессина, Валенте Патрик
Впервые появился	2001 год ; 23 года назад
Стабильная версия	20120523 / 23 мая 2013 г .; 11 лет назад
ТЫ	Кроссплатформенность (мультиплатформенность)
Лицензия	Собственный
Расширения имен файлов	.mod .dat .run .образец
Веб-сайт	www .optirisk-системы .с
Под влиянием
	AMPL

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

Языковые особенности

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

Особенности и конструкции стохастического программирования

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

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

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

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

Доступность

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

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

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

set Prod;
set Resource;

# Scenarios (future possible realizations)
scenarioset Scen;

# Definition of the problem as a two-stage problem
tree Tree := twostage;

# Demand for each product in each scenario
random param Demand{Prod, Scen};

# Probability of each scenario
probability P{Scen};	

# Cost of each unit of resource
param Cost{Resource};

# Requirement in terms of resources units to produce one unit of each product
param ProdReq{Resource,Prod};

# Selling price of each product
param Price{Prod};

# Initial budget
param Budget;

# Amount of resources to buy
var buy{r in Resource} >= 0, suffix stage 1;

# Amount of each product to produce
var amountprod{p in Prod, s in Scen} >= 0, suffix stage 2;

# Amount of each product to sell
var amountsell{p in Prod, s in Scen} >= 0, suffix stage 2;

# Total final wealth, as expected total income from sales minus costs for the resources
maximize 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 to
balance{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 produce
production{p in Prod, s in Scen}: amountsell[p,s] <= amountprod[p,s];
# Make sure we do not sell more than the market demand
sales{p in Prod, s in Scen}: amountsell[p,s] <= Demand[p,s];
# Respect initial budget
budgetres: sum{r in Resource} Cost[r] * buy[r] <= Budget;

Подключение решателей

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

См. также

Алгебраический язык моделирования
АИММС
AMPL
Продолжить СП
GAMS - Общая система алгебраического моделирования
GLPK - бесплатная система с открытым исходным кодом, основанная на подмножестве AMPL.
HiGHS - HiGHS - это высокопроизводительное последовательное и параллельное программное обеспечение для решения крупномасштабных моделей разреженного линейного программирования (LP), смешанно-целочисленного программирования (MIP) и квадратичного программирования (QP).
МПС (формат)
Надежная оптимизация
Стохастическое программирование

Ссылки

^ Кристиан Валенте, Гаутам Митра, Мустафа Садки и Роберт Фурер (2009). «Расширение языков алгебраического моделирования для стохастического программирования» . ИНФОМС Журнал по вычислительной технике . 21 (1): 107–122. дои : 10.1287/ijoc.1080.0282 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ «Решатели» .
^ Аллен Л. Сойстер (1974). «Техническое примечание. Выпуклое программирование с ограничениями, включающими множество, и приложения к неточному линейному программированию» . Исследование операций . 21 (5): 1154–1157. дои : 10.1287/опре.21.5.1154 .
^ Берцимас, Димитрис; Сим, Мелвин (2004). «Цена надежности» . Исследование операций . 52 (1): 35–53. дои : 10.1287/opre.1030.0065 . hdl : 2268/253225 . S2CID 8946639 .
^ Аарон Бен-Тал и Аркадий Немировский (1998). «Надежная выпуклая оптимизация». Математика исследования операций . 23 (4): 769–805. CiteSeerX 10.1.1.135.798 . дои : 10.1287/moor.23.4.769 .
^ «Продукты: АМПЛДев СП» . optirisk-systems.com . Архивировано из оригинала 11 ноября 2012 г.
^ Хигл, Джулия Л., Уоллес, Стейн В. (2003). «Анализ чувствительности и неопределенность в линейном программировании» (PDF) . Интерфейсы . 33 (4): 53–60. дои : 10.1287/inte.33.4.53.16370 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

Внешние ссылки

[ExtendingAlgebraicLanguages-1] Кристиан Валенте, Гаутам Митра, Мустафа Садки и Роберт Фурер (2009). «Расширение языков алгебраического моделирования для стохастического программирования» . ИНФОМС Журнал по вычислительной технике . 21 (1): 107–122. дои : 10.1287/ijoc.1080.0282 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[2] «Решатели» .

[Soyster-3] Аллен Л. Сойстер (1974). «Техническое примечание. Выпуклое программирование с ограничениями, включающими множество, и приложения к неточному линейному программированию» . Исследование операций . 21 (5): 1154–1157. дои : 10.1287/опре.21.5.1154 .

[4] Берцимас, Димитрис; Сим, Мелвин (2004). «Цена надежности» . Исследование операций . 52 (1): 35–53. дои : 10.1287/opre.1030.0065 . hdl : 2268/253225 . S2CID 8946639 .

[BenTal-5] Аарон Бен-Тал и Аркадий Немировский (1998). «Надежная выпуклая оптимизация». Математика исследования операций . 23 (4): 769–805. CiteSeerX 10.1.1.135.798 . дои : 10.1287/moor.23.4.769 .

[6] «Продукты: АМПЛДев СП» . optirisk-systems.com . Архивировано из оригинала 11 ноября 2012 г.

[7] Хигл, Джулия Л., Уоллес, Стейн В. (2003). «Анализ чувствительности и неопределенность в линейном программировании» (PDF) . Интерфейсы . 33 (4): 53–60. дои : 10.1287/inte.33.4.53.16370 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

[1]

[2]

[3]

[4]

[5]

[6]

[7]