Citeseer/The continuous knapsack set (2014) 10.1.1.642.3962 — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
При <m>n=1</m> это множество является небольшим обобщением множества потока одиночных дуг, изученного Magnanti, Mirchandani, and Vachani (1993). | При <m>n=1</m> это множество является небольшим обобщением множества потока одиночных дуг, изученного Magnanti, Mirchandani, and Vachani (1993). | ||
| − | Сначала мы покажем, что в любом неравенстве, определяющем грань, число различных ненулевых коэффициентов непрерывных переменных ограничено <m>2^ | + | Сначала мы покажем, что в любом неравенстве, определяющем грань, число различных ненулевых коэффициентов непрерывных переменных ограничено <m>2^n-n</m>. Наш следующий результат - показать, что при <m>n=2</m> эта верхняя граница на самом деле равна 1. |
Из этого следует, что при <m>n=2</m> коэффициенты непрерывных переменных в любом неравенстве, определяющем фасет, после масштабирования равны либо 0, либо 1, и что все фасеты могут быть получены из фасетов непрерывных ранцевых множеств с <m>m=1</m>. | Из этого следует, что при <m>n=2</m> коэффициенты непрерывных переменных в любом неравенстве, определяющем фасет, после масштабирования равны либо 0, либо 1, и что все фасеты могут быть получены из фасетов непрерывных ранцевых множеств с <m>m=1</m>. | ||
Текущая версия на 17:23, 23 ноября 2021
Мы изучаем выпуклую оболочку непрерывного ранцевого множества, состоящего из одного ограничения неравенства с n неотрицательными целыми и m неотрицательными ограниченными непрерывными переменными.
При это множество является небольшим обобщением множества потока одиночных дуг, изученного Magnanti, Mirchandani, and Vachani (1993).
Сначала мы покажем, что в любом неравенстве, определяющем грань, число различных ненулевых коэффициентов непрерывных переменных ограничено . Наш следующий результат - показать, что при эта верхняя граница на самом деле равна 1.
Из этого следует, что при коэффициенты непрерывных переменных в любом неравенстве, определяющем фасет, после масштабирования равны либо 0, либо 1, и что все фасеты могут быть получены из фасетов непрерывных ранцевых множеств с .
Затем показано, что выпуклый корпус множеств с и задается гранями либо двухпеременных чисто целочисленных ранцевых множеств, либо непрерывных ранцевых множеств с и , в которых непрерывная переменная не ограничена.
Мы покажем на примере, что при ненулевые коэффициенты непрерывных переменных могут принимать различные значения.
…»