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