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

14

Рассмотрим мерное пространство , и пусть - линейное ограничение вида , где , и k \ in \ mathbb {R} .n{0,1}nca1x1+a2x2+a3x3+ ... +an1xn1+anxnkaiRxi{0,1}kR

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

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

  1. O содержит ровно n точек.
  2. Такие n точек линейно независимы.
  3. Такими n точками являются те, которые находятся на минимальном расстоянии от гиперплоскости, представленной c . Точнее, пусть d(x,c) - расстояние от точки x{0,1}n до гиперплоскости c . Тогда BSc такой, что B удовлетворяет 1 и 2, это тот случай, когда xBd(x,c)xOd(x,c) , Другими словами, O среди всех подмножеств Sc удовлетворяющих условиям 1 и 2, минимизирует сумму расстояний его точек от гиперплоскости c .

Вопросов

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

 

Пример с n=3

Пример с n = 3

O = { ( 0 , 0 , 1 ) , ( 1 , 1 , 1 ) , ( 1 , 0 , 0 ) }S¬сзнак равно{(1,0,1)} , .Ознак равно{(0,0,1),(1,1,1),(1,0,0)}

 

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

мотивация

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

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

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

Оптимальная формулировка

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

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

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

Джорджио Камерани
источник
Похоже, что это трудно сделать с помощью NP, уменьшив сумму подмножества. Учитывая двоичные целые числа , чтобы проверить, есть ли подмножество, суммирующее , мы можем проверить, есть ли точка на гиперплоскости . Вас интересуют приближения? s v 1 x 1 + + v 1 x n = sv1,,vnsv1x1++v1xn=s
Колин МакКиллан
@ColinMcQuillan: вопрос предназначался для точного решения, однако меня, конечно, интересуют и приближения. Почему бы вам не превратить свой комментарий в ответ?
Джорджио Камерани
@ColinMcQuillan: Кроме того, ваша гиперплоскость определяется с использованием равенства, а моя - с использованием неравенства. Вы уверены, что это не имеет значения с точки зрения твердости? Я еще этого не проверял, поэтому просто спрашиваю.
Джорджио Камерани
Я немного смущен обо всех ограничениях на . Если вы ищете информацию о выпуклой оболочке то в литературе по исследованию операций есть много результатов о многограннике ранцев 0-1. С точки зрения приблизительных формулировок, посмотрите на это . S cОSс
Остин Бьюкенен

Ответы:

6

Похоже, что это трудно сделать с помощью NP, уменьшив сумму подмножества. Предположим , что мы имели эффективную процедуру для вычисления . Учитывая положительные целые числа v 1 , , v n, закодированные в двоичном виде, мы хотим проверить, существует ли подмножество, суммирующее s . Предварительная обработка, выбрасывая любые целые числа больше s .Оv1,...,vNss

Вызовите процедуру, чтобы получить небольшой набор точек, удовлетворяющих v 1 x 1 + + v 1 x ns , удовлетворяющих вашим условиям минимальности (предварительная обработка обеспечивает | S c |n ). Этот набор, безусловно, будет содержать точку на гиперплоскости v 1 x 1 + + v 1 x n = s, если она есть.Оv1Икс1++v1ИксNs|Sс|Nv1Икс1++v1ИксNзнак равноs

Колин Маккуиллан
источник
Может быть, я пропускаю что-то макроскопическое здесь, но у меня есть 2 вопроса: 1) Когда вы говорите «Заданные двоичные числа», что вы подразумеваете под двоичным ? принадлежат R . Может ты имеешь ввиду закодированный в двоичном виде? Или, может быть, вы хотели сказать положительное? 2) Зачем выбрасывать все целые числа больше s ? Они могут способствовать решению. Например: v 1 = - 3 , v 2 = 7 , v 3 = - 5 ,v1,,,,,vNрs если вы выбрасываете v 2, вы теряете единственное решение { v 2 , v 3 } . v1знак равно-3,v2знак равно7,v3знак равно-5,sзнак равно2v2{v2,v3}
Джорджио Камерани
2
Я думаю, что Колин имеет в виду, что если коэффициенты ограничения являются рациональными числами в их обычном двоичном представлении, то ваша задача кажется NP-трудной. (Смешивать действительные числа и NP-твердость всегда сложно.)aя
Джефф
1
@GiorgioCamerani: Мне нужно было сказать положительно - я обновил свой ответ.
Колин МакКиллан
1

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

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

AJ Студент
источник