A tárgy II. részéről. Applied - Alkalmazott

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


4


5


•

•

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.




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.



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;


• • • • •

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

•


• • • • • •

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.



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


•

• 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



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



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”


•

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


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



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


13


•

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 • •



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ó?


16


14


Heurisztika

Metaheurisztika

http://en.wikipedia.org/wiki/Heuristic

http://en.wikipedia.org/wiki/Metaheuristic


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.



17



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.



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



original problem: (IP)


• • • •

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


m N(i)

l i k j


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



• •

maximise cx subject to Ax ≤ b x≥0

23

•


• •

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


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).


– 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)


• állapottér (S)

Legegyszerűbb approximáció: Dekompozíció

„Állapottér robbanás” • • • •

2. Diszkrét Optimalizálás


Fractional z = 22


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




26


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



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



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?

• • • • • •


3.2. Elágazás-korlátozás


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


• Nagyon jól kell megválasztani a 2 függvényt

34




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


• 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.


• 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


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


• 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


3. Néhány „meta-heurisztikus” módszer


• Probléma • Modell • Megoldó módszer

35



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ó



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



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


40


{0,0,0,1}

{0,0,0,1}

{0,0,1,1}

{0,1,1,1}


{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}


{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


{0,1,0,1}

{0,1,1,0}

{1,0,0,1}

{1,0,1,1}

{1,0,1,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,0,0}

{1,1,1,0}

{1,1,1,1}


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}


•

{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ő



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


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



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


Gradiens módszer

– random walks – Stb.

46


3.7. Véletlen újraindítású hegymászás


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



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}


– 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}


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


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


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



52


{1,0,1,1}

{1,1,0,1}

{1,1,1,1}


– 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



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}


55


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



•

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: –


• 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



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)


Simulated Annealing

• • • • • • • •

Alkalmazott optimalizálás és játékelmélet



3.9. Szimulált Lehűtés (Simulated Annealing)

3. alkalom


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}


Mohó algoritmus TSP-re: Nearest neighbour algorithm

61



62



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


ILP megoldás SA-val


64

{1,0,1,1} →18

{1,1,0,1} →23

{1,1,1,0} →25

{1,1,1,1} →29



Simulated Annealing applied to the Travelling Salesman Problem (TSP)

65



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



67


3.11. Tabu Search • • • •



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



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)


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?



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



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



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.


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)


74



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.)



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.)

• •

• •



• 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


– Learning to Speed Up Search: • http://www.cs.cornell.edu/~weiwei/workshop-aaai02-new.ppt • local copy: STAGE_workshop-aaai02-new.ppt




77


79



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|)


• 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



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



82



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


3.18. Raj (Swarm Inteligence: SI)

• Csoportoakat törlünk

{0,1,0,0} →11


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


85


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ó



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)

•


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


88



89



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


91

Shortest Path


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



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



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}


for all links l vittd097 ― Alkalmazott optimalizálás és játékelmélet ― 2006 ősz

95


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


o ki

(Applied Optimisation and Game Theory) For all nodes i and commodities o


Boolean/Maximum Satisfiability Problem • •


for all links l


• Az ILP NP nehéz (Pióro sl. ) Max Sat-ra visszavezetés


≤ 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



98

http://en.wikipedia.org/wiki/Boolean_satisfiability_problem http://en.wikipedia.org/wiki/Maximum_satisfiability_problem



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





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


• Integrality Property: Every minimum cost flow problem with integer demands and integer capacities has an integer optimal solution!



Mi van, ha útfüggetlen védelmet is keresünk? (Diverse Routing)


104


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




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


105

1 C

3 C

-1 C

A

1

1

Z

3 B

– Ferdén súlyozott is lehet...

B

3 1


B

Shortest sets of disjoint paths

• 2 Dijkstra • Suurballe • ILP


102

LP vagy ILP?

The SAT problem is directly reducible to this IP problem. Given: Question:


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


NP-Completeness cntd.




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


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


110


o l'

for all nodes i and commodities o

ylo b o ≤ Yl for all l

NONLINEAR!

xlo , y lo ∈ {0,1}


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


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


α <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



112




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).


flow of demand d on link e

• constraints

constants – – – – –


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



d=1,2,…,D



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



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



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)

•




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


•

Subject to one or more constraints of the form: •

where x’ indicates the vector transpose of x. 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


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)

•


• 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



Nemlineáris programozás

• Nonlinear programming



125

Quadratic programming is a special case of the more general field of convex optimization.



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



Uncapacitated flow allocation problem variants

127


Uncapacitated problem - convex link penalty functions


• 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



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


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



• • • • • •

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


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.


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





134



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



136

A tárgy II. részéről. Applied - Alkalmazott

Recommend Documents