Branch-and-Bound en Cutting Planes

Branch-and-Bound en Cutting Planes

Vandaag: Er is nog geen algoritme om ILP’s in polynomiale tijd op te lossen. Twee opties: 1

Exponentiëel algoritme dat optimale oplossing geeft

2

Polynomiaal algoritme dat niet-optimale oplossing geeft

P.L. van den Berg Faculteit EWI 19 november 2014

1


Exponentiëel algoritme dat optimale oplossing geeft ⇒ (VANDAAG)

2

Polynomiaal algoritme dat niet-optimale oplossing geeft ⇒ (College 12)


1


Exponentiëel algoritme dat optimale oplossing geeft ⇒ (VANDAAG)

2

Polynomiaal algoritme dat niet-optimale oplossing geeft ⇒ (College 12)

Vandaag 2 methoden: 1

Branch-and-Bound

2

Cutting planes (geldige ongelijkheden)


1

Branch-and-Bound Idee: ILP’s zijn moeilijk, LP’s zijn makkelijk. We gebruiken LP om ILP op te lossen. Belangrijke relatie: ZTOEG ≤ ZIP ≤ ZLP

(Maximalisatie)

ZLP ≤ ZIP ≤ ZTOEG

(Minimalisatie)

Branchen: Het probleem opsplitsen in deelproblemen, zdd elke toegelaten oplossing bevindt zich in exact één deelprobleem. Bounden: Boven- en ondergrens bijhouden voor oplossing. Gebruik deze grenzen voor het snoeien van zoekboom. Snoeien: Concluderen dat een deelprobleem niet verder onderzocht hoeft te worden P.L. van den Berg Faculteit EWI 19 november 2014

2

Branch-and-Bound (Minimalisatie)

Lijst met nog te beschouwen deelproblemen Bovengrens voor hele boom Ondergrens per deelprobleem In geval van geheeltallige doelstellingscoëfficiënten: ondergrens naar boven afronden


3

Voorbeeld Branch-and-Bound

ZIP = min −4x1 + x2 odv 7x1 − 2x2 ≤ 14 x2 ≤ 3 2x1 − 2x2 ≤ 3 x1 , x2 ≥ 0, geheeltallig


4

Wanneer kunnen we snoeien? (Maximalisatie) 1

Niet-toegelaten LP-relaxatie deelprobleem ⇒ Geen geheeltallige oplossingen in dit deelprobleem

2

Geheeltallige LP-relaxatie in deelprobleem ⇒ Toegelaten (integer) oplossing gevonden. ⇒ Globale ondergrens updaten

3

Bovengrens deelprobleem kleiner dan globale ondergrens ⇒ Er is geen betere oplossing in dit deelprobleem dan de al gevonden integer oplossing

Merk op: Ondergrenzen zijn globaal, terwijl bovengrenzen alleen geldig in deelprobleem


5

Wanneer kunnen we snoeien? (Minimalisatie) 1

Niet-toegelaten LP-relaxatie deelprobleem ⇒ Geen geheeltallige oplossingen in dit deelprobleem

2

Geheeltallige LP-relaxatie in deelprobleem ⇒ Toegelaten (integer) oplossing gevonden. ⇒ Globale bovengrens updaten

3

Ondergrens deelprobleem kleiner dan globale bovengrens ⇒ Er is geen betere oplossing in dit deelprobleem dan de al gevonden integer oplossing

Merk op: Bovengrenzen zijn globaal, terwijl ondergrenzen alleen geldig in deelprobleem


6

Implementatieaspecten

1

2

Welke variabele kiezen we om te branchen? ⇒ Fractie het dichtst bij 12 Welke deelprobleem beschouwen we eerst? Depth-first search: Deelprobleem zo diep mogelijk in de boom Best-node first: Deelprobleem met beste waarde van de LP-relaxatie

⇒ Vaak mengsel van beide


7

Rekentijd Branch-and-Bound

Stel alle variabelen zijn 0-1 variabelen. ⇒ Maximaal aantal eindpunten: 2n ⇒ Maximaal aantal knopen/deelproblemen: 20 + 21 + 22 + ... + 2n =

1−2n+1 1−2

= 2n+1 − 1

Exponentiëel aantal deelproblemen Werkcollege: voorbeeld waarin inderdaad exponentiëel veel deelproblemen opgelost moeten worden


8

Cutting Planes

zIP = min odv

cT x Ax ≤ b x ≥ 0, geheeltallig

Laat S de verzameling toegelaten punten zijn. Definitie: Een polyeder P = {x ∈ Rn≥0 |A0 x ≤ b 0 } noemen we een formulering voor S als geldt P ∩ Zn = S. Vorige week gezien dat er meerdere formuleringen bestaan voor een gegeven verzameling S. ⇒ Er bestaan zelfs oneindig veel formuleringen voor S P.L. van den Berg Faculteit EWI 19 november 2014

9

Sterkte van een formulering Een formulering P 0 is tenminste even sterk als een formulering P als geldt P 0 ⊆ P Definitie: Een ongelijkheid αx ≤ β is geldig voor S als αx ≤ β voor iedere x ∈ S. Het toevoegen van een geldige ongelijkheid aan P resulteert in een formulering P 0 die tenminste even sterk is. Wat is de sterkst mogelijke formulering? ⇒ Conv(S), het convexe omhulsel van de toegelaten punten S. Merk op: Met een expliciete omschrijving van Conv(S) kunnen we ILP oplossen met LP. ⇒ Het vinden van conv(S) kan echter niet in polynomiale tijd P.L. van den Berg Faculteit EWI 19 november 2014

10

Gomory’s cutting planes

We zoeken niet het volledige convexe omhulsel Fractioneel deel van optimale oplossing LP-relaxatie geeft geldige ongelijkheid Stop wanneer LP-relaxatie geheeltallig optimum heeft ⇒ Alle snedes zijn “geldig”, dus ook optimum voor IP


11

Voorbeeld Gomory’s cutting planes

ZIP = max 4x1 − x2 odv 7x1 − 2x2 ≤ 14 x2 ≤ 3 2x1 − 2x2 ≤ 3 x1 , x2 ≥ 0, geheeltallig (Zelfde voorbeeld als voor Branch-and-Bound)


12

Duale simplex algoritme

Zowel bij B&B als bij cutting planes moet herhaaldelijk een LP-relaxatie worden opgelost Moeten we iedere keer opnieuw beginnen met simplex? ⇒ Nee, we gebruiken duale simplex algoritme Oude oplossing blijft duaal toegelaten na toevoeging van extra voorwaarde.


13

Voorbeeld duale simplex


14

Duale simplex algoritme Initialisatie: Basisoplossing, niet-noodzakelijk toegelaten, met c¯j ≤ 0

∀j (maximalisatie)

c¯j ≥ 0

∀j (minimalisatie)

Uittredende variabele: xB(i 0 ) zdd b¯i 0 = min{b¯i |b¯i < 0} Als b¯i ≥ 0 ∀i, STOP, huidige basisoplossing is toegelaten en optimaal. c¯ 0

c¯ 0

i j

i j

Intredende variabele: xj 0 zdd | ¯a 0j 0 | = min{| ¯a 0j 0 | : ¯ai 0 j 0 < 0} Als ¯ai 0 j ≥ 0 ∀j, STOP, probleem heeft geen toegelaten oplossing. Anders, voer pivot uit en ga naar 1


15

Branch-and-Bound en Cutting Planes

Recommend Documents