Означает ли разрыв нулевой целостности нулевой разрыв двойственности для определенных задач?

14

Мы знаем, что если разрыв между значениями целочисленной программы и ее двойственной («двойственность разрыв») равен нулю, то линейные программные релаксации целочисленной программы и двойственной релаксации, оба допускают интегральные решения (нулевая) интегральность разрыв "). Я хочу знать, верно ли обратное, по крайней мере, в некоторых случаях.

AP:max{1Tx:Ax1,x{0,1}n}AP P01PPP

Буду признателен за любые контрпримеры или указатели ..

Анкур
источник
@Kaveh не уверен, что аппроксимационные алгоритмы - правильный тег здесь. или даже ds.algorithms
Суреш Венкат
4
В первом абзаце, что вы подразумеваете под двойной целочисленной программой? Полезно взглянуть на книгу Шрайвера по линейному и целочисленному программированию, чтобы понять основы теории многогранников и, в частности, когда релаксации линейного программирования имеют целочисленные вершины. Матрицы TUM и системы неравенств TDI имеют отношение к вашему вопросу.
Чандра Чекури
@Suresh, линейное программирование и оптимизация не попадают в алгоритмы?
Каве
@ChandraChekuri Я говорю о целочисленных линейных программах; таким образом, дуал является стандартным дуалом ILP, для которого имеет место слабая двойственность. Трудность заключается в том, что достаточные условия для целостности (первичных) решений ЛП (таких как TUM / сбалансированные и т. Д.), По-видимому, проходят через кажущуюся более сильной концепцию целостности решений первичного и его двойственного ЛП. Это заставило меня задуматься, подразумевает ли интегральность первичного решения интегральность двойственного решения, по крайней мере, для интегральных коэффициентов. PS: Я мог бы просто дойти до Siebel, и мы могли бы поговорить там! Я был в вашем классе несколько лет назад!
Анкур
Этот конкретный вопрос ближе к тегам, которые у него есть в настоящее время.
Суреш Венкат

Ответы:

5

Вот пример, который может быть близок к контрпримеру к иску.

Рассмотрим LP и его двойственное P = min { 1 T y + 1 T z | A T y + z 1 , y 0 , z 0 } дляматрицы 12 × 6P=max{1Tx|Ax1,x1,x0}P=min{1Ty+1Tz | ATy+z1, y0,z0}12×6

A=[100001010010110000001011010000100010000001001000100010000100011001001100].

Оптимальное решение дается выражением y 1 = y 2 = y 12 = 1 (все остальные переменные равны нулю) со значением целевой функции 3 . Оптимальное решение P задается вектором х = [ 0,5 0,5 0 1 0,5 0,5 ] T . Если вы решите P как целочисленную программу, оптимальное значение целевой функции будет только 2 , а x = [ 1 0 0 1 0Py1=y2=y12=13Px=[0.5 0.5 0 1 0.5 0.5]TP2 является оптимальным решением.x=[1 0 0 1 0 0]

PP

kbala
источник
Благодарность! Это работает! Как вы пришли к этому примеру? Есть ли класс проблем, из которых он взят?
Анкур
1
Матрица является модификацией граничной матрицы полосы Мёбиуса, приведенной в нашей статье об оптимальных гомологических циклах. Недавно я играл с такими граничными матрицами, и поэтому несколько естественным образом начал с этой матрицы, чтобы создать пример, который я привел.
Кбала