Bedeutet Null-Integralitätslücke für bestimmte Probleme Null-Dualitätslücke?

Wir wissen, dass, wenn die Lücke zwischen den Werten eines ganzzahligen Programms und seines Dualen (die "Dualitätslücke") Null ist, die linearen Programmierrelaxationen des ganzzahligen Programms und des Dualen der Relaxation beide integrale Lösungen zulassen (Integralität Null) Spalt"). Ich möchte wissen, ob das Gegenteil zutrifft, zumindest in einigen Fällen.

$P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$ $A$ $0-1$ $P'$ $P$ $P'$

Ich würde mich über Gegenbeispiele oder Hinweise freuen.

ds.algorithms optimization linear-programming integrality-gap Ankur
quelle

@Kaveh ist sich nicht sicher, ob Approximationsalgorithmen das richtige Tag sind. oder sogar ds.algorithms

Suresh Venkat

Was meinen Sie im ersten Absatz mit Dual eines Integer-Programms? Es ist nützlich, Schrijvers Buch über lineare und ganzzahlige Programmierung zu lesen, um die Grundlagen der Polyedertheorie zu verstehen, insbesondere wenn die linearen Programmierrelaxationen ganzzahlige Eckpunkte haben. TUM-Matrizen und TDI-Ungleichungssysteme sind für Ihre Frage relevant.

Chandra Chekuri

@Suresh, fallen nicht lineare Programmierung und Optimierung in Algorithmen?

Kaveh

@ChandraChekuri Ich spreche von ganzzahligen linearen Programmen; Das Dual ist also das Standard-Dual eines ILP, für das schwache Dualität gilt. Die Schwierigkeit hierbei besteht darin, dass ausreichende Bedingungen für die Integrität von (ursprünglichen) LP-Lösungen (wie TUM / ausgeglichen usw.) durch das scheinbar stärkere Konzept der Integrität von Lösungen des ursprünglichen und seines doppelten LP zu gehen scheinen. Dies ließ mich fragen, ob die Integralität der ursprünglichen Lösung die Integralität der dualen Lösung impliziert, zumindest für integrale Koeffizienten. PS: Ich könnte einfach zu Siebel gehen und wir könnten uns dort unterhalten! Ich war vor einigen Jahren in deiner Klasse!

Ankur

Diese bestimmte Frage ist näher an den Tags, die es derzeit hat.

Suresh Venkat

Antworten:

Hier ist ein Beispiel , das sein könnte nahe an ein Gegenbeispiel zu der Forderung.

Betrachten Sie die LP und sein dualesfür dieMatrix $P = \max \{ 1^T x \,|\, Ax \leq 1, x \leq 1, x \geq 0\}$ $P' = \min \{1^Ty + 1^Tz ~|~ A^Ty + z \geq 1, ~y \geq 0, z \geq 0 \}$ $12 \times 6$

$A = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 0 & 0 \end{bmatrix}\,.$

Eine optimale Lösung von ist gegeben durch (alle anderen Variablen sind Null) mit dem Zielfunktionswert von . Die optimale Lösung für durch den Vektor gegeben . Wenn Sie als ganzzahliges Programm lösen , ist der optimale Zielfunktionswert nur und $P'$ $y_1=y_2=y_{12}=1$ $3$ $P$ $x = [0.5~0.5~0~1~0.5~0.5]^T$ $P$ $2$ ist eine optimale Lösung. $x = [1~0~0~1~0~0]$

Zusammenfassend ist die LP hat eine integrale optimale Lösung, aber seine Doppel, nicht über eine integrierte optimale Lösung. Die primär-dualen Rollen sind von der von Ankur gewünschten Einstellung umgekehrt. In Anbetracht der Natur der LP-Dualität kann diese Instanz dennoch als Gegenbeispiel zur allgemeinen Aussage der ursprünglichen Behauptung angesehen werden. $P'$ $P$

kbala
quelle

Vielen Dank! Das geht doch! Wie sind Sie auf dieses Beispiel gekommen? Gibt es eine Klasse von Problemen, aus denen es hervorgeht?

Ankur

Die Matrix ist eine Modifikation der Grenzmatrix eines Mobius-Streifens, die in unserer Arbeit zu optimalen homologen Zyklen angegeben ist. Ich habe in letzter Zeit mit solchen Grenzmatrizen herumgespielt und daher etwas natürlich mit dieser Matrix begonnen, um das von mir angegebene Beispiel zu erstellen.

kbala