Citeseer/On the Mixing Set with a Knapsack Constraint (2014) 10.1.1.746.9893
Смешанное (линейное и целочисленное) подмножество ограничений с множество с ранцевым ограничением возникает как подструктура в переформулировках смешанного целочисленного программирования для программ, ограниченных шансами, со стохастическими правыми сторонами над конечным дискретным распределением.
Недавно Luedtke и Kucukyavuz изучили допустимые неравенства для таких множеств.
Однако большинство их результатов было сосредоточено на случае равных вероятностей (эквивалентно, когда ранец сводится к ограничению кардинальности), и лишь незначительные результаты были получены в общем случае.
В данной работе мы рассматриваем общий случай вероятностей (ограничение общего ранца).
Мы характеризуем допустимые неравенства, не вытекающие из ранцевого политопа, и используем эту характеристику для обобщения неравенств, полученных ранее для случая равных вероятностей.
Мы также показываем, что можно разделить большой класс неравенств за полиномиальное время.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.