0-1 Линейное программирование: вычисление оптимальной формулировки

Рассмотрим мерное пространство , и пусть - линейное ограничение вида , где , и k \ in \ mathbb {R} .$n$$\{0,1\}^n$$c$$a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$$a_i \in \mathbb{R}$$x_i \in \{0,1\}$$k \in \mathbb{R}$

Очевидно, что $c$ имеет эффект разделения $\{0,1\}^n$ на два подмножества $S_c$ и $S_{\lnot c}$ . $S_c$ содержит все и только те точки, которые удовлетворяют $c$ , тогда как $S_{\lnot c}$ содержит все и только те точки, фальсифицирующие $c$ .

Предположим, что $|S_c| \geq n$ . Теперь позвольте $O$ быть подмножеством $S_c$ таким, чтобы выполнялись все следующие три утверждения:

1. $O$ содержит ровно $n$ точек.
2. Такие $n$ точек линейно независимы.
3. Такими $n$ точками являются те, которые находятся на минимальном расстоянии от гиперплоскости, представленной $c$ . Точнее, пусть $d( x, c )$ - расстояние от точки $x \in \{0,1\}^n$ до гиперплоскости $c$ . Тогда $\forall B \subseteq S_c$ такой, что $B$ удовлетворяет 1 и 2, это тот случай, когда $\sum_{x \in B} d(x, c) \geq \sum_{x \in O} d(x, c)$ , Другими словами, $O$ среди всех подмножеств $S_c$ удовлетворяющих условиям 1 и 2, минимизирует сумму расстояний его точек от гиперплоскости $c$ .

Вопросов

1. Учитывая , возможно ли эффективно вычислить ? $c$$O$
2. Какой самый известный алгоритм для его вычисления?

$\ $

Пример с $n = 3$

O = { ( 0 , 0 , 1 ) , ( 1 , 1 , 1 ) , ( 1 , 0 , 0 ) $S_{\lnot c} = \{ ( 1, 0, 1 ) \}$ , .$O = \{ ( 0, 0, 1 ), ( 1, 1, 1 ), ( 1, 0, 0 ) \}$

$\ $

Обновление 05/12/2012

мотивация

Мотивация , что использование должно быть возможным , чтобы определить оптимальное ограничение , как это должно быть гиперплоскость определяется точек . c ∗ n $O$$c^*$$n$$O$

Оптимальное ограничение - это то, которое приводит к оптимальному многограннику .P $c^*$$P^*$

Оптимальным многогранником является тот, вершинами которого являются все и только целочисленные вершины исходного многогранника (целочисленная вершина - это вершина, координаты которой являются целыми).$P^*$$P$

Процесс может быть повторен для каждого ограничения экземпляра 0-1 , каждый раз заменяя его соответствующим оптимальным ограничением . В конце концов, это приведет к оптимальным многогранника из . Тогда, поскольку вершины - это все и только целочисленные вершины исходного многогранника из , любой алгоритм для можно использовать для вычисления оптимального целочисленного решения. Я знаю, что возможность эффективного вычисления подразумевает , однако следующий дополнительный вопрос все еще стоит:L P I c c ∗ P ∗ I P ∗ P I L P P ∗ P = N $c$$LP$$I$$c$$c^*$$P^*$$I$$P^*$$P$$I$$LP$$P^*$$P = NP$

Дополнительный вопрос

Есть ли предыдущие работы в этом направлении? Кто-нибудь уже исследовал задачу вычисления, учитывая многогранник , его соответствующий оптимальный многогранник ? Какой самый известный алгоритм для этого?P $P$$P^*$

Похоже, что это трудно сделать с помощью NP, уменьшив сумму подмножества. Предположим , что мы имели эффективную процедуру для вычисления . Учитывая положительные целые числа v 1 , … , v n, закодированные в двоичном виде, мы хотим проверить, существует ли подмножество, суммирующее s . Предварительная обработка, выбрасывая любые целые числа больше s .$O$$v_1,\dots,v_n$$s$$s$

Вызовите процедуру, чтобы получить небольшой набор точек, удовлетворяющих v 1 x 1 + ⋯ + v 1 x n ≤ s , удовлетворяющих вашим условиям минимальности (предварительная обработка обеспечивает | S c | ≥ n ). Этот набор, безусловно, будет содержать точку на гиперплоскости v 1 x 1 + ⋯ + v 1 x n = s, если она есть.$O$$v_1x_1+\dots+v_1x_n\leq s$$|S_c|\geq n$$v_1x_1+\dots+v_1x_n= s$

Мне кажется, вы пытаетесь добраться до выпуклой оболочки IP - по сути, это то, чего пытаются достичь алгоритмы разреза. Хотя на первый взгляд эти методы не очень привлекательны, на практике это плохо сказывается.

Есть все теории о генерации действительных неравенств. Хорошей отправной точкой была бы теория целочисленного программирования книги Шрайвера.