ILPs Flashcards
(13 cards)
Odd Cycle Traversal <= ILP
dane:
G, V={v1,…,vn}
czy da się usunąć maksymalnie k wierzchołków tak żeby podzielić graf na dwa podzbiory gdzie każdy z A ma połączenie z co najmniej jednym z B
- xi=1 języki vi usunięty
- yi=1 jeśli vi zostaje i jest w A
- zi=1 jeśli vi zostaje i jest w B
- usuwamy max k
- wierzchołek tylko w jednym stanie: 1 <= xi+yi+zi <= 1
- każdy wierzchołek należy do jednego podzbioru:
dla każdego {vi,vj} in E
1 <= yi+yj <= 1
1 <= zi+zj <= 1
Graph Isomorphism <= ILP
dane:
G1, G2
bijekcja f: V1 -> V2 taka, że dla u,v in V1 zachodzi f(u),f(v) in V2
V1={v1,…,vn}
V2={u1,…,un}
- xij=1 jeśli vi jest mapowany na uj
- mapowanie 1:1:
1 <= suma po j (xij) <= 1 (dla każdego wierzchołka z V1 jest tylko jeden w V2)
1 <= suma po i (xij) <= 1 (dla każdego z V2 tylko jeden w V1) - równoważność
dla każdych {va,vb} i {up,uq} takich, że zachodzi:
{va,vb} to krawędź, {up,uq} nie
ORAZ
{va,vb} to nie krawędź, a {up,uq} tak
tworzymy:
1 <= xap + xbq <= 1
Dominating Set <= ILP
dane:
G, k in N
czy istnieje zbiór S taki, że |S| <= k oraz każdy wierzchołek albo należy do S, albo ma sąsiada w S
- xi=1 bierzemy vi do S
- 0 <= suma po i (xi) <= k
- warunek sąsiadów:
dla każdych {vi, vj} in E
1 <= xi + suma po j (xj) <= n - 1 - albo ty, albo sąsiad
dla każdych {vi, vj} in E
1 <= xi + xj <= 1
X3C <= ILP
dane:
B={b1,…,b3k}
k in N
S={S1,…,Sn}
czy istnieje suma takich podzbiorów dająca pełne pokrycie B?
- xi=1 jeśli i-ty (Si) zbiór w rozwiązaniu
- k <= suma po i (xi) <= k
- warunek pokrycia zbioru:
dla każdego bj in B: 1 <= suma po i:bj in Si (xi) <= 1
Bin Packing
ciąg liczb: s1,…,sn in N
k, c in N
czy da się tak podzielić ciąg na co najwyżej k grup, aby suma każdej równała się maksymalnie c?
1.dla każdego i in {1,…,n} i dla każdego j in {1,…,k}:
xij=1 jeśli si w grupie j
2. dla każdego j: 0 <= suma po i (xij * si) <= c
3. zawarcie każdego elementu tylko w 1 grupie:
dla każdego i: 1 <= suma po j (xij) <= 1
Graph-3-Colouring
G, c: V -> {1,2,3}
c(u) /= c(v)
innymi słowy, czy da się pokierować graf tak żeby żadne dwa połączone wierzchołki nie były tego samego koloru?
- dla j in {1,2,3}: xij=1 jeśli vi koloru j
- dokładnie 1 kolor wierzchołka
1 <= suma po j (xij) <= 1 - sąsiedzi różnych kolorów
dla każdego {va,vb} in E: 0 <= xaj+xbj <= 1
Set Packing
S={S1,…,Sn}
k in N
czy można wybrać k parami rozłącznych zbiorów?
- xi=1 bierzemy Si do rozwiązania
- k <= suma po i (xi) <= k
- rozłączność zbiorów:
dla każdego bj in B: 1 <= suma po i:bj in Si, Si in S (xi) <= 1
Half Clique
G
czy graf posiada podgraf pełny rozmiaru |V|/2?
|V| = n
1. xi=1 jeśli vi w klice
2. n/2 <= suma po i (xi) <= n/2
3. warunek kliki:
dla każdego {vi,vj} not in E, in V: 0 <= xi + xj <= 1
Densest-k-Subgraph
G
k, t in N
czy da się wybrać k wierzchołków między którymi występuje co najmniej t krawędzi?
- xi=1 jeśli wybieramy vi
- yi=1 wybieramy ei
- k <= suma po i (xi) <= k
- co najmniej t krawędzi:
t <= suma po i (yi) <= |E| - poprawność wybrania wierzchołków:
dla każdej {va,vb}=ei in E: 0 <= xa + xb - 2yi <= 1
Hitting Set
X={x1,…,xn}
S={S1,…,Am}
k in N
czy da się wybrać k elementów z X tak żeby każdy zbiór S zawierał choć 1 wybrany element?
- zi=1 jeśli xi wybrany
- k <= suma po i (zi) <= k
- pokrycie S:
dla każdego j in {1,…,m}: 1 <= suma po xi in Sj, Sj in S, xi in X (zi)
Hamiltonian Cycle
G
czy da się znaleźć cykl Hamiltona?
- dla każdego i,j in {1,…,n} xij=1 jeśli vi jest na pozycji j
- wybranie 1 wierzchołka na raz:
dla każdego i: 1 <= suma po j (xij) <= 1 - każda pozycja raz:
dla każdego j: 1<= suma po i (xij) <= 1 - między kolejnymi wierzchołkami istnieje krawędź
dla każdego {vi,vj} in E, dla każdego k in {1,…,n-1}: 0 <= xik+xjk+1 <= 1 - krawędź między 1szym a ntym:
dla każdego {vi,vj} not in E: 0 <= xi0+xj0 <= 1
Knapsack
W=(w1,…,wn}
V={v1,…,vn}
k in N
czy da się wybrać taki podzbiór aby suma była jak największa nie przekraczając pojemności k?
- xi=1 wzięty przedmiot wi
- pojemność:
0<= suma po i (wi*v1) <= k
