Citeseer/On the Mixing Set with a Knapsack Constraint (2014) 10.1.1.746.9893 — различия между версиями
StasFomin (обсуждение | вклад) (Новая страница: «{{checked|}} {{citeseerlink|citeseer/On the Mixing Set with a Knapsack Constraint (2014) 10.1.1.746.9893|<html> </html>}} {{enddiv}} Категория:CiteSee…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{checked|}} | {{checked|}} | ||
| − | {{citeseerlink|citeseer/On the Mixing Set with a Knapsack Constraint (2014) 10.1.1.746.9893| | + | {{citeseerlink|citeseer/On the Mixing Set with a Knapsack Constraint (2014) 10.1.1.746.9893| |
| − | + | Смешанное (линейное и целочисленное) подмножество ограничений с множество с ранцевым ограничением возникает как подструктура в переформулировках смешанного целочисленного программирования для программ, ограниченных шансами, со стохастическими правыми сторонами над конечным дискретным распределением. | |
| + | |||
| + | Недавно Luedtke и Kucukyavuz изучили допустимые неравенства для таких множеств. | ||
| + | |||
| + | Однако большинство их результатов было сосредоточено на случае равных вероятностей (эквивалентно, когда ранец сводится к ограничению кардинальности), и лишь незначительные результаты были получены в общем случае. | ||
| + | |||
| + | В данной работе мы рассматриваем общий случай вероятностей (ограничение общего ранца). | ||
| + | |||
| + | Мы характеризуем допустимые неравенства, не вытекающие из ранцевого политопа, и используем эту характеристику для обобщения неравенств, полученных ранее для случая равных вероятностей. | ||
| + | |||
| + | Мы также показываем, что можно разделить большой класс неравенств за полиномиальное время. | ||
| + | }} | ||
{{enddiv}} | {{enddiv}} | ||
[[Категория:CiteSeerArticles]] | [[Категория:CiteSeerArticles]] | ||
Текущая версия на 15:42, 23 ноября 2021
Смешанное (линейное и целочисленное) подмножество ограничений с множество с ранцевым ограничением возникает как подструктура в переформулировках смешанного целочисленного программирования для программ, ограниченных шансами, со стохастическими правыми сторонами над конечным дискретным распределением.
Недавно Luedtke и Kucukyavuz изучили допустимые неравенства для таких множеств.
Однако большинство их результатов было сосредоточено на случае равных вероятностей (эквивалентно, когда ранец сводится к ограничению кардинальности), и лишь незначительные результаты были получены в общем случае.
В данной работе мы рассматриваем общий случай вероятностей (ограничение общего ранца).
Мы характеризуем допустимые неравенства, не вытекающие из ранцевого политопа, и используем эту характеристику для обобщения неравенств, полученных ранее для случая равных вероятностей.
Мы также показываем, что можно разделить большой класс неравенств за полиномиальное время.
…»