Optimalisering/Besliskunde 1 College 1 2 september, 2015
Algemene informatie • College: woensdag 13:45-15:30: Leiden – C1 en C2: Gorlaeus gebouw – Zaal DS: De Sitterzaal, Oort gebouw • Werkcollege: vrijdag: Leiden en Delft • Drie sets huiswerkopgaven • Deeltentamen • Tentamen
Eindcijfer = max{tentamencijfer, 0.55×tentamencijfer + 0.25×deeltentamencijfer + 0.2×huiswerkcijfer} Onder de voorwaarde: tentamencijfer ≥ 5.5
Algemene informatie • Informatie en documenten worden op mijn homepage bijgehouden:
http://leovaniersel.wordpress.com/optimalisering • Het deeltentamen is op maandag 2 november 2015, 11:00 – 13:00 in Leiden en Delft. • Inleverdata voor het huiswerk zijn: – maandag 28 september – maandag 26 oktober – maandag 7 december
Wat is optimalisering? Bepaal “de beste” oplossing uit een “gegeven” verzameling oplossingen. Wat is hier moeilijk aan????
Voorbeeld: Je moet gaten boren voor componenten en bedrading van een “printed circuit board” (pcb). De boormachine moet zo snel mogelijk klaar zijn. Hoe kunnen we dit probleem wiskundig modelleren?
Een model gebaseerd op een graaf G: Een graaf bestaat uit “punten” en “kanten” (verbindingen)
De punten representeren de gaten in het pcb. Alle verbindingen tussen punten zijn mogelijk. Als een verbinding wordt gebruikt betekent dit dat de twee verbonden punten (=gaten) achter elkaar worden geboord.
Een graaf waar we uit alle mogelijke verbindingen mogen kiezen
Een graaf
Hoe ziet er een “toegelaten” verzameling verbindingen uit? Ze vormen een route door de gaten. Elk gat wordt precies één keer geboord.
Nog een voorbeeld:
Een mogelijke route:
Goede route?
Deze route is veel korter?
Maar is het de beste?
Hoeveel routes zijn er in een ongerichte graaf met n punten?
Voor ons voorbeeldje: 19,958,400 routes Die zijn makkelijk te bepalen en te vergelijken. Maar dit was maar een klein voorbeeldje...
100 gaten:
394328933682395251776181606966092531147567988843 586631647371266622179724981701671460152142005992 311952088606069459819415128821395121318552530963 312476414965556731428635381658618698494471961222 810725832120127016645932065613714147426638762121 203786951620160628702789784330113015952085162031 175850429398089461111394811851948687360000000000 000000000000000000000000000000000000000 routes
Ouch, we moeten iets slimmers bedenken
Terug naar ons echte voorbeeld:
3038 gaten Beste (=optimale) route:
Hoe pakken we dit aan? Formuleer een optimaliseringsprobleem gebaseerd op het grafen-model: Input (wat weten wij?): De graaf lengte van elke verbinding (kant)
.
en de
Stap 1: Definieer de beslissingsvariabelen (wat willen we eigenlijk weten?)
Stap 2: Formuleer de doelfunctie (wat willen wij maximaliseren of minimaliseren?) Hier: minimaliseer de lengte van de route
Stap 3: Formuleer de voorwaarden (Als we niks doen krijgen alle variabelen waarde 0) (i) De boormachine gaat naar een te boren gat en gaat na het boren weer weg. Dat betekent dat elk punt precies twee verbindingen moet hebben
(ii) Wij willen geen “sub-routes”
Iets ingewikkelder te formuleren maar kan wel lineair!
(iii) Restricties op de variabelwaarden
Oftewel,
Output: De variabelwaarden 0 of 1 voor elke variabele. De variabelen met waarde 1 behoren bij verbindingen die samen een route vormen! Om output te produceren, laten we een algoritme op het model los. Huidig “wereldrecord”: 85.900 punten in een VLSI-toepassing, opgelost in 2006
Belangrijke vragen: Wat is een “goed” wiskundig model voor een gegeven probleem? Hoe ziet er een “optimaliteitsbewijs” eruit? Wat is een “goed” algoritme om het probleem, gegeven het model, op te lossen? Zijn er modellen waarvoor we geen efficiënte (“goede”) algoritmes kennen? Zo ja, hoe kunnen we dat verklaren?
Het net beschreven probleem is een toepassing van het Handelsreizigersprobleem (Traveling Salesman Problem, TSP) Zie http://www.math.uwaterloo.ca/tsp/ voor een boel info!
Wat is optimalisering? Bepaal “de beste” oplossing uit een “gegeven” verzameling oplossingen. Wat is hier moeilijk aan???? De oplossingen zijn impliciet gegeven als een verzameling vectoren die voldoen aan gegeven voorwaarden. Hoe kunnen we oplossingen karakteriseren? Oneindig veel oplossingen? Ook in gevallen waar wij de oplossingen expliciet zouden kunnen opschrijven en vergelijken, zou dit in de meeste gevallen veel te lang duren. WIJ HEBBEN WISKUNDE NODIG (algebra, discrete wiskunde, analyse, algoritmiek…)!!!
OPTIMALISERING Algemene formulering:
zijn functies van o.d.v. = “onder de voorwaarden” In het Engels:
s.t. = “subject to”
Zie appendix
Speciale gevallen:
is convex,
• •
, Als
en
concaaf,
lineair: convexe optimalisering
lineair: lineaire optimalisering : lineaire geheeltallige optimalisering
Focus van dit vak LINEAIRE PROGRAMMERINGS- problemen: LP-problemen LINEAIRE GEHEELTALLIGE PROGRAMMERINGS-problemen: (Eng: INTEGER LINEAR PROGRAMMING): ILP- of IP-problemen
Het gebied ontstond in de 1940-er jaren uit de behoefte om grote logistieke operaties te plannen (“programming”) ivm WW II. Toen kwam ook de eerste computers en kon er gerekend worden! Belangrijke artikelen: George B. Dantzig (1951): Maximization of a linear function of variables subject to linear inequalities. Ralph E. Gomory (1958): Outline of an algorithm for integer solutions to linear programs.
Voorbeeld Probleem: Facility Location • Stel m winkels moeten regelmatig bevoorraad worden. • Er zijn n locaties waar distributiecentra (dc) gevestigd kunnen worden. • Selecteerd locaties voor distributiecentra zodanig dat de totale kosten zo klein mogelijk zijn. – 𝒄𝒄𝒋𝒋 zijn de kosten om een distributiecentrum te openen op locatie j – 𝒅𝒅𝒊𝒊𝒊𝒊 zijn de kosten om winkel i vanuit locatie j te bevoorraden
Formuleren als een ILP-probleem (Integer Linear Programming) • Stap 1: definieer de beslissingsvariabelen – Hoe kun je een oplossing met variabelen beschrijven?
• Stap 2: formuleer de doelfunctie – Wat willen we optimaliseren?
• Stap 3: formuleer de voorwaarden – Zorg er voor dat de beslissingsvariabelen geldige oplossingen beschrijven
Facility Location formuleren met ILP • Stap 1: definieer de beslissingsvariabelen
𝑥𝑥𝑖𝑖𝑖𝑖 = 1 als klant i vanuit locatie j bevoorraad wordt en anders is 𝑥𝑥𝑖𝑖𝑖𝑖 = 0 𝑦𝑦𝑗𝑗 = 1 als op locatie j een distributiecentrum geopend wordt en anders is 𝑦𝑦𝑗𝑗 = 0
• Stap 2: formuleer de doelfunctie
min � 𝑑𝑑𝑖𝑖𝑖𝑖 𝑥𝑥𝑖𝑖𝑖𝑖 + � 𝑐𝑐𝑗𝑗 𝑦𝑦𝑗𝑗 𝑖𝑖,𝑗𝑗
𝑗𝑗
• Stap 3: formuleer de voorwaarden O.d.v. ∑𝑗𝑗 𝑥𝑥𝑖𝑖𝑖𝑖 = 1 𝑥𝑥𝑖𝑖𝑖𝑖 ≤ 𝑦𝑦𝑗𝑗 𝑥𝑥𝑖𝑖𝑖𝑖 , 𝑦𝑦𝑗𝑗 ∈ {0,1}
voor alle 𝑖𝑖 voor alle 𝑖𝑖, 𝑗𝑗 voor alle 𝑖𝑖, 𝑗𝑗
NEIGHBORHOODS Gegeven een toegelaten oplossing
van een bepaald
probleem, de buurruimte (neighbourhood) van
is de
verzameling oplossingen die in een bepaalde opzicht “dichtbij” zijn.
Voorbeeld: TSP, 2-exchange neighborhood verzameling oplossingen die kunnen worden verkregen door 2 kanten uit de tour te verwijderen en daarna 2 nieuwe kanten toe te voegen, zodanig dat een nieuwe tour wordt gecreёerd.
Een “2-exchange”:
Een “2-exchange”:
Def. Een oplossing is een lokaal optimum m.b.t. als voor iedere Een oplossing
is een globaal optimum als
voor iedere
Def. Gegeven een optimaliseringsprobleem met verzameling toegelaten oplossingen en buurruimte . Als elke die locaal optimaal is m.b.t. ook globaal optimaal is, dan noemen we buurruimte exact.
Voorbeeld: Voor TSP:
is niet exact, maar
wel.
Grafen Een graaf G is een paar, G=(V,E) V = verzameling knooppunten/knopen (nodes, vertices) E = verzameling kanten (edges); ongeordend paar punten Voorbeeld:
𝑣𝑣1
𝑣𝑣2
𝑣𝑣3
𝑣𝑣4
Gerichte grafen Een gerichte graaf D is een paar D=(V,A) V = verzameling knooppunten/knopen (nodes, vertices) A = verzameling pijlen (arcs); geordende paren knopen Voorbeeld:
𝐷𝐷 = ( 𝑣𝑣1 , 𝑣𝑣2 , 𝑣𝑣3 , 𝑣𝑣4 , {[𝑣𝑣1 , 𝑣𝑣2 ], [𝑣𝑣2 , 𝑣𝑣3 ], [𝑣𝑣4 , 𝑣𝑣1 ], [𝑣𝑣4 , 𝑣𝑣3 ], [𝑣𝑣1 , 𝑣𝑣3 ]}) 𝑣𝑣1
𝑣𝑣2
𝑣𝑣3
𝑣𝑣4
Een grafenprobleem formuleren met ILP (Integer Linear Programming) • Probleem: Kortste Pad • Gegeven: gerichte graaf D=(V,A) met lengte 𝑙𝑙𝑖𝑖𝑖𝑖 voor elke pijl 𝑎𝑎 = [𝑖𝑖, 𝑗𝑗] en twee speciale knopen s en t. • Vind: een kortste pad van s naar t.
𝒔𝒔 2
4
2 3
3 3
3
2 1
6
3 2
𝒕𝒕
Een grafenprobleem formuleren met ILP (Integer Linear Programming) • Probleem: Kortste Pad • Gegeven: gerichte graaf D=(V,A) met lengte 𝑙𝑙𝑖𝑖𝑖𝑖 voor elke pijl 𝑎𝑎 = [𝑖𝑖, 𝑗𝑗] en twee speciale knopen s en t. • Vind: een kortste pad van s naar t.
𝒔𝒔 2
4
2 3
3 3
3
2
6 Het kortste pad heeft lengte 10
1
3 2
𝒕𝒕
Een grafenprobleem formuleren met ILP (Integer Linear Programming) • Probleem: Kortste Pad • Gegeven: gerichte graaf D=(V,A) met lengte 𝑙𝑙𝑖𝑖𝑖𝑖 voor elke pijl 𝑎𝑎 = [𝑖𝑖, 𝑗𝑗] en twee speciale knopen s en t. • Vind: een kortste pad van s naar t. • Formuleer als een ILP-probleem
– Stap 1: definieer de beslissingsvariabelen
• Hoe kun je een oplossing met variabelen beschrijven?
– Stap 2: formuleer de doelfuctie • Wat willen we optimaliseren?
– Stap 3: formuleer de voorwaarden
• Zorg er voor dat de beslissingsvariabelen geldige oplossingen beschrijven
Kortste Pad Probleem formuleren met ILP • Stap 1: definieer de beslissingsvariabelen 1 𝑥𝑥𝑖𝑖𝑖𝑖 = � 0
Als het pad pijl 𝑖𝑖, 𝑗𝑗 gebruikt Anders
• Stap 2: formuleer de doelfunctie min � 𝑙𝑙𝑖𝑖𝑖𝑖 𝑥𝑥𝑖𝑖𝑖𝑖 [𝑖𝑖,𝑗𝑗]∈𝐴𝐴
• Stap 3: formuleer de voorwaarden 1 voor 𝑖𝑖 = 𝑠𝑠 O.d.v. ∑𝑗𝑗 𝑥𝑥𝑖𝑖𝑖𝑖 − ∑𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗 = �−1 voor 𝑖𝑖 = 𝑡𝑡 0 voor alle andere 𝑖𝑖 𝑥𝑥𝑖𝑖𝑖𝑖 ∈ {0,1} voor alle i,j
Boom en bos is samenhangend als er een pad bestaat tussen elk tweetal knopen. Een boom (tree) is een samenhangende graaf zonder circuits.
Lemma: Zij een ongerichte graaf. De volgende beweringen zijn equivalent: • • •
is een boom is samenhangend en heeft kanten heeft geen circuits, maar als een kant aan toegevoegd dan ontstaat er een uniek circuit.
Een bos (forest) is een verzameling bomen.
wordt
Een deelgraaf van een samenhangende graaf is een opspannende boom in als een boom is en . . • Probleem: Minimum Spanning Tree (MST) • Gegeven: graaf G=(V,E) met lengte 𝑑𝑑𝑖𝑖 voor elke kant ei ∈ 𝐸𝐸. • Vind: een opspannende boom van G zodanig dat de som van de lengtes van de lijnen in de boom minimaal is. u 2
2 1 v
x 4
3 w
Een deelgraaf van een samenhangende graaf is een opspannende boom in als een boom is en . . • Probleem: Minimum Spanning Tree (MST) • Gegeven: graaf G=(V,E) met lengte 𝑑𝑑𝑖𝑖 voor elke kant ei ∈ 𝐸𝐸. • Vind: een opspannende boom van G zodanig dat de som van de lengtes van de lijnen in de boom minimaal is. u 2
2 1 v
x 4
3 w
De minimum opspannende boom heeft lengte 6.
MST formuleren met LP: voorbeeld • Beslissingsvariabelen: 𝑥𝑥𝑖𝑖 = 1 als lijn 𝑒𝑒𝑖𝑖 in de boom zit en anders is 𝑥𝑥𝑖𝑖 = 0 u
v
𝒆𝒆𝟏𝟏
𝒆𝒆𝟑𝟑
𝒆𝒆𝟐𝟐
w
min 𝑑𝑑1 𝑥𝑥1 + 𝑑𝑑2 𝑥𝑥2 + 𝑑𝑑3 𝑥𝑥3 o.d.v. 𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 = 2 𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 ≥ 0 𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , ≤ 1 (𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 geheeltallig)
MST formuleren met LP: voorbeeld u
v
Alle hoekpunten zijn geheeltallig, dus de geheeltalligheidseisen kunnen worden weggelaten!
𝒆𝒆𝟏𝟏
𝒆𝒆𝟑𝟑
𝒆𝒆𝟐𝟐
w
min 𝑑𝑑1 𝑥𝑥1 + 𝑑𝑑2 𝑥𝑥2 + 𝑑𝑑3 𝑥𝑥3 o.d.v. 𝑥𝑥1 + 𝑥𝑥2 + 𝑥𝑥3 = 2 𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 ≥ 0 𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 , ≤ 1 (𝑥𝑥1 , 𝑥𝑥2 , 𝑥𝑥3 geheeltallig)
Netwerk Een netwerk is een gerichte graaf samen met een startpunt (source) met in-graad 0, een eindpunt (terminal) met uit-graad 0, bovengrens (capaciteit) op de stroom op elke pijl .
𝒔𝒔
12
7 3 4
7
2
4
2
5 1
3
Capaciteit
4 12
𝒕𝒕
Een grafenprobleem formuleren met LP (Linear Programming) • Probleem: Max Flow • Gegeven: netwerk 𝑛𝑛 = (𝑠𝑠, 𝑡𝑡, 𝑉𝑉, 𝐴𝐴, 𝑏𝑏) • Vind: een maximale stroom van s naar t
– In elke knoop behalve s en t is er behoud van stroom – Op elke pijl [u,v] is de stroom maximaal b(u,v).
𝒔𝒔
6 (7) 0(3)
5 (7)
Stroom Capaciteit
10 (12)
4(4)
0(2)
5(5)
1(1) 1 (3)
2 (2)
3(4)
4(4) 9 (12)
𝒕𝒕
Max Flow formuleren met LP • Stap 1: definieer de beslissingsvariabelen 𝑥𝑥𝑖𝑖𝑖𝑖 is de stroom over pijl [i,j]
• Stap 2: formuleer de doelfunctie max � 𝑥𝑥𝑠𝑠𝑠𝑠 [𝑠𝑠,𝑗𝑗]∈𝐴𝐴
• Stap 3: formuleer de voorwaarden O.d.v. ∑𝑗𝑗 𝑥𝑥𝑖𝑖𝑖𝑖 − ∑𝑗𝑗 𝑥𝑥𝑗𝑗𝑗𝑗 = 0 voor alle 𝑖𝑖 ∈ 𝑉𝑉 ∖ {𝑠𝑠, 𝑡𝑡} 𝑥𝑥𝑖𝑖𝑖𝑖 ≤ 𝑏𝑏 𝑖𝑖, 𝑗𝑗
𝑥𝑥𝑖𝑖𝑖𝑖 ≥ 0
voor alle 𝑖𝑖, 𝑗𝑗 ∈ 𝑉𝑉
voor alle 𝑖𝑖, 𝑗𝑗 ∈ 𝑉𝑉
Trucs voor ILP formuleringen • Laat 𝑥𝑥𝑖𝑖 , 𝑦𝑦𝑗𝑗 ∈ {0,1} binaire variabelen zijn
• “als 𝒙𝒙𝒊𝒊 = 𝟏𝟏 dan 𝒚𝒚𝒋𝒋 = 𝟏𝟏” kan gemodelleerd worden als: 𝒚𝒚𝒋𝒋 ≥ 𝒙𝒙𝒊𝒊 • “als 𝒙𝒙𝒊𝒊 = 𝟎𝟎 dan 𝒚𝒚𝒋𝒋 = 𝟎𝟎” kan gemodelleerd worden als: 𝒚𝒚𝒋𝒋 ≤ 𝒙𝒙𝒊𝒊
Trucs voor ILP formuleringen • Laat 𝑧𝑧 ∈ {0,1} en 𝑥𝑥 ∈ ℝ variabelen zijn en 𝑎𝑎, 𝑏𝑏 ∈ ℝ constantes.
• “als 𝒛𝒛 = 𝟎𝟎 dan 𝒂𝒂𝒂𝒂 ≤ 𝒃𝒃” kan gemodelleerd worden als:
𝒂𝒂𝒂𝒂 ≤ 𝒃𝒃 + 𝑴𝑴𝑴𝑴
oftewel 𝒂𝒂𝒂𝒂 − 𝑴𝑴𝑴𝑴 ≤ 𝒃𝒃
• “als 𝒛𝒛 = 𝟏𝟏 dan 𝒂𝒂𝒂𝒂 ≤ 𝒃𝒃” kan gemodelleerd worden als:
𝒂𝒂𝒂𝒂 ≤ 𝒃𝒃 + 𝑴𝑴(𝟏𝟏 − 𝒛𝒛)
oftewel 𝒂𝒂𝒂𝒂 + 𝑴𝑴𝑴𝑴 ≤ 𝒃𝒃 + 𝑴𝑴
• met M een heel groot getal.
Appendix:
CONVEXE FUNCTIES EN VERZAMELINGEN Def. Een convexe combinatie van twee gegeven punten is elk punt dat geschreven kan worden als
dat wil zeggen, elk punt dat op het lijnsegment ligt tussen (en inclusief) de punten en . Def. Een verzameling is convex als die alle convexe combinaties bevat van paren punten .
𝑥𝑥
𝑦𝑦
convex
𝑥𝑥
𝑦𝑦
convex
𝑦𝑦
𝑥𝑥
Niet convex
Lemma. De doorsnede van convexe verzamelingen convexe verzameling.
is een
Bewijs. Als en tot behoren, dan behoren ze tot elke deelverzameling . Iedere convexe combinatie van en behoren dan ook tot elke , en daardoor ook tot .
Def. Zij
een convexe verzameling. De functie
is convex in 𝐒𝐒 als voor ieder paar punten 𝑥𝑥, 𝑦𝑦 ∈ 𝑆𝑆 geldt dat Als
zeggen we dat
convex is.
Def. Een functie gedefinieerd in een convexe verzameling noemen we concaaf in 𝐒𝐒 als convex is in . Een lineaire functie is convex en concaaf!
concaaf
convex
lineair
Begrippen m.b.t. optimaliseringsproblemen Def. Een instantie (geval) van een optimaliseringsprobleem is een paar
waarbij
oplossingen en
is de verzameling toegelaten
is de kostenfunctie (doelfunctie):
We willen een oplossing
bepalen zodanig dat
voor iedere noemen we (globaal) optimaal!
. Zo’n oplossing
Def. Een probleem(type) is de verzameling van al zijn instanties. Voorbeelden: 1. Probleem: Het Handelsreizigersprobleem (Traveling Salesman Problem (TSP)) Gegeven zijn steden en een afstandenmatrix . Een tour (of route) is een gesloten pad dat elke “stad” precies één keer bezoekt. Bepaal de kortste tour. Een instantie wordt bepaald door een gegeven afstandenmatrix.
en een specifieke
2. Probleemtype: Lineaire optimalisering, LP
Gegeven een -vector
matrix
, een
-vector
en een
, kunnen we een instantie van LP definiëren als: (toegelaten “gebied”) (doelfunctie)
Begrippen m.b.t grafen Ongerichte grafen grenst aan (is adjacent to)
als er een kant
raakt (is incident to)
bestaat
en
De graad (degree) 𝒅𝒅(𝒗𝒗) van een knoop 𝑣𝑣 is het aantal kanten dat 𝑣𝑣 raakt 𝑣𝑣1
𝑣𝑣2
𝑣𝑣3
𝑣𝑣4
Hier grenst 𝑣𝑣1 aan 𝑣𝑣2 , 𝑣𝑣3 en 𝑣𝑣4 . De graad van 𝑣𝑣1 is dus 3.
Een wandeling w in G is een aaneenschakeling van knooppunten
zodanig dat De wandeling is gesloten als
v
en
.
w [y,u,v,y,x,z] is een wandeling
y
u x
z
[y,u,v,y,x,z,w,y] is een gesloten wandeling
Een wandeling zonder repetities van knopen is een pad (path). v
w [y,u,v,w,z] is een pad
y
u
z
x
Een gesloten wandeling zonder repetities van knopen is een circuit of kring (cycle). v
w [y,u,v,w,z,x,y] is een circuit
y
u x
z
Gerichte grafen De in-graad (indegree) 𝒅𝒅− 𝒗𝒗 van knoop 𝑣𝑣, is het aantal pijlen dat 𝑣𝑣 als eindpunt heeft. De uit-graad (outdegree) 𝒅𝒅+ 𝒗𝒗 van knoop 𝑣𝑣, is het aantal pijlen dat 𝑣𝑣 als beginpunt heeft. 𝑣𝑣1
𝑣𝑣2
𝑣𝑣3
𝑣𝑣4
𝑑𝑑 − 𝑣𝑣1 = 1 𝑑𝑑 + 𝑣𝑣1 = 2
Analoog met het ongerichte geval hebben wij gerichte wandeling, gericht pad, gericht circuit
Bipartiete grafen Een graaf heet bipartiet als er een partitie van de knopen in en bestaat, zodanig dat elke kant één eindpunt in en één eindpunt in heeft.
niet bipartiet
bipartiet
bipartiet
