CombinatorialProblems TheAlgorithm Parameter ConclusionandSources SIMULATED ANNEALING AMETHODETOSOLVECOMBINATORIALPROBLEMS KurniaHendrawan [email protected] 30May2007 KurniaHendrawan [email protected] SimulatedAnnealing CombinatorialProblems TheAlgorithm Parameter ConclusionandSources OUTLINE 1 COMBINATORIAL PROBLEMS 2 THE ALGORITHM 3 PARAMETER 4 CONCLUSION AND SOURCES KurniaHendrawan [email protected] SimulatedAnnealing CombinatorialProblems TheAlgorithm Parameter ConclusionandSources OUTLINE 1 COMBINATORIAL PROBLEMS 2 TheAlgorithm 3 Parameter 4 ConclusionandSources KurniaHendrawan [email protected] SimulatedAnnealing CombinatorialProblems TheAlgorithm Parameter ConclusionandSources WHAT IS A COMBINATORIAL PROBLEM? Whichproblems givennobjectstoobserve Parameters searchforoptimum Classic Focus: "better"result examples KurniaHendrawan [email protected] SimulatedAnnealing CombinatorialProblems TheAlgorithm Parameter ConclusionandSources WHAT IS A COMBINATORIAL PROBLEM? Whichproblems S:solutionsspace Parameters f: costfunction Classic f(i): qualityofsolution examples KurniaHendrawan [email protected] SimulatedAnnealing CombinatorialProblems TheAlgorithm Parameter ConclusionandSources WHAT IS A COMBINATORIAL PROBLEM? Whichproblems Clique Parameters TSP Classic Hamilton-Path examples KurniaHendrawan [email protected] SimulatedAnnealing CombinatorialProblems TheAlgorithm Parameter ConclusionandSources RESOLUTION METHODES "bruteforce" Numerical searchinginthewholeS methode pro: findtheglobaloptimum Heuristical con: hugecomplexity methode KurniaHendrawan [email protected] SimulatedAnnealing CombinatorialProblems TheAlgorithm Parameter ConclusionandSources RESOLUTION METHODES stochastic Numerical localsearch: methode iterationwithlimitedworkspace Heuristical searchingintheneighbourhood methode KurniaHendrawan [email protected] SimulatedAnnealing CombinatorialProblems TheAlgorithm Parameter ConclusionandSources LOCAL SEARCH HOWDOESITWORK? INITILIZATION ITERATION Choosearandomsolutioni 1. Trytofindabettersolution fromtheworkspace(TSP: ontheneighbourhoodofi choosearandompermutation (TSP:changetherouteabit) forthetrip) 2. Recordbettersolutions 3. Iterateback 4. Terminateifthewhole neighbourhoodiscompletely searched KurniaHendrawan [email protected] SimulatedAnnealing CombinatorialProblems TheAlgorithm Parameter ConclusionandSources LOCAL SEARCH HOWDOESITWORK? INITILIZATION ITERATION Choosearandomsolutioni 1. Trytofindabettersolution fromtheworkspace(TSP: ontheneighbourhoodofi choosearandompermutation (TSP:changetherouteabit) forthetrip) 2. Recordbettersolutions 3. Iterateback 4. Terminateifthewhole neighbourhoodiscompletely searched KurniaHendrawan [email protected] SimulatedAnnealing