Citeseer/On the Mixing Set with a Knapsack Constraint (2014) 10.1.1.746.9893

Материал из DISCOPAL
Версия от 15:42, 23 ноября 2021; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

«

Смешанное (линейное и целочисленное) подмножество ограничений с множество с ранцевым ограничением возникает как подструктура в переформулировках смешанного целочисленного программирования для программ, ограниченных шансами, со стохастическими правыми сторонами над конечным дискретным распределением.

Недавно Luedtke и Kucukyavuz изучили допустимые неравенства для таких множеств.

Однако большинство их результатов было сосредоточено на случае равных вероятностей (эквивалентно, когда ранец сводится к ограничению кардинальности), и лишь незначительные результаты были получены в общем случае.

В данной работе мы рассматриваем общий случай вероятностей (ограничение общего ранца).

Мы характеризуем допустимые неравенства, не вытекающие из ранцевого политопа, и используем эту характеристику для обобщения неравенств, полученных ранее для случая равных вероятностей.

Мы также показываем, что можно разделить большой класс неравенств за полиномиальное время.

…»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.