1. Diszkrét Optimalizálás Bevezetés és Alapfogalmak
A tárgy II. részéről
1. alkalom 2006.X.11. 8:00-10:05 IB.141
Alkalmazott optimalizálás és játékelmélet (Applied Optimisation and Game Theory)
Dr. Cinkler Tibor cinkler()tmit.bme.hu http://opti.tmit.bme.hu/optgame/ http://www.vdk.bme.hu/targykov/doktorandusz/vittd097.htm vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
1
•
•
• • • • •
Alaklmazott (Applied) Folytonos Optimalizálás (Continuous optimization) Operáció Kutatás (Operations Research) Diszkrét Optimalizálás (Discrete Optimisation) Kombinatorikus Optimalizálás (Combinatorial Optimisation)
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Applied - Alkalmazott
Operáció Kutatás http://en.wikipedia.org/wiki/Operations_research
• Applied Mathematics is a branch of mathematics that concerns itself with the mathematical techniques typically used in the application of mathematical knowledge to other domains.
• Operations research, operational research, or simply OR is an interdisciplinary science which deploys scientific methods like mathematical modeling, statistics, and algorithms to decision making in complex real-world problems which are concerned with coordination and
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
4
cinkler()tmit.bme.hu
5
cinkler()tmit.bme.hu
•
•
7
Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. In particular, it is concerned with "counting" the objects in those collections (enumerative combinatorics), with deciding when the criteria can be met, with constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), with finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and with finding algebraic structures these objects may have (algebraic combinatorics). Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory that sits at the intersection of several fields, including artificial intelligence, mathematics and software engineering. Combinatorial optimization algorithms solve instances of problems that are believed to be hard in general, by exploring the usually-large solution space of these instances. Combinatorial optimization algorithms achieve this by reducing the effective size of the space, and by exploring the space efficiently.
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
6
Folytonos → Diszkrét
http://en.wikipedia.org/wiki/Combinatorial_optimization
http://en.wikipedia.org/wiki/Discrete_optimization Discrete optimization is a branch of optimization in applied mathematics and computer science. As opposed to continuous optimization, the variables used in the objective function (or some of them) are restricted to assume only discrete values, such as the integers. Problems of combinatorial optimization can be formulated in terms of discrete optimization, however methods of their solution are often different.
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
3
execution of the operations within an organization.
WikiPedia: Kombinatorikus Optimalizálás
The word discrete comes from the Latin word discretus which means separate. In discrete mathematics, without notion of continuity, a discrete set is a countable set; this concept is also important for combinatorics, probability theory, and statistical theory. In discrete mathematics and in theoretical computer science, the abstract world is usually modeled as a discrete space with discrete time. Discrete mathematics, also called finite mathematics, is the study of mathematical structures that are fundamentally discrete, in the sense of not supporting or requiring the notion of continuity. Most, if not all, of the objects studied in finite mathematics are countable sets, such as integers, finite graphs, and formal languages. Discrete mathematics has become popular in recent decades because of its applications to computer science. Concepts and notations from discrete mathematics are useful to study or describe objects or problems in computer algorithms and programming languages. In some mathematics curricula, finite mathematics courses cover discrete mathematical concepts for business, while discrete mathematics courses emphasize concepts for computer science majors. Algorithmics - a study of methods of calculation;
cinkler()tmit.bme.hu
• • • • •
http://en.wikipedia.org/wiki/Applied_mathematics
Diszkrét • •
2
Folytonos Kevert (Mixed) Diszkrét (Disrete) Egészértékű (Integer) Bináris (0/1 vagy 0-1) változók (Binary) Ebből is a diszkrét a legbonyolultabb!
http://en.wikipedia.org/wiki/Continuous_optimization
http://en.wikipedia.org/wiki/Discrete_mathematics
•
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• • • • • •
Folytonos Optimalizálás • Continuous optimization is a branch of optimization in applied mathematics. As opposed to discrete optimization, the variables used in the objective function can assume real values, e.g., values from intervals of the real line.
cinkler()tmit.bme.hu
cinkler()tmit.bme.hu
Bevezetés – Eddig folytonos → most diszkrét!
Vázlat: • 1. Diszkrét optimalizálás bevezetés és alapfogalmak • 2. Diszkrét optimalizálás módszertana • 3. Meta-heurisztikus módszerek • 4. ILP alapok és trükkük
vittd097 ― 2006 ősz
cinkler()tmit.bme.hu
•
• 2004 őszén tartottuk először a tárgyat heti kétórásként ― játákelmélet nélkül • 2005 őszén heti 4 óra (kb 1/3-a játékelmélet) ― „tábla+kréta” • 2006 ősz heti 4 óra ― „ppt”
• Ha bináris és több változó is van, akkor ennél rosszabb a helyzet! • Például 10 többtermékes egységnyi osztatlan folyamnak keresünk 0,99 kapacitású hálózatban max folyamot: 0 nulla lesz • Ha folytonos esetben nézzük, és van 10 független út akkor 9,9 egységnyi folyamot kapunk... • (Ha 11 út, akkor belefér az egész)
8
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
9
LP→ILP •
LP→ILP
•
Standard form is the usual and most intuitive form of describing a linear programming problem. It consists of the following three parts: A linear function to be maximized
•
Problem constraints of the following form
•
A célfüggvényben szerepelő változók: x1, x2 értelmezési tartománya – – – – –
– e.g. maximize – e.g. • •
•
Non-negative variables
• • •
– e.g. •
•
The problem is usually expressed in matrix form, and then becomes: – maximize – subject to
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
10
•
A Tutorial on Integer Programming
•
http://mat.gsia.cmu.edu/orclass/integer/integer.html
•
Az ILP csak egy a diszkrét optimalizálás eszköztárából: „Ágyúval lövünk a verébre”
cinkler()tmit.bme.hu
•
Pl. Matroidok Pl. Kruskal és Prim algoritmus feszítő fákra Problémafüggő Mohó módszer, iteratívan részmegoldásokon át a teljesig. ILP-vel is lehet, hisz mindent lehet ILP-vel, de nincs értelme, mert sokkal bonyolultabb mint a mohó! „Testreszabottan” a legjobb! 2
3 6 3
3 3 3
1 4 5
1
8
cinkler()tmit.bme.hu
3
9
2 3 3
1
3
2
9
8 3
7
3
1 4 5
1 9 8
1
3
2
http://en.wikipedia.org/wiki/Computational_complexity_theory
• Sztochasztikus (stochastic) (randomised) methods mostly • Heuristics, meta-heuristics, generally applicable heuristics for global optimisation • Empiric (tapasztalati) 11
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Approximáció
Sztochasztikus
http://en.wikipedia.org/wiki/Approximation
http://en.wikipedia.org/wiki/Stochastic
12
• Stochastic, from the Greek "stochos" or "goal", means of, relating to, or characterized by conjecture and randomness. A stochastic process is one whose behavior is non-deterministic in that the next state of the environment is partially but not fully determined by the previous state of the environment. An antonym is astochastic, because its being one is predicated on having an opposite.
9
3
8
7
3
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
13
cinkler()tmit.bme.hu
•
A random sample is one chosen by a method involving an unpredictable component.
http://en.wikipedia.org/wiki/Random_sample:
•
http://en.wikipedia.org/wiki/Applications_of_randomness • •
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Eredmény minősége
Futási idő
http://en.wikipedia.org/wiki/Approximation_theory
3 6 3
Randomised
•
•
An approximation is an inexact representation of something that is still close enough to be useful. Although approximation is most often applied to numbers, it is also frequently applied to such things as mathematical functions, shapes, and physical laws.
http://en.wikipedia.org/wiki/Randomization •
• Bonyolultság elmélet Computational complexity theory
x1, x2 ∈ R (valós szám) - folytonos x1, x2 ∈{d1, d2, ...dN} (N tetszéleges diszkrét érték) x1, x2 ∈N vagy x1, x2 ∈N0 vagy x1, x2 ∈Z vagy x1, x2 ∈Z+, stb. x1, x2 ∈{0,1} bináris x1∈{0,1}, x2 ∈R kevert – fentiek tetszőleges kombinaciója, jellemzően folytonos és diszkrét változó is van
integer programming (IP) or integer linear programming (ILP) 0-1 integer programming mixed integer programming (MIP)
A mohó algoritmus is adhat globális optimumot • • • • •
Globális Optimum vagy Approximáció?
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
16
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
14
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Heurisztika
Metaheurisztika
http://en.wikipedia.org/wiki/Heuristic
http://en.wikipedia.org/wiki/Metaheuristic
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
15
• A metaheuristic is a heuristic method for solving a very general class of computational problems by combining user given black-box procedures — usually heuristics themselves — in a hopefully efficient way. The name combines the Greek prefix "meta" ("beyond", here in the sense of "higher level") and "heuristic" (from ευρισκειν, heuriskein, "to find"). • Metaheuristics are generally applied to problems for which there is no satisfactory problem-specific algorithm or heuristic; or when it is not practical to implement such a method. Most commonly used metaheuristics are targeted to combinatorial optimization problems, but of course can handle any problem that can be recast in that form, such as solving boolean equations.
A heuristic is a replicable method or approach for directing one's attention in learning, discovery, or problem-solving. It is originally derived from the Greek "heurisko" (ευρίσκω, the verb from which Archimedes's famous exclamation of "eureka" was derived ), which means "I find". The term was introduced in the 4th century AD by Pappus of Alexandria. Lexical note: The name of the topic is heuristic (not "heuristics"); a particular technique of directing your attention toward discovery is a heuristic, two or more of these are heuristics, and the adjective for "pertaining to how something is discovered" is heuristic. The mathematician George Pólya popularized heuristics in the mid–20th century in his book, How to Solve It. Two fundamental goals in computer science are finding algorithms with provably good run times and with provably good or optimal solution quality. A heuristic is an algorithm that gives up one or both of these goals; for example, it usually finds pretty good solutions, but there is no proof the solutions could not get arbitrarily bad; or it usually runs reasonably quickly, but there is no argument that this will always be the case.
cinkler()tmit.bme.hu
cinkler()tmit.bme.hu
17
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
18
Néhány (meta)heurisztikus módszer példa
Empirical
http://en.wikipedia.org/wiki/Metaheuristic: • • • • • • • • • • • • • • • • • • • •
• http://en.wikipedia.org/wiki/Empirical • ...use of working hypotheses that are testable using observation or experiment. In this sense of the word, scientific statements are subject to and derived from our experiences or observations.
Brute-force search (exact) Exhaustive Search Branch and bound (exact) Random optimization Local search Greedy algorithm and hill-climbing Random-restart hill climbing Best-first search Simulated annealing , Threshold Accepting Quantum annealing Ant colony optimization Tabu search Genetic algorithms GRASP Swarm intelligence Stochastic Diffusion Search Generalized extremal optimization Reactive search STAGE Számtalan variációja és kombinációja a fentieknek Stb.
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
19
Mekkora az állapottér? 10 binaris valtozó: 210 állapot = 1 024 1 048 576 20 binaris valtozó: 220 állapot = 30 30 binaris valtozó: 2 állapot = 1 073 741 824
Állapottér robbanás: • Hozzáveszünk egy új változót egy polinom idejű, egy exponenciális és egy faktoriális algoritmushoz, megtöbbszöröződik a futási idő: • 105 = 100 000 < 115 = 161 051 (polinom) • 105 = 100 000 << 106 = 1 000 000 (exponencialis) • 10! = 3 628 800 << 11! = 39 916 800 (faktoriális) << 20! ∼ 2.4×1018 = 2.4 quadrillion : 1s<<11s<<10 000 év
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
original problem: (IP)
cinkler()tmit.bme.hu
• • • •
22
B&B - example
20
állapot (i) (rész vagy teljes) szomszédosság (N(i)) célfüggvény (F(i): S→R) korlátok lokális és globális optimum
cinkler()tmit.bme.hu
m N(i)
l i k j
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
21
Hátizsák Probléma • 14 „kapacitású” hátizsák • 8, 11, 6 és 4 értékű „tárgyak” • Melyek térfogata 5, 7, 4 és 3 • Egészértékű és bináris változat
• dekomponalva tízszer 1 illetve kétszer 5 valtozóra: 10·15 = 10 << 55+55 = 6250 << 105 = 100 000 10·101 = 100 << 2·105 = 200 000 << 1010 = 10 000 000 000
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• •
maximise cx subject to Ax ≤ b x≥0
23
•
cinkler()tmit.bme.hu
• •
maximise subject to
8x1 + 11x2 + 6x3+ 4x4 5x1 + 7x2 + 4x3 + 3x4 ≤ 14 xj ∈ {0,1} , j=1,2,3,4 (LR) solution: x1 = 1, x2 = 1, x3 = 0.5, x4 = 0, z = 22
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
24
we know that the optimal integer solution is not greater than 21.85 (21 in fact) we will take a subproblem and branch on one of its variables - we choose an active subproblem (here: not chosen before) - we choose a subproblem with highest solution value
B&B example cntd.
Fractional z = 22
– no integer solution will have value greater than 22
add the constraint to (LR)
x3 = 0 Fractional z = 21.65
x1 = 1, x2 = 1, x3 = 0, x4 = 0.667 Forrás: M. Pióro vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• • • • •
B&B - knapsack problem
maximise cx subject to Ax ≤ b x ≥ 0 and integer
The optimal objective value for (LR) is greater than or equal to the optimal objective for (IP). If (LR) is infeasible then so is (IP). If (LR) is optimised by integer variables, then that solution is feasible and optimal for (IP). If the cost coefficients c are integer, then the optimal objective for (IP) is less than or equal to the “round down” of the optimal objective for (LR).
cinkler()tmit.bme.hu
– az összes i állpot halmaza
Példa: • polinom ideju algoritmus, ötödik hatvány, 10 változóra 105 (x5) komplexitás • exponenciális idejű algoritmus, 10 változóra 1010 (10x) komplexitás
linear relaxation: (LR)
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• állapottér (S)
Legegyszerűbb approximáció: Dekompozíció
„Állapottér robbanás” • • • •
2. Diszkrét Optimalizálás
x3 = 0 Fractional z = 21.65
Fractional z = 22
x3 = 1 Fractional z = 21.85
x3 = 1, x2 = 0 Integer z = 18 INTEGER
no further branching, not active
x1 = 1, x2 = 0.714, x3 = 1, x4 = 0
x1 = 1, x2 = 0, x3 = 1, x4 = 1
Forrás: M. Pióro 25
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
x3 = 1 Fractional z = 21.85
26
cinkler()tmit.bme.hu
x3 = 1, x2 = 1 Fractional z = 21.8
x1 = 0.6, x2 = 1, x3 = 1, x4 = 0
Forrás: M. Piórovittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
27
B&B example cntd.
Fractional z = 22
Teljes és részmegoldások
2. alkalom 2006.X.16. 8:00-10:05 IB.142
x3 = 0 Fractional z = 21.65
x3 = 1 Fractional z = 21.85
there is no better solution than 21: fathom
x3 = 1, x2 = 0 Integer z = 18 INTEGER
x1 = 0, x2 = 1, x3 = 1, x4 = 1 cinkler()tmit.bme.hu
Alkalmazott optimalizálás és játékelmélet (Applied Optimisation and Game Theory)
x3 = 1, x2 = 1 Fractional z = 21.8
x3 = 1, x2 = 1, x1 = 0 Integer z = 21 INTEGER
optimal
x1 = 1, x2 = 1, x3 = 1, x4 = ? 28
• Pl. hátizsák-problémánál minden részmegoldás lehet teljes is • Iteratív kiegészítgetéssel haladunk
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
29
3.1 Exhaustive Search (Kimerítő keresés)
Állapottér Szomszédosság Célfüggvény Korlátok Leállási kritériumok Konvergál? Eddigi legjobbhoz, vagy előbbi állapothoz viszonyít? Milyen elfogadási kritériumot használ?
• • • • • •
cinkler()tmit.bme.hu
3.2. Elágazás-korlátozás
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
32
Elágazás-korlátozás
– Ágazás (Branching): Az értelmezési tartomány rekurzív felbontása al-tartományokra melyek lefedik az egész tartományt • Ez fát alkot: search tree vagy branch-and-bound-tree • A fa csomópontjai az egyes tartományoknak felelnke meg
– Korlátozás (Bounding): Egy altartományon belül az optimális megoldásra felső és alsó korlátot talál
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• Nagyon jól kell megválasztani a 2 függvényt
34
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
33
– Knapsack problem – Integer programming – Nonlinear programming (see this for nonconvex programming) – Traveling salesman problem (TSP) – Quadratic assignment problem (QAP) – Maximum satisfiability problem (MAX-SAT)
– Legrosszabb esetben kimerítő kereséssé válik cinkler()tmit.bme.hu
cinkler()tmit.bme.hu
• Több NP-nehéz problémára használják • Számos heurisztikus elemet tartalmaz
– Ha A tartomány alsó küszöbe nagyobb mint bármely egyéb B tartomány felső küszöbe, akkor A tartomány biztos kihagyható (pruning) „levágjuk” a fa adott ágát és az esedékes tartományban finomítjuk a keresést – Pl. egy m változóval tároljuk mindig az altartományok legkisebb felső korlátját és minden altartományt melynek az alsó korlátja nagyobb – elvetünk – Ha átfedés van ezen intervallumok közt, nem vetjük el, hanem kiértékeljük – Ha minden állapotot kiértékeltünk vagy elvetettünk vége van az eljárásnak – Leállítható előbb is ha pl: error criterium = (max-min)/(min + max) elér valamilyen érték alá
• 2 eszköz kell az Elágazás-korlátozás módszerhez
30
Elágazás-korlátozás alkalmazása
• Ha pl. minimalizálunk
Branch-and-Bound Egzact módszer Állapottér részeinek kizárása Először A. H. Land és A. G. Doig javasolták a módszert 1960-ban LP-re.
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• xj ∈ {0,1} , j=1,2,3,4 • x ∈ {{0,0,0,0}, {0,0,0,1}, {0,0,1,0}, {0,0,1,1}, {0,1,0,0}, {0,1,0,1}, {0,1,1,0}, {0,1,1,1}, {1,0,0,0}, {1,0,0,1}, {1,0,1,0}, {1,0,1,1}, {1,1,0,0}, {1,1,0,1},{1,1,1,0}, {1,1,1,1}} • 16 lehetőség, de bármely két elem belefér, de mind a négy már nem – ez vagy más szabályok alapján korlátozhatunk • NP-complete (NP-teljes) • Egy a Karp's 21 NP-complete problems.
– Példa: http://en.wikipedia.org/wiki/Computer_chess – Ügyesen kizárjuk a tér részeit, különben valós időben nem menne... 31
cinkler()tmit.bme.hu
0-1 Hátizsákunk kimerítő keresése
Brute-force („Nyers erő” módszere) Az állapottér szisztematikus bejárása Egy állapotot sem hagyunk ki A legjobbat mindig eltároljuk Egzakt (exact) (globálisan optimális) megoldás Trükkök: szisztematikusan kizárható egy-egy része a térnek heurisztikus szabályok alapján
http://en.wikipedia.org/wiki/Branch_and_bound • • • •
– Részmegoldások sorozata (ez is egy állapottér...)
http://opti.tmit.bme.hu/optgame/ http://www.vdk.bme.hu/targykov/doktorandusz/vittd097.htm
INFEASIBLE
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• Pl. feszítőfa-problémánál ha minden csúcsot bekötöttük a fába
Dr. Cinkler Tibor cinkler()tmit.bme.hu
x3 = 1, x2 = 1, x1 = 1 Infeasible
Forrás: M. Piórovittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
– Mohó, ILP, nem-determinisztikus, stb. – Teljes megoldások állapottere
vittd097 ― 2006 ősz
3. Néhány „meta-heurisztikus” módszer
cinkler()tmit.bme.hu
• Probléma • Modell • Megoldó módszer
35
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
36
3.3. Random Sampling: „véletlen” módszerek
3.4. RR: Randomised Rambling Céltalan (Véletlen) Bolyongás
• véletlen „rálövünk sörétes puskával” • Minden állapot kiválasztásának valószínűsége azonos • „Elég sok” minta alapján „van remény”, hogy találunk „elég jó” megoldást • Ismétlés előfordul - kizárandó
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
http://en.wikipedia.org/wiki/Random_walk
• Részegesen előre lépkedve 45º-ban balra vagy jobbra lépünk • 8 ilyen „séta” első 100 lépése • Aszimptotikusan konvergál: • Ahol n a lépések száma
• Más néven: "Random walk" vagy "drunkard's walk" http://en.wikipedia.org/wiki/Random_walk • Azonos valószínűséggel fogad el minden szomszédos állapotot, hogy abból lépjen tovább) • Nagyon kiindulópont függő
37
Analógia: Brown-i mozgás
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
38
• Ürestől a teljes állapot felé • Mindegyik állapotnak 4 szomszédja van
• Elég kis lépésekkel lépkedve a céltalan bolyongás (véletlen séta) közelíti a Browni mozgást
1000 lépés 2D-ben
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
40
cinkler()tmit.bme.hu
{0,0,0,1}
{0,0,0,1}
{0,0,1,1}
{0,1,1,1}
cinkler()tmit.bme.hu
{0,1,0,1}
• Tetszőleges kiindulás • Mindkét irányba léphetünk (fel le) • Így már nehezebb lokális optimumban elakadni
{0,0,0,0}
{0,0,1,0}
{0,1,0,0}
{0,1,1,0}
{1,0,0,1}
{1,0,1,1}
{1,0,0,0}
{1,0,1,0}
{1,1,0,1}
{1,1,1,1}
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
{0,0,1,1}
{0,0,0,1}
41
{1,1,0,0}
{0,0,1,1}
{1,1,1,0}
{0,1,1,1}
43
cinkler()tmit.bme.hu
{0,1,0,1}
{0,1,1,0}
{1,0,0,1}
{1,0,1,1}
{1,0,1,0}
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
{0,1,1,0}
{1,0,0,1}
{1,0,1,1}
{1,0,0,0}
{1,0,1,0}
{1,1,0,1}
{1,1,0,0}
{1,1,1,0}
{1,1,1,1}
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
42
http://en.wikipedia.org/wiki/Random_walk Típusai – valamennyi a múltat veszi valahogy figylembe: – The self-avoiding walk. Neal Madras and Gordon Slade (1996), The SelfAvoiding Walk, Birkhäuser Boston. ISBN 0-8176-3891-1 – The loop-erased random walk. See the two books of Lawler. – The reinforced random walk. – The exploration process.
{1,0,0,0}
{1,1,0,1}
{1,1,1,1}
cinkler()tmit.bme.hu
•
{0,1,0,0}
{0,1,0,1}
{0,1,0,0}
Random Walk típusai és alkalmazásai
{0,0,0,0}
{0,0,1,0}
39
{0,0,0,0}
{0,0,1,0}
{0,1,1,1}
Példa: 0-1 Hátizsákunk – szomszédossági gráf –
Példa: 0-1 Hátizsákunk – szomszédossági gráf – Teljestől az üres állapot felé – ezesetben ez a gyorsabb! – előre becsülhető
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Példa: 0-1 Hátizsákunk – szomszédossági gráf –
– Lépésméret: ε – Séta hossza: L/ε2 – Brown-i úthossz: L – Központi határeloszlás tétel szerint http://en.wikipedia.org/wiki/Central_limit_theor em cinkler()tmit.bme.hu
cinkler()tmit.bme.hu
Analógia: Brown-i mozgás (folytatás)
http://en.wikipedia.org/wiki/Brownian_motion Robert Brown botanikus nyomán 32, 256 és 2048 lépésenként
Példa: 1D Random Walk
•
Alkalmazásai: – In brain research, random walks and reinforced random walks are used to model cascades of neuron firing in the brain. – Random walk can be used to sample from a state space which is unknown or very large, for example to pick a random page off the internet or, for research of working conditions, a random illegal worker in a given country. – When this last approach is used in computer science it is known as Markov Chain Monte Carlo or MCMC for short. Often, sampling from some complicated state space also allows one to get a probabilistic estimate of the space's size. The estimate of the permanent of a large matrix of zeros and ones was the first major problem tackled using this approach. – In wireless networking, random walk is used to model node movement. – Random walk is used to model gambling. – During World War II a random walk was used to model the distance that an escaped prisoner of war would travel in a given time. – Stb.
{1,1,0,0}
{1,1,1,0}
44
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
45
3.5. Local Search Helyi (szomszédossági) keresés
3.6. Hegymászás (Hill-climbing)
http://en.wikipedia.org/wiki/Local_search_(optimization)
http://en.wikipedia.org/wiki/Hill-climbing
• simple hill climbing (first better neighbour) • steepest ascent hill climbing (the best neighbour) • Folytonos téren (continuous space)
• Ez egy csoportja a módszereknek • Iteratív lépkedés szomszédos állapotba – Ezért helyi (local)
• gradient ascent (or gradient descent if the function is minimized)
• Csak lokális optimumot talál! Ezellen: – Random-restart hill climbing (Shotgun hill climbing ) – stochastic hill climbing • A „lépés méretét” állítják • „If the step size scales as 1/T (where T is the number of gradient steps taken so far), then stochastic gradient descent is guaranteed to converge”
• Hegymászás a legjellemzőbb példa – ha maximumot keresünk vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• Mindig a legmeredekebb irányban halad (fel vagy le) • Szomszédossági keresésre is általánosítható
– Gradiens módszer megfelelője
• Nem véletlenül, hanem irányítottam mozog a szomszédossági (N) gráfban • Csak lokális opőtimumot keres
cinkler()tmit.bme.hu
Gradiens módszer
– random walks – Stb.
46
cinkler()tmit.bme.hu
3.7. Véletlen újraindítású hegymászás
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
47
3.8. Mohó Algoritmus (Greedy Algorithm)
http://en.wikipedia.org/wiki/Random-restart_hill_climbing
• • • •
• 41 US centet kell visszaadni, úgy, hogy a legkevesebb darab érmét adjuk vissza (25, 10, 5, 1) • Ez hasonlít a súlyozatlan egészértékű hátizsák problémára • A számrendszerek közti átalakítás is hasonlóan működik (pl 1310→ 11012)
Jellemzően részmegoldásokon át → teljes megoldásig Pl: Feszítő fa: Példa Kruskal, Prim (m sorbarendezése + O(m+log n) m él és n csomópont) Spanning Tree (minimum összköltségű feszítőfa): – mohó algoritmusok (említeni matroidokat) • Kruskal’s Algorithm (1956-ban, sokan mások is előtte és vele egyidőben ) (AMO 520. oldal), • improved Kruskal algorithm • Prim’s algorithm • Sollin’s algorithm
49
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
50
0-1 hátizskproblémánk mohón ― súlyozatlan eset ― példa+
0-1 hátizskproblémánk mohón ― súlyozatlan eset ―
• Martello and Toth (1990) • ha optimálisan k elem férne be legalább k/2-t tesz be a mohó algoritmus • 14 „kapacitású” hátizsák
{0,0,0,0}
{0,0,0,1}
{0,0,1,0}
• Súlyozatlan mohó módszer:
{0,0,1,1}
– 1. lépés: 7 térfogatú: {0,1,0,0} – 2. lépés: 5 térfogatú: {1,1,0,0} – 3. lépés: 4 nem fér be, 3 sem fér bele
51
• 14 „kapacitású” hátizsák
{0,1,0,0}
{0,1,1,0}
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
– 8, 11, 6 és 4 értékű „tárgyak” – 5, 7, 4 és 3 térfogatú tárgyak – 1.6, 1.57, 1.5, 1.33 haszon egységnyi térfogatra
{1,0,0,0}
• Súlyozott mohó módszer:
{1,0,0,1}
{1,0,1,0}
– 1. lépés: 5 térfogatú: {1,0,0,0} – 2. lépés: 7 térfogatú: {1,1,0,0} – 3. lépés: 4 nem fér be, 3 sem fér bele
{1,1,0,0}
• Eredmény: {0,1,1,1}
• Eredmény: – 14-ből csak 12 egységnyi kapacitást használtunk ki – {0,1,1,1} optimumhoz képest 19 a haszon 21 helyett vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
{0,1,0,1}
cinkler()tmit.bme.hu
0-1 hátizskproblémánk mohón ― súlyozott eset ― példa++
– 8, 11, 6 és 4 értékű „tárgyak” – 5, 7, 4 és 3 térfogatú tárgyak
cinkler()tmit.bme.hu
48
Mohó algoritmus példák
• Kruskal és Sollin mohón teszi be az éleket. • Prim mohón fát épít. (pl. Fibonacci Heap-pel.) vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
http://en.wikipedia.org/wiki/Greedy_algorithm
• Hegymászás → lokális optimum • Iteratív ismétlés véletlen kiinduló-ponttal • Mindig a legjobb célfüggvényű állapotot tároljuk • Meglepően hatékony • Gyors és nem kell az állapottér ismerete
cinkler()tmit.bme.hu
cinkler()tmit.bme.hu
52
cinkler()tmit.bme.hu
{1,0,1,1}
{1,1,0,1}
{1,1,1,1}
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
– 14-ből csak 12 egységnyi kapacitást használtunk ki – {0,1,1,1} optimumhoz képest 19 a haszon 21 helyett – Ugyanaz mint súlyozatlan esetre!
{1,1,1,0}
53
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
54
0-1 hátizskproblémánk mohón ― súlyozott eset ―
Utazóügynök probléma ― példa+++
{0,0,0,0}
• Travelling salesman problem (TSP) http://en.wikipedia.org/wiki/Traveling_salesman_problem • "Given the distances between any two points, what is the shortest route a salesman can make from point A, visiting all points, and returning to point A? This is the Travelling Salesman problem, an NP-Hard problem in mathematics."
{0,0,0,1}
{0,0,1,1}
{0,0,1,0}
{0,1,0,1}
{0,1,1,1}
{0,1,0,0}
{0,1,1,0}
{1,0,0,1}
{1,0,1,1}
{1,0,0,0}
{1,0,1,0}
{1,1,0,1}
{1,1,1,0}
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
55
cinkler()tmit.bme.hu
2006.X.18. 8:00-10:05 IB.141
56
vittd097 ― 2006 ősz Dr. Cinkler Tibor cinkler()tmit.bme.hu http://opti.tmit.bme.hu/optgame/ http://www.vdk.bme.hu/targykov/doktorandusz/vittd097.htm 58
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
•
begin choose an initial solution i∈ S; select an initial temperature T > 0; while stopping criterion not true count := 0; while count < L choose randomly a neighbour j∈Ν(i); ∆F:= F(j) - F(i); if ∆F ≤ 0 then i := j else if random(0,1) < exp (-∆F / T) then i := j; count := count + 1 end while; Metropolis test reduce temperature (T:= T×α)
• • •
• uphill moves are permitted but only with a certain (decreasing) probability (“temperature” dependent) according to the so called Metropolis test • neighbours are selected at random 59
•
• for T→0, Prob { X = i } remains greater than 0 only for optimal configurations i∈S
http://en.wikipedia.org/wiki/Quantum_annealing
A megengedhető energia különbséget nézzük: –
60
– Prob { X = i } = exp(-F(i)/T) / Z(T) – Z(T) = Σj∈S exp(-F(j)/T)
Nem a hőt, hanem a lépésméretet csökkentjük: –
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• limit theorem: global optimum will be found • for fixed T, after sufficiently number of steps:
http://en.wikipedia.org/wiki/Stochastic_tunneling
this is not a very practical result: too many moves (number of states squared) would have to be made to achieve the limit sufficiently closely
end while end vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Forrás: M. Pióro cinkler()tmit.bme.hu
Simulated Annealing - limit theorem
Lehet az állapot-váltás elfogadására különböző szabályokat használni Különböző hűtési stratégiák Újrahűtögetjük Adaptívvá tesszük: http://en.wikipedia.org/wiki/Adaptive_simulated_annealing
•
57
Ν(i) ⊆ S - neighbourhood of a feasible point (configuration) i∈ S
SA Variációk
Simulated Annealing - algorithm
Forrás: M. Pióro cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Combinatorial Optimisation Problem given a finite set S (solution space) and evaluation function F : S → R find i ∈ S minimizing F(i)
http://en.wikipedia.org/wiki/Simulated_annealing Kezdőállapot Szomszédok (érvényes állapotok) Célfüggvény: energiafüggvény Kezdőhőmérséklet Hűtési fgv (TSP-nél: hurokhossz is kell) bináris és integer stringre, majd TSP problémára, ahol az állapotteret ügyesen tudjuk tartani: csak érvényesből érvényes állapotba!! Permutációkat keresünk. PioroPPT 2. resz, 34-37 slide • Bizonyitas hogy optimalis • Knapsack es TSP problemara pelda
(Applied Optimisation and Game Theory)
cinkler()tmit.bme.hu
Simulated Annealing
• • • • • • • •
Alkalmazott optimalizálás és játékelmélet
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
3.9. Szimulált Lehűtés (Simulated Annealing)
3. alkalom
cinkler()tmit.bme.hu
http://en.wikipedia.org/wiki/Nearest_neighbor_algorithm – The nearest neighbor algorithm, which is normally fairly close to the optimal route, and does not take too long to execute. Rosenkrantz et al. [1977] showed that the nearest neighbour algorithm has approximation factor Θ(log | V | ). Unfortunately, it is provably reliable only for special cases of the TSP, namely those where the triangle inequality is satisfied. In the general case, there exists an example for which the nearest neighbor algorithm gives the worst possible route. In practice this heuristic provides solutions which are in average 10 to 15 percent above the optimal. An example of the nearest neighbor algorithm finding the worst case path would be to travel along a line, starting at 0, to alternating negative and positive powers of 2 minus 1, therefore, from 0,1,-3,7,-15,31,-63... (2n − 1)( − 1)n.
{1,1,0,0}
{1,1,1,1}
cinkler()tmit.bme.hu
Mohó algoritmus TSP-re: Nearest neighbour algorithm
61
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
62
Forrás: M. Pióro cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
63
SA 0-1 hátizsákunkra
SA a 0-1 hátizsák problémára • • •
• Szomszéd: Melyik tárgyat tesszük be vagy vesszük ki • Energia-változás: összköltség az előbbi állapothoz képest • Lehet binárisan is reprezentálni: 1
0
1
0
.....
0
1
1
Véletlen pontból indul, mindig 1 szomszédot vizsgál Energia? Érvényes állapotok?
• Hasonlóan lehet ILP-t is megoldani SA-val
{0,0,0,0}→0
– Célfüggvény, korlátok kezelése {0,0,0,1} →4
{0,0,1,0} →6
{0,0,1,1}10 {0,1,0,1}15
{0,1,0,0} →11
{0,1,1,0}17
{1,1,0,0}19
{1,0,1,0}14
{1,0,0,1} 12
• Sőt folytonos problémákra is lehet SA-t használni
{1,0,0,0} →8
1
{0,1,1,1} →21
cinkler()tmit.bme.hu
ILP megoldás SA-val
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
64
{1,0,1,1} →18
{1,1,0,1} →23
{1,1,1,0} →25
{1,1,1,1} →29
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Simulated Annealing applied to the Travelling Salesman Problem (TSP)
65
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
66
3.10. Küszöbértékes elfogadás (Threshold Accepting)
TSP - neighbourhood relation
Combinatorial Optimisation Problem
• (Greate Deluge – Nagy Özönvíz)
given a finite set S (solution space) and evaluation function F : S → R find p ∈ S minimizing F(p), Ν(p) ⊆ S - neighbourhood of a feasible point (configuration) p ∈ S
j p
TSP S = { p : set of all cyclic permutations of length n with cycle n } p(i) - city visited just after city no. i F(p) = ∑ i=1,2,…,n cip(i) ( cip(i) - distance between city i and p(i) ) Ν(p) - neighbourhood of p (next slide)
q j’
i
– Ha az addig talált legjobb értékhez viszonyítunk
j j’
• Javított "local search" • Determinisztikus szabály az új állapot elfogadására SA-val mely véletlenszerűsített szemben!
i i’
i’ Hamiltonian circuit to Hamiltonian circuit any p reachable from any q
Forrás: M. Pióro cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
67
Forrás: M. Pióro cinkler()tmit.bme.hu
3.11. Tabu Search • • • •
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
3.12. Genetic Algorithm
– látogatott állapotok („steepest ascent, mildest descent”) – módosítás típus
•
• • • •
3. kereszteződés (1 pont, 2pont, uniform stb), 1-2 utód (offspring); recombination •
• crossover (genetic algorithm) n-pontos v cut-and-splice
4. mutáció (1 pont, 2 pont(szakasz))
• Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer, Norwell, MA. • Glover, F. "Tabu Search — Part I", ORSA Journal on Computing 1989 1: 3, 190206. • Glover, F. "Tabu Search — Part II", ORSA Journal on Computing 1990 2: 1, 4-32.
•
– mutation
5. új nemzedék (populáció - nemzedék) részben vagy teljesen új egyedek, rögzített populációméret) 70
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Rengeteg változat – Változó populációméret – A legjobb az előző generációból szerepel az újban – Stb.
– roulette wheel selection – tournament selection
– Irodalom:
69
GA variációk
1. fitness kiértékelés a populáció minden egyedére 2. szülőválasztás (párválasztás);selection
• Mekkora a tabu lista = 7 ☺, • Mi a megállási feltétel) (többszintű tabu kritérium, memóriával (tapasztalatot gyűjt)) • Példa SiAn Metropolis TSP-re: élek a tabulistában (n lépésen át nem nyúlúnk egy betett élhez)
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
68
• Genetic (Evolutionary) Algorithms • kromozóma, genotipus (péléda: facility location problems) • Szóba-jövő megoldások: individuals, creatures, or phenotypes • Generációk • fázisok:
http://en.wikipedia.org/wiki/Tabu_search Memóriával (emlékezettel) rendelkezik A szomszédosságot dinamikusan állítja! („N-T”) Mi a tabu?
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
71
Elosztottan is implementálható Folytonos probléma global optimumanak keresese diszkret heurisztikakkal, pl. GA (Zbigniew könyv 18-20 oldal) Diszkrét visszavezetése binárisra - abszolut (egy érték egy változó és kizárásos korlátok) Integer visszavezetése binárisra - inkrementálisan (kettes számrendszerben felírva, mázli ha pont kettő hatványa) The Distributed Genetic Programming Framework (DGPF) http://dgpf.sourceforge.net/ GENOCOP http://www.cs.adelaide.edu.au/~zbyszek/evolsystems.html
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
72
Léállási feltételek •
• Common terminating conditions are – – – –
A solution is found that satisfies minimum criteria Fixed number of generations reached Allocated budget (computation time/money) reached The highest ranking solution's fitness is reaching or has reached a plateau such that successive iterations no longer produce better results – Manual inspection – Combinations of the above
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
3.13. Tarts a győztessel! GWW: Go with the Winner
GA történelem
•
73
Computer simulations of evolution started with Nils Aall Barricelli in 1954. Barricelli was simulating the evolution of automata that played a simple card game. The Australian quantitative geneticist Alex Fraser published a series of papers on simulation of artificial selection of organisms with multiple loci controlling a measurable trait. From these beginnings, computer simulation of evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970) and Crosby (1973). Many early papers are reprinted by Fogel (1998). Although Barricelli had also used evolutionary simulation as a general optimization method, genetic algorithms became a widely recognized optimization method as a result of the work of John Holland in the early 1970s, and particularly his 1975 book. His work originated with studies of cellular automata, conducted by Holland and his colleagues at the University of Michigan. Research in GAs remained largely theoretical until the mid-1980s, when The First International Conference on Genetic Algorithms was held at The University of Illinois. As academic interest grew, the dramatic increase in desktop computational power allowed for practical application of the new technique. In 1989, The New York Times writer John Markoff wrote about Evolver, the first commercially available desktop genetic algorithm. Custom computer applications began to emerge in a wide variety of fields, and these algorithms are now used by a majority of Fortune 500 companies to solve difficult scheduling, data fitting, trend spotting and budgeting problems, and virtually any other type of combinatorial optimization problem.
cinkler()tmit.bme.hu
3.14. GRASP
• Best First Search http://en.wikipedia.org/wiki/Bestfirst_search GWW később!
• n golyó jobb mint nx1golyó! • Kölcsönhatások • Példa: Gráfbejárás (Bárász Mihály)
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
74
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
3.15. STAGE
75
4. alkalom 2006.X.25. 8:00-10:05 IB.141
• • • • • • • •
http://en.wikipedia.org/wiki/Greedy_randomized_adaptive_search_pr ocedure GRASP Greedy Randomised Adaptive Search Procedure (Pioro könyv 178, (Feo-Resende 1995-ben javasoltak)) kombinációk (Gennetic Annealing, GRASP: Initial solution in greedy way + Improvement in randomised way iteratively) Iterative, two-phase approach: Construction (Greedy Randomized Solution, via a very simple and fast method) Improvement (via Local Search or other more sophisticated method) (Más kiindulópont keresése) Például (1.SiAl + 2. SiAn) (GRASP consists of two phases: construction and local search. The construction phase builds good feasible solutions (a set of satisfied clauses), whose neighbourhood is investigated until a local optimum is found during the local phase. The best total weight of satisfied clauses is kept as the result.)
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
76
3.16. Dynamic Programming •
http://en.wikipedia.org/wiki/Dynamic_programming
• • • • •
Példák: Legrövidebb út választás Hatizsak problemara pl. Rugalmas forgalmas (ElasticTraffic) algoritmus is egy DynProg „Principle of optimality” egy adott állapotban az optimalitás feltétele, hogy jó következő döntést kell hozni az adott állapotban. Dynamikus programozás bináris hátizsák problémára: komplexitás O(nb) ha a hasznok egységnyiek, azonban O(n Sum_n pi) ahol pi az egyes i elemek által hozott haszon) ami legfeljebb O(n2pmax) Pseudopolynomial time algorithm (but not polynomial!) a lépések száma ugyan polinom idejű, de függ a haszontól! Elvileg a pi költség reprezentálására t=log pi bitre van szükség. Azaz 2t szám reprezentálható t bittel. (Ausiello et al. Complexity and Approximation 69-74) Tehát a komplexitás legfeljebb O(n22t) Ausiello et al. Complexity and Approximation 114-116 pseudo-polynomiality Definition 3.15. Példa, mikor approximációt használunk a bemeneti értékek átskálázására, és megmutatjuk, mikor lesz a polinom időben kapott eredmény valóban optimális is. (Ausiello et al.)
• •
• •
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• STAGE function approximator, 2 local searches (példa: sinx/x) (Lőrincz András, Ziegler Gábor) • Ahol lehet rekurzivan kozeliteni, pl hatizsak! • Ahol van rendszer az állapottérben • Néhol remekül működik! • Hatékonysága sokmindentől függ! • Két példa:
Alkalmazott optimalizálás és játékelmélet (Applied Optimisation and Game Theory) vittd097 ― 2006 ősz
– Latest Results with STAGE : • http://www.cs.cmu.edu/~reinf/papers/boyan.stage-talk.ps • local copy: BoyanSTAGEtalk.pdf
Dr. Cinkler Tibor cinkler()tmit.bme.hu
– Learning to Speed Up Search: • http://www.cs.cornell.edu/~weiwei/workshop-aaai02-new.ppt • local copy: STAGE_workshop-aaai02-new.ppt
cinkler()tmit.bme.hu
http://opti.tmit.bme.hu/optgame/ http://www.vdk.bme.hu/targykov/doktorandusz/vittd097.htm
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
77
cinkler()tmit.bme.hu
79
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
78
Dynamic Programming
Dynamic Programming ötlete • L.A.Wolsey: Integer Programming, 1998 WiIley, 67-80 oldal szépen leírja – én itt ezt használom • Ha az s-t legrövidebb út áthalad j-n akkor s-j és j-t a legrövidebb utak s és j valamint j és t között • d(sj)=mini∈N(j){d(si)+d(ij)} • Negatív összköltségű körtől s j mentes irányított gráfra • k-ra iterálva (1,2,…|V|-1) • Dk(sj)=min{Dk-1(sj), mini∈N(j){Dk-1(si)+d(ij)} } • Lépésszám: O(|V||E|)
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• Knapsack problem (appears in many ND applications) – maximize – subject to
• • • • •
t
F = r1x1 + r2x2 + ... + rnxn w1x1 + w2x2 + ... + wnxn ≤ W x1,x2,...,xn binary
Linear relaxation is straightforward to solve NP-complete becuase problem size is O(n log W) A hátizsák mérete w nő 1-től W-ig! Az iterációk száma k nő 1-től n-ig F*(k,w) = max { F*(k - 1,w), F*(k-1,w - wk) + rk } – F*(0,w) = 0 for all w, F*(k,w) = -∞ for all k and w < 0 – start from F*(1,1) and continue until F*(n,W) – time: nW Forrás: M. Pióro
80
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
81
Dynamic Programming - example w = (1, 2, 5, 6, 7) tárgyak mérete
W=11 méretű hátizsák
r = (1, 6, 18, 22, 28) tárgyak értéke
n=5 darab tárgy
3.17. Simulált foglalás • Simulated Allocation és típusai • Michał Pióro • Példák:
Optimal objectives in knapsack subproblems
k \ w
0
1
2
3
4
5
6
7
8
9
10
11
1 2 3 4 5
0 0 0 0 0
1 1 1 1 1
1 6 6 6 6
1 7 7 7 7
1 7 7 7 7
1 7 18 18 18
1 7 19 22 22
1 7 24 24 28
1 7 25 28 29
1 7 25 29 34
1 7 25 29 35
1 7 25 40 40
w1=1, r1=1 w1=2, r1=6 w1=5, r1=18 w1=6, r1=22 w1=7, r1=28
SAl - pseudocode
begin step:= 0; min_cost:= +∞; x:= 0; repeat step:= step+1; if random
– Hátizsák – Folyamproblémák • Minden él egy hátizsák • Egyszerre több hátizsákot pakolunk
Forrás: M. Pióro
Forrás: M. Pióro cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
82
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
SAl a 0-1 hátizsák problémára • • •
üresből indul, mindig 1 szomszédot vizsgál és el is fogadja
{0,0,0,1} →4
• • • •
– Pl. Nem egy utat hanem utak csoportját töröljük – Pl. agy élet használó össz utat
{1,0,0,0} →8
• Újraindítgatás {0,0,1,1}10 {0,1,0,1}15
{0,1,1,1} →21
{0,1,1,0}17
{1,0,1,1} →18
{1,0,0,1} 12
{1,0,1,0}14
{1,1,0,1} →23
{1,1,0,0}19
84
Halak, bacik, rovarok, madarak http://en.wikipedia.org/wiki/Swarm_intelligence Beni & Wang in 1989 Artificial Intelligence – ACO: Ant colony optimization • Amerre jár, feromont tesz, és amerre feromon van arra jár
– PSO: Particle swarm optimization
Példa:
• Egy-egy pont a térben, és affelé mozognak szórtan, amelyik a legjobb
• Networks 2002: Cinkler, Pióro: Impact of Shared Protection Strategies on Network Design Networks2002_TopDes_td11.ppt
{1,1,1,0} →25
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
3.18. Raj (Swarm Inteligence: SI)
• Csoportoakat törlünk
{0,1,0,0} →11
cinkler()tmit.bme.hu
SAl változatai
{0,0,0,0}→0
{0,0,1,0} →6
83
– SDS: Stochastic Diffusion Search • Szétbontjuk a célfüggvényt, és egy-egy elosztott ügynök egyegy részt képvisel
{1,1,1,1} →29 cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
85
cinkler()tmit.bme.hu
3.19. Hangyák (Ant Colony Optimisation) •
http://en.wikipedia.org/wiki/Ant_colony_optimization
• • •
Marco Dorigo [Dor92,DoSt04] Elsősorban útkeresés gráfokban Hangyás módszerek (elosztott, feromon, stb.)
•
86
• • • • • • • • • •
Leállási feltételek: lépésszám, idő, felhasznalói megszkítás, eltelt idő vagy lépés az utolsó javítástól Alkalmazása: – Dinamikus hálózaton útvonalválasztási problémákra jó
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
87
3.21. NFLTheorem
3.20. További heurisztikák
– ants (initially) wander randomly – upon finding food return to their colony while laying down pheromone trails – If other ants find such a path, they are likely not to keep travelling at random, but to instead follow the trail, returning and reinforcing it if they eventually find food (Ant communication and behavior). Pozitív visszacsatolás. – A feromon párolog! (pheromone evaporates)
•
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
http://en.wikipedia.org/wiki/No-free-lunch_theorem • no-free-lunch theorem (NFLT) • by physicists David H. Wolpert and William G. Macready • "[...] all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions." (Wolpert and Macready, 1995) • "there ain't no such thing as a free lunch"
Random restarts (RSA: Re-Applied SiAn) Adaptivitás (ASA: Adaptive SiAn) Iteratív (dinamikus programozás) Korlátok kezelése: büntetőfüggvény (lineáris-nem jó, convex és növekvő meredekségű legyen) Dekompozíció Kizárás, állapottérszűkítés Fontos: elvileg járhassa be az egész állapotteret Megfelelő kezdőpont kiválasztása! Több célfüggvény → súlyozott átlag Korlát vagy célfüggvény - együttműködés
• Pl. közúti szállítmányozás dugó-kerüléssel
– TSP cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
88
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
89
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
90
4. ILP vagy LP? Hálózati folyamproblémák
NFLT • "a general-purpose universal optimization strategy is theoretically impossible, and the only way one strategy can outperform another is if it is specialized to the specific problem under consideration" (Ho and Pepyne, 2002) • http://www.no-free-lunch.org • An illustration of the no-free-lunch theorem, showing the performance of a highly specialized algorithm (red) and a general-purpose one (blue). Note that both algorithms perform — on average — equally well as they are applied to different problems.
• • • •
Dijkstra shortest path algorithm (1959) • • •
Legrövidebb út Legolcsóbb folyam Legolcsóbb osztatlan folyam Többtermékes folyam
– l(i) - temporary label of node i – l*(i) - permanent label of node i
•
– Mikor LP az ILP? – „Rezegtetés” ε élsúlyokkal – Relaxálás – kerekítés
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
91
Shortest Path
cinkler()tmit.bme.hu
the algorithm (finds shortest paths from s to all other nodes):
step0: step1:
set l*(s)=0 and l(i)=l(s,i) for all i∈V among all temporary labels l(i) pick l(k) = min { l(i): i∈V } change l(k) to l*(k); stop if there is no temporary label left update all temporary labels of the nodes i with (k,i)∈E for all i by l(i) = min { l(i), l*(k) + l(k,i) }
step2:
return to step1.
• Védelem cinkler()tmit.bme.hu
explained here for directed unigraphs l(i,j) - length of arc (i,j)∈E, l(i,j)= ∞ for (i,j)∉E, l(i,j) > 0 (!) node labelling algorithm
remark: to retrieve the paths, the permanent node labels should contain the number of the node, from which the labelled one has been reached vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
92
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Minimum Cost (Splittable) (Single-Commodity) Flow Problem
Minimum Cost Unsplittable (Single-Commodity) Flow Problem
(Legrövidebb) legolcsóbb folyam LP (immár kapacitással)
Legrövidebb út LP
93
Legolcsóbb osztatlan folyam
i j
min ∑ xl
k
N
N
j =1
ij
N
ij
j =1
l∈L
N
l∈L
∑x −∑x
min ∑ xl
∑x −∑x k =1
ki
0 if i is neither source nor sink =1 if i is the source − 1 if i is the sink
0 ≤ xl ≤ b
for all vertices (nodes) i
for all edges (arcs) (links) i
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
min ∑ xl
l∈L
94
k =1
ki
0 if i is neither source nor sink = b if i is the source − b if i is the sink
for all nodes i
N
N
∑x −∑x j =1
ij
k =1
ki
0 if i is neither source nor sink if i is the source =1 − 1 if i is the sink
xl ≤ Bl for all links l
xl b ≤ Bl for all l
0 ≤ xl ≤ b
xl ∈ {0,1}
cinkler()tmit.bme.hu
for all links l vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
95
cinkler()tmit.bme.hu
for all nodes i
for all links l vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
96
Minimum Cost Unsplittable Multi-Commodity Flow Problem
Legolcsóbb osztatlan többtermékes folyam min
∑ ∑x b
∀o∈O ∀l∈L
o l
∑x b ∀o
N
o ij
o l
o
cinkler()tmit.bme.hu
o ki
(Applied Optimisation and Game Theory) For all nodes i and commodities o
Dr. Cinkler Tibor cinkler()tmit.bme.hu
Boolean/Maximum Satisfiability Problem • •
http://opti.tmit.bme.hu/optgame/ http://www.vdk.bme.hu/targykov/doktorandusz/vittd097.htm
for all links l
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• Az ILP NP nehéz (Pióro sl. ) Max Sat-ra visszavezetés
vittd097 ― 2006 ősz
≤ Bl for all l
xlo ∈ {0,1}
• Az ILP NP nehéz míg az LP polinom idejű! • Ezért szeretjük az LP-t
Alkalmazott optimalizálás és játékelmélet
o
0 if i is neither source nor sink x −∑x = 1 if i is the source ∑ j =1 k =1 − 1 if i is the sink N
Az ILP NP nehéz
5. alkalom 2006.X.30. 8:00-10:05 IB.141
97
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
98
http://en.wikipedia.org/wiki/Boolean_satisfiability_problem http://en.wikipedia.org/wiki/Maximum_satisfiability_problem
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
99
NP-Completeness - decision problems
Appendix B
NP-Completeness - reduction
Decision problem P input data: parameters (p1,p2,...,pm) characterizing the finite solution (given) space X(p1,p2,...,pm), and constant C question: does there exist x ∈ X(p1,p2,...,pm) such that F(x) ≤ C
NP-complete (NP-C) • NP problem is NP-complete if any other NP problem can be reduced to it in polynomial time • All NP problems can be reduced in polynomial time to the Satisfiability Problem SAT (SAT is NP-complete) NP • Are P and NP-C disjoint ???
Problem P1 can be reduced (transformed) in polynomial time to problem P2 (P1→P2): 1. For each instance of P1 we can find an equivalent instance of P2 2. There exists a polynomial H(N) of degree k such that for each instance of P1 of size N we can transform it to an equivalent instance of P2 in the number of steps not greater than H(N) 3. And back.
N - size of the problem polynomially related to the length of the strings encoding the instances I
Garey, M.R., Johnson, D.S.: Computer and Intractability – A Guide to the Theory of NP-Completeness, W.H.Freeman & Co., 1979
100
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Forrás: M. Pióro 101
cinkler()tmit.bme.hu
SAT (Satisfiability Problem)
X - set of vectors x = (x1,x2,...,xn) x ∈ X iff Ax ≤ b and x are integers
t : U → {T,F} - truth assignment U = {u1,u2,…um} - Boolean variables; a clause - {u1,u2,u4 } represents conjunction of its elements (u1 + u2 + u4) a clause is satisfied by a truth assignment t if and only if one of its elements is true under assignment t C - finite collection of clauses
Decision problem: Instance: given n, A, b, B, and function f(x). Question: is there x ∈ X such that f(x) ≥ B?
a set U of variables and a collection C of clauses is there a truth assignment satisfying all clauses in C?
• LP relaxáció – Ha egészértékű kapacitás és egységnyi igények OK, ha egyetlen folyamot vezetünk el! – Ha unimoduláris u.a. az eredmény – Teljesen (totálisan) unimoduláris az A mátrix → minden négyzetes almátrix determinánsa 1, -1 vagy 0 – ha nem „rezegtessünk!” (+ε) vagy egyébb trükkök - ha egy pontpár közt csak 1 igény van, akkor működik...
Hint: • assign binary variables xi and xi with all Boolean variables ui and ui • an equality with each clause of the instance of SAT (x1 + x2 + x4 ≥ 1) • add inequalities: 0 ≤ xi ≤ 1, 0 ≤ xi ≤ 1, 1 ≤ xi + xi ≤ 1, i=1,2,...,n
So far there are several thousands of known NP-C problems, including Travelling Salesman, Clique, Steiner Problem, Graph Colourability, Knapsack (pseudo-polynomial) Forrás: M. Pióro cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• Integrality Property: Every minimum cost flow problem with integer demands and integer capacities has an integer optimal solution!
Forrás: M. Pióro 103
cinkler()tmit.bme.hu
Mi van, ha útfüggetlen védelmet is keresünk? (Diverse Routing)
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
104
cinkler()tmit.bme.hu
B 1
1 C
A
1
-1
A
3
B 1
• •
Shortest sets of disjoint paths
3 C
3
1
Z
1
•
Z
B
3
P1 ={ABCZ} , P2={ABZ,ACZ} P2 - P1 - logical difference with – + on arcs of P2 – - on arcs of P1 – cancellation of sign on common arcs
1
Z A
1
Z
3
3
-1
A
+ C
A
• •
the difference is a path between A and Z with the cost
in general the difference P2 - P1 is more complicated, but always includes an A to Z path with + and - labels transition from P1 to P2 – find a shortest path from A to Z with only - arcs common with P1 (interlacing with P1) – add it to P1 to get P2
K disjoint paths are found inductively from optimal solutions for 1,2,...,(K-1) disjoint paths, using a shortest path algorithm at each step
Forrás: M. Pióro 106
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Z
+
– (total length of + arcs) - (total length of - arcs) – equal to cost difference between P2 and P1 solutions
3
Shortest set of K node-disjoint paths between a pair of nodes is found in K iterations of a single shortest path algorithm
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
105
1 C
3 C
-1 C
A
1
1
Z
3 B
– Ferdén súlyozott is lehet...
B
3 1
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
B
Shortest sets of disjoint paths
• 2 Dijkstra • Suurballe • ILP
cinkler()tmit.bme.hu
102
LP vagy ILP?
The SAT problem is directly reducible to this IP problem. Given: Question:
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Integer Programming is NP-hard
NP-Completeness cntd.
SAT:
NP-C
P
Forrás: M. Pióro
Forrás: M. Pióro vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Polynomial problems (P) Non-deterministic Polynomial (NP) NP (intuitive): we can construct each x ∈ X(p1,p2,...,pm), and check in time polynomial in N, if F(x) ≤ C NP (intuitive): the solution tree has polynomially bounded paths
Polynomial problem: there exists a polynomial G(N) of degree m (G(N) = O(Nm)) such that for each instance I of the problem of size N we can solve it (YES or NO) in the number of steps not greater than G(N)
Instance I (p1,p2,...,pm) and C are given fixed numbers
cinkler()tmit.bme.hu
NP-Completeness cntd.
Forrás: M. Pióro 107
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
108
Minimum Cost Unsplittable Multi-Commodity Flow Problem with Dedicated Protection
Minimum Cost Unsplittable Multi-Commodity Flow Problem with Assymetrically Weighted Disjoint Paths
Minimum Cost Unsplittable Multi-Commodity Flow Problem with Shared Protection
Legolcsóbb osztatlan többtermékes folyam hozzárendelt védelemmel
Legolcsóbb osztatlan többtermékes folyam hozzárendelt ferdén súlyozott védelemmel
Legolcsóbb osztatlan többtermékes folyam megosztott védelemmel
min ∑ ∑ xlo + ylo b o l∈L o∈O
(
)
min ∑ ∑ xlo + α ⋅ ylo b o , l∈L o∈O
(
Objective
s.t. (constraints)
0 if i is neither source nor sink of o if i is source of o =1 k =1 j =1 − 1 if i is sink of o if i is neither source nor sink of o 0 N N yijo − ∑ y kio = 1 if i is source of o ∑ k =1 j =1 − 1 if i is sink of o N
N
∑x −∑x o ij
∑ (x
o∈O
o l
)
xlo + y lo ≤ 1 for all l and o xlo , y lo ∈ {0,1}
min ∑ ∑ xlo b o + Yl l∈L o∈O
Objective
0 if i is neither source nor sink of o if i is source of o =1 − 1 if i is sink of o if i is neither source nor sink of o 0 N N yijo − ∑ y kio = 1 if i is source of o ∑ k =1 j =1 − 1 if i is sink of o N
N
∑x −∑x j =1
for all nodes i and commodities o Flow Conservation Constraints
o ij
∑ (x
Capacity Constraint
o∈O
o l
k =1
)
+ ylo b o ≤ Bl for all links l
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
109
Amikor az ILP és LP relaxációja ugyanazt a feszítőfát adják...
for all nodes i and commodities o Flow Conservation Constraints
∑x b
Capacity Constraint
Path Diversity Constraint
o l
∑∑x
+ Yl ≤ Bl for all l
l '∈L o∈O l '≠ l
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
110
cinkler()tmit.bme.hu
o l'
for all nodes i and commodities o
ylo b o ≤ Yl for all l
NONLINEAR!
xlo , y lo ∈ {0,1}
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
111
Capacitated flow allocation problem
Egyszerűsítések -közelítések
• AMO 530 oldal: Spanning tree and LP: exponential and linear formulation • AMO 532. oldal: Amikor az ILP es LP relaxacioja ugyanazt a feszitofat adja (a polieder csucsai egeszertekuek!) (feszitofa problema) • AMO 533. oldal Theorem 13.10: The Polyhedron defined by the linear programming relaxation of the packing formulation of the minimum spanning tree problem has integer extreme points.
o
o ki
xlo + y lo ≤ 1 for all l and o
Integrality Constraint
cinkler()tmit.bme.hu
N
o ij
o∈O
xlo , y lo ∈ {0,1}
ITC 1999: Cinkler, Laborczi, Horváth: Protection through Thrifty Configuration Itc999_xy_emu.ppt
0 if i is neither source nor sink of o if i is source of o =1 k =1 j =1 − 1 if i is sink of o if i is neither source nor sink of o 0 N N yijo − ∑ y kio = 1 if i is source of o ∑ k =1 j =1 − 1 if i is sink of o N
∑x −∑x
o ki
xlo + y lo ≤ 1 for all l and o
Path Diversity Constraint
Integrality Constraint
cinkler()tmit.bme.hu
α <1
s.t. (constraints)
o ki
+ ylo b o ≤ Bl for all links l
)
• Élek helyett csomópont vagy teljes út basic-models-day-1-LUND.ppt (M. Pióro)
• indices – d=1,2,…,D – p=1,2,…,Pd – e=1,2,…,E
– NL: Node-Link • minden élre x minden folyamra változó
– LP: Link-Path
demands paths for flows realizing demand d links
• constants
• minden alternatív útra x minden folyamra változó
– hd – ce – δedp
– ANL: Aggregated Node-Link • Minden élre x minden forrásra aggregált folyam
volume of demand d capacity of link e = 1 if e belongs to path p realizing demand d; 0, otherwise
Forrás: M. Pióro cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
112
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
cinkler()tmit.bme.hu
so far we have been using link-path formulation applicable for both undirected and directed graphs
• variables – xed ≥ 0
indices
• variables
– d=1,2,…,D demands – v=1,2,... ,V nodes – e=1,2,...,E links (directed arcs)
flow realizing demand d on path p •
• constraints Σp xdp = hd d=1,2,…,D Σd Σp δedpxdp ≤ ce e=1,2,…,E – flow variables are continuous and non-negative
hd sd, td aev bev ce
Σe aev xed - Σe bev xed
volume of demand d source, sink node of demand d = 1 if link e originates at node v; 0, otherwise = 1 if link e terminates in node v; 0, otherwise capacity of link e
Forrás: M. Pióro vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
= = =
hd 0 - hd
if v = sd if v ≠ sd,td if v = td
v=1,2,...,V
Σd xed ≤ ce
For directed graphs (applicable to undirected graphs as well).
cinkler()tmit.bme.hu
flow of demand d on link e
• constraints
constants – – – – –
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Node-link formulation (eddig ezt használtuk)
Node-link formulation
Capacitated flow allocation problem – LP formulation
– xdp
113
e=1,2,…,E Forrás: M. Pióro
Forrás: M. Pióro cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
d=1,2,…,D
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
117
Aggregated node-link formulation
Aggregated node-link formulation
• variables – xev ≥ 0
• indices – v,w=1,2,... ,V – e=1,2,...,E
nodes arcs
• constants – hvw – – – –
Hv aev bev ce
Number of variables and constraints
flow realizing all demands originating at node v on link e
• constraints Σe aev xev
volume of demand d originating at node v and terminating at node w = Σw≠v hvw total demand volume originating at node v = 1 if link e originates at node v; 0, otherwise = 1 if link e terminates in node v; 0, otherwise capacity of link e
= Hv
#variables
#constraints
L-P
P×V(V-1) = O(V2)
V(V-1) + (k×V)/2 = O(V2)
(k×V ×V(V-1))/2 = O(V3)
V ×V(V-1) + (k×V)/2 = O(V3)
v=1,2,...,V
(redundant)
N-L
Σe aew xev - Σe bew xev = hvw
v,w=1,2,...,V
v≠w
A/N-L (k×V×V)/2 = O(V2)
Σv xev ≤ ce
e=1,2,…,E
V×V + (k×V)/2 = O(V2)
Remark: still N-L can be faster than A/N-L Forrás: M. Pióro cinkler()tmit.bme.hu
Forrás: M. Pióro
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
cinkler()tmit.bme.hu
5. Nemlineáris problémák megoldása
– Non-Convex • Special Formulations • Branch-and-Bound Decomposition – exact or approximations
• Többcélú (pareto optimum) 121
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Constrints: • x2 − y2 + z2 ≤ 2 • x2 + y2 + z2 ≤ 10 Objective: • max f(x,y,z) = xy + yz
• The intersection of the line with the constrained space represents the solution • http://en.wikipedia.org/wiki/Nonlinear_programming 122
Minimize (with respect to x)
•
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
123
If Q is a positive semidefinite matrix, then f(x) is a convex function. In this case the quadratic program has a global minimizer if there exists at least one vector 'x' satisfying the constraints.
•
If the matrix Q is positive definite then this global minimizer is unique. For positive-definite Q, the ellipsoid method solves the problem in polynomial time. If Q has at least one negative eigenvalue, the problem is NP-hard.
•
If Q is zero, then the problem becomes a linear program.
•
If there are only equality constraints, then the QP can be solved by a linear system.
•
Otherwise, a variety of methods for solving the QP are commonly used, including – interior point – active set and – conjugate gradient methods.
1. Ax ≤ b (inequality constraint) 2. Ex = d (equality constraint)
124
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
•
Subject to one or more constraints of the form: •
where x’ indicates the vector transpose of x. cinkler()tmit.bme.hu
cinkler()tmit.bme.hu
Quadratic Programming Cases
• http://en.wikipedia.org/wiki/Quadratic_programming • Quadratic programming is a special case of the more general field of convex optimization • Assume x belongs to Rn space. The n×n matrix Q is symmetric, and c is any n×1 vector.
The intersection of the top surface with the constrained space in the center represents the solution http://en.wikipedia.org/wiki/Nonlinear_programming
120
Constraints: • x≥0 • y≥0 • x2 + y2 ≥ 1 • x2 + y2 ≤ 2 Objective: • max f(x,y) = x + y
Quadratic Programming
3D példa – nem-lineáris célfüggvény
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
2D példa – nem-lineáris korlátok
• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-48643227-0. • Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1. • Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2. • Dimitri P. Bertsekas (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.
• Quadratic Programming • Szakaszos lineáris közelítés • Közelítés függvénnyel (pl. hatványfüggvény)
•
cinkler()tmit.bme.hu
• http://en.wikipedia.org/wiki/Nonlinear_programming • Ha a célfüggvény lineáris és az állapottér polytop → LP
– Ha csak a célfüggvény és/vagy – A korlátok (kényszerek) nemlineárisak – Convex Programming
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Forrás: M. Pióro 119
Nemlineáris programozás
• Nonlinear programming
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
125
Quadratic programming is a special case of the more general field of convex optimization.
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
126
• •
Nemlineáris linearizálása
Ha van idő: Rugalmas forgalom (Elastic Traffic) kezelése
Konkáv és Konvex (Pióro slidek) Nemlineárisból lineárisat (pl. logaritmus szakaszos közelítése: ∧) – Convex költségfüggvény kezelése és konvex korlátok kezelése
• Networks2002 cikk Elastic Traffic-cal (a PPT képletek nélkül van!!!) Networks2002_ela4.ppt • Nemlineáris kezelése iterációval (Relative fairness) • Log szakaszos közelítése: Proportional Rate Fairness
• nemlineáris, de convex korlátok kezelése (egészértékű változókra) • nemlineáris, de convex célfüggvény kezelése (egészértékű változókra)
•
Linearisation of convex (cost) functions – convex definíció AMO 544.oldal közép – 546 és 552 convex célfüggvény concave convex – Ha integer megoldásra törekszünk akkor linearizáljunk úgy, hogy a töréspontok az x tengely egészértékű pontjaiban legyenek! – Bármilyen integer bemenetre definiált függvény felírható szakaszos közelítéssel, de a közelítőszakaszok száma egyenlő lesz az értelmezési tartomány hosszával!!! log közelítése 6 szakasszal:
Minimalizáláshoz konkáv Maximalizáláshoz konvex fgv kell
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Uncapacitated flow allocation problem variants
127
cinkler()tmit.bme.hu
Uncapacitated problem - convex link penalty functions
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
• objective minimize F(y) = Σe ξeye
( F(y) = Σe Σk ξekyek )
Σd Σp δedpxdp ≤ M⋅ye e=1,2,…,E ye integer - MIP Σd Σp δedpxdp ≤ M⋅ye e=1,2,…,E xdp, ye integer – IP Σd Σp δedpxdp ≤ Σk Mk⋅yek e=1,2,…,E yek integer – MIP – incremental modular function (most general, Section 4.3.1): Σd Σp δedpxdp ≤ Σk mk⋅uek e=1,2,…,E uek binary – MIP ue1 ≥ ue2 ≥ ... ≥ ueK e=1,2,…,E
• objective minimize F(y) = Σe ξef(ye) – ye = Σd Σp δedpxdp – f(z) – convex (penalty, delay) - CXP – f(z) – concave (dimensioning function) - CVP 128
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
Uncapacitated problem - concave link dimensioning functions
LP approximation of the convex problem f(y) f(y) = c3y+b3
• objective minimize F(x) = Σe ξef( Σd Σp δedpxdp ) • constraints: f(y) = c1y+b1
f(y) a1
• •
One global minimum. Solution is bifurcated. y1 < y2 → f(y1)/y1 < f(y2)/y2
minimize z constraints
cinkler()tmit.bme.hu
c3y+b3 c2y+b2 Using this approximation we can convert CVP to MIP.
b2 c1y+b1 y
Numerous local minima. Solution is non-bifurcated. y1 < y2 → f(y1)/y1 > f(y2)/y2
a2
y
• minimize z = ∑k (ckyk + bkuk) • constraints:
( z = f(y) )
– ∑k yk = y – ∑k uk = 1 – 0 ≤ yk ≤ ∆uk, uk ∈ {0,1} , k=1,2,…,n
y
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
cinkler()tmit.bme.hu
• • • • • •
Binaris linearizalása Diszkrét és integer visszavezetése binárisra Logikai relációk kezelése: ∧, ∨, ⇔, ⇒ (Lengyel slidek) z=xy For the linearisation of the product xy of two binary variables x and y I have used two approaches. T. Cinkler, P. Laborczi, Á. Horváth: "Protection through Thrifty Configuration", ITC 16, 16th International Teletraffic Congress, Edinburgh, UK, June 1999 (http://opt.tmit.bme.hu/~cinkler/MYPUB/itc5.ps)
• • • • •
Boole x + y >= z 1 + x - y >= z 1 - x + y >= z - 1 + x + y <= z
• • • •
or something similar... Where binary variable z will have value z=xy BOOLEAN ALGEBRA TUTORIAL: http://www.doc.ic.ac.uk/~dfg/hardware/hardware.html MinMax és MaxMin feladatok: Pl.: Vzs1 és Vzs2 2005/2006 őszi félév végén Min-Max: Ha szeretnénk, hogy a legnagyobb is a lehető legkisebb legyen, akkor mindegyiket felülről korlátozzuk egy segédváltozóval és e segédváltozót minimalizáljuk, vagy csak hozzácsapjuk a célfüggvényhez. y1, y2, y3 ≥ 0; y1, y2, y3 ≤Y; min Y; Hasonlóan a Max-Min problémánál y1, y2, y3 ≥Y; max Y;
•
Simpler y >= z x >= z -1 + x + y <= z
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
6. Irodalomjegyzék (könyvek)
Logikai kifejezések ILP-sítése (és, vagy, akkor, stb.)
f(y)
a1
y
– z ≥ cky + bk , k=1,2,…,n
Linear approximation of the concave problem
b1
a2
Using this approximation we can convert CXP to LP.
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
b3
y
( z = f(y) )
y cinkler()tmit.bme.hu
objective minimize F(x) = Σe ξef( Σd Σp δedpxdp ) constraints: – all flows non-negative d=1,2,…,D Σp xdp = hd
f(y) = c2y+b2
– all flows non-negative Σp xdp = hd d=1,2,…,D
f(y)
• •
M.S. Bazaraa, J.J. Jarvis, H.D. Sherali: Linear Programming and Network Flows, Wiley 1990 R. Bhandari: Survivable Networks – Algorithms for Diverse Routing, Kluwer 1990 M. Pióro, D. Medhi: Routing, Flow and Capacity Design in Communication and Computer Networks, Morgan Kaufmann 2004 R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows- Theory, Algorithms, and Applications, Prentice Hall 1993
Two constraints only x + y >= 2z -1 + x + y <= z
G. Ausiello et al.: Complexity and Approximations – Combinatorial Optimization Problems and Their Approximability Properties, Springer 1999 L.A. Wolsey: Integer Programming, Wiley 1998 Vízvári B.: Egészértékű Programozás, Typotex 2006 Z. Michalewicz: Genetic Algorithms + Data Strutures = Evolution Programs, Springer 1992 M.R. Garey, D.S. Johnson: Computers and Intractability – A Guide to the Theory of NP-Completeness, Freeman 1979 V.V. Vazirani: Approximation Algorithms, Springer 2003
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
134
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
135
6. és 7. alkalom 2006.XI.6. és 8. 8:00-10:05 IB.142 hétfőn IB.141 szerdán
Alkalmazott optimalizálás és játékelmélet (Applied Optimisation and Game Theory) vittd097 Rétvári Gábor, Tapolcai János
[email protected],
[email protected] TMIT, 2006 ősz http://opti.tmit.bme.hu/optgame/ http://www.vdk.bme.hu/targykov/doktorandusz/vittd097.htm
cinkler()tmit.bme.hu
vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz
136