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