Citeseer/The continuous knapsack set (2014) 10.1.1.642.3962

Материал из DISCOPAL
Версия от 17:23, 23 ноября 2021; StasFomin (обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

«

Мы изучаем выпуклую оболочку непрерывного ранцевого множества, состоящего из одного ограничения неравенства с n неотрицательными целыми и m неотрицательными ограниченными непрерывными переменными.

При это множество является небольшим обобщением множества потока одиночных дуг, изученного Magnanti, Mirchandani, and Vachani (1993).

Сначала мы покажем, что в любом неравенстве, определяющем грань, число различных ненулевых коэффициентов непрерывных переменных ограничено . Наш следующий результат - показать, что при эта верхняя граница на самом деле равна 1.

Из этого следует, что при коэффициенты непрерывных переменных в любом неравенстве, определяющем фасет, после масштабирования равны либо 0, либо 1, и что все фасеты могут быть получены из фасетов непрерывных ранцевых множеств с .

Затем показано, что выпуклый корпус множеств с и задается гранями либо двухпеременных чисто целочисленных ранцевых множеств, либо непрерывных ранцевых множеств с и , в которых непрерывная переменная не ограничена.

Мы покажем на примере, что при ненулевые коэффициенты непрерывных переменных могут принимать различные значения.

…»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.