Citeseer/The continuous knapsack set (2014) 10.1.1.642.3962
Мы изучаем выпуклую оболочку непрерывного ранцевого множества, состоящего из одного ограничения неравенства с n неотрицательными целыми и m неотрицательными ограниченными непрерывными переменными.
При это множество является небольшим обобщением множества потока одиночных дуг, изученного Magnanti, Mirchandani, and Vachani (1993).
Сначала мы покажем, что в любом неравенстве, определяющем грань, число различных ненулевых коэффициентов непрерывных переменных ограничено . Наш следующий результат - показать, что при эта верхняя граница на самом деле равна 1.
Из этого следует, что при коэффициенты непрерывных переменных в любом неравенстве, определяющем фасет, после масштабирования равны либо 0, либо 1, и что все фасеты могут быть получены из фасетов непрерывных ранцевых множеств с .
Затем показано, что выпуклый корпус множеств с и задается гранями либо двухпеременных чисто целочисленных ранцевых множеств, либо непрерывных ранцевых множеств с и , в которых непрерывная переменная не ограничена.
Мы покажем на примере, что при ненулевые коэффициенты непрерывных переменных могут принимать различные значения.
…»
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.