Czy zerowa luka integralności oznacza zerową lukę dualności dla niektórych problemów?

Wiemy, że jeśli różnica między wartościami programu liczb całkowitych i jego dualności („dualność”) wynosi zero, wówczas liniowe relaksacje programowania programu liczb całkowitych i dualność relaksacji dopuszczają rozwiązania integralne (integralność zerowa) luka"). Chcę wiedzieć, czy konwersacja się utrzymuje, przynajmniej w niektórych przypadkach.

Załóżmy, że mam program liczb całkowitych 0-1 , gdzie macierz jest macierzą . Załóżmy, że programowanie liniowe relaks z ma integralną rozwiązanie optymalne. Czy zatem dualne programowanie liniowe również dopuszcza integralne rozwiązanie? $P: \max\{1^Tx: Ax \leq 1, x\in \{0,1\}^n\}$ $A$ $0-1$ $P'$ $P$ $P'$

Byłbym wdzięczny za wszelkie kontrprzykłady lub wskazówki ...

— Ankur
źródło

@Kaveh nie jest pewny, czy algorytmy aproksymacyjne są tutaj właściwym tagiem. a nawet ds.algorytmy

— Suresh Venkat

W pierwszym akapicie, co masz na myśli przez dual z liczbą całkowitą? Przydatne jest przyjrzenie się książce Schrijvera o programowaniu liniowym i całkowitym, aby zrozumieć podstawy teorii wielościennej, a zwłaszcza gdy relaksacje programowania liniowego mają wierzchołki całkowite. Macierze TUM i systemy nierówności TDI są odpowiednie dla twojego pytania.

— Chandra Chekuri,

@Suresh, czy algorytmy programowania liniowego i optymalizacji nie są objęte?

— Kaveh,

@ChandraChekuri Mówię o całkowitych programach liniowych; więc dual jest standardowym dualem ILP, dla którego utrzymuje się słaba dualność. Trudność polega na tym, że wystarczające warunki dla integralności (pierwotnych) rozwiązań LP (takich jak TUM / zbalansowane itp.) Wydają się przechodzić przez pozornie silniejszą koncepcję integralności rozwiązań pierwotnego i podwójnego LP. To sprawiło, że zastanawiałem się, czy integralność pierwotnego rozwiązania implikuje integralność podwójnego rozwiązania, przynajmniej dla współczynników całkowych. PS: Mógłbym po prostu iść do Siebel i porozmawiać tam! Byłem w twojej klasie kilka lat temu!

— Ankur,

To konkretne pytanie jest bliższe obecnym tagom.

— Suresh Venkat

Oto przykład, który może być zbliżony do kontrprzykładu do roszczenia.

Rozważ LP $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}\,.$

$P'$ $y_1=y_2=y_{12}=1$ $3$ $P$ $x = [0.5~0.5~0~1~0.5~0.5]^T$ $P$ $2$ $x = [1~0~0~1~0~0]$

$P'$ $P$

— kbala
źródło

Dzięki! To działa! Jak wymyśliłeś ten przykład? Czy istnieje klasa problemów, z których jest czerpana?

— Ankur,

Macierz jest modyfikacją macierzy granicznej paska Mobiusa, podaną w naszym artykule na temat optymalnych cykli homologicznych. Ostatnio bawiłem się takimi matrycami granicznymi i dlatego trochę naturalnie zacząłem od tej matrycy, aby stworzyć przykład, który podałem.

— kbala