Huiswerk # 4, TW2020/Besliskunde 1 2014/2015 Inleveren: Vrijdag 12 december 2014 1. Gegeven is het volgende IP-probleem: max z = 13x1 + 8x2 x1 5x1 + + 2x2 2x2 ≤ ≤ 10 20 x2 ≥ 0, geheeltallig odv x1 , Los op met behulp van branch-and-bound. N.B. De LP-relaxaties mogen grafisch, of met behulp van een optimaliseringspakket (bv Qsopt), opgelost worden. Gebruik volgende zoekstrategie: • depth-first, • ≤-tak eerst, • fractie dichtstbij 21 . 2. Gegeven is het probleem IP max zIP = odv 2x1 x1 −x1 4x1 x1 , + + + + x2 x2 2x2 2x2 x2 , + + − + 4x3 2x3 x3 x3 x3 ≥ ≤ ≥ ≤ 0, geheeltallig 10 5 10 De LP-relaxatie van IP is opgelost met behulp van het simplexalgoritme. Het verkregen tableau ziet er als volgt uit: basis ¯b x1 x2 x3 s1 e2 s3 −z − 55 4 − 35 4 0 0 0 − 74 − 94 s1 x2 x3 5 4 15 4 5 2 − 19 4 0 1 0 0 0 1 1 0 0 − 34 − 14 − 54 3 4 5 2 1 2 1 4 1 2 a) Bepaal een “Gomory cut” (Gomorysnede) van de rij van het Simplextableau behorend bij basisvariabele x3 . b) Druk de gevonden snede uit in termen van de oorspronkelijke variabelen x1 , x2 en x3 . c) Voeg de Gomorysnede toe aan het optimale tableau en heroptimaliseer met behulp van Duale Simplex. Wat is de optimale oplossing van de LPrelaxatie na het toevoegen van de snede? d) Is de in c) verkregen oplossing ook optimaal voor IP? Motiveer je antwoord. 1 3. Het probleem ILP is als volgt gedefini¨eerd: Gegeven: Een geheeltallige m x n matrix A, een n-vector c, een m-vector b en een integer k Probleem: Bestaat er een geheeltallige n-vector x ≥ 0 zdd Ax = b en cT x = k? Het probleem NETWORK FLOW is als volgt gedefini¨eerd: Gegeven: Een netwerk N = (s, t, V, A, c) en een integer k. Probleem: Heeft het netwerk N een flow van s naar t ter grootte k? (De functie c geeft de capaciteit van de pijlen) Gegeven is dat ILP NP-volledig is. a) Laat zien dat NETWORK FLOW ∝ ILP b) Betekent dit dat NETWORK FLOW NP-volledig is? Motiveer je antwoord! 2 4. Het probleem VERTEX COVER is als volgt gedefini¨eerd: Gegeven: Ongerichte graaf G=(V,E). Probleem: Wat is de kleinste vertex cover in de graaf G? (Een vertex cover is een verzameling knopen, zdd voor elke kant geldt dat deze grenst aan tenminste ´e´en van de knopen in de verzameling.) De LP-relaxatie voor VERTEX COVER is gegeven door: X zLP = min cv xv v∈V odv x u + xv ≥ 1 ∀{u, v} ∈ E xv ≥ 0 ∀v ∈ V Het bijbehorende duale probleem is: X zD = max ye e∈E odv X ye ≤ cv ∀v ∈ V (∗) e∈δ(v) ye ≥ 0 ∀e ∈ E Gegeven is het volgende algoritme voor VERTEX COVER: Input: Een graaf G = (V, E) Output: Een vertex cover Initialisatie: ye := 0, ∀e ∈ E, E 0 := E, C := ∅; while E 0 6= ∅ do kies een e = {u, v} ∈ E 0 willekeurig; Verhoog ye totdat (*) gelijkheid geeft voor u of v, zeg dat v de bijbehorende knoop is; C := C ∪ {v}, E 0 := E 0 \δ(v); end return C a) Toon aan dat dit algoritme inderdaad een vertex cover retourneert. b) Toon aan dat dit algoritme een 2-approximatiealgoritme is voor VERTEX COVER Hints: Er geldt: P • e∈δ(v) ye = cv ∀v ∈ C P P P • zALG (C) = v∈C cv = v∈C ( e∈δ(v) ye ) Maak gebruik van de zwakke dualiteitsstelling. 3