Просмотр исходного текста страницы Citeseer/On the Mixing Set with a Knapsack Constraint (2014) 10.1.1.746.9893

{{checked|}}
{{citeseerlink|citeseer/On the Mixing Set with a Knapsack Constraint (2014) 10.1.1.746.9893|
Смешанное (линейное и целочисленное) подмножество ограничений с  множество с ранцевым ограничением возникает как подструктура в переформулировках смешанного целочисленного программирования для программ, ограниченных шансами, со стохастическими правыми сторонами над конечным дискретным распределением. 

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

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

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

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

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

[[Категория:CiteSeerArticles]]