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