1 Outline Slide 1 Approximation algorithms Local search methods Simulated annealing 2 Approximation algorithms Algorithm H is an -approximation algorithm for a minimization problem with optimal cost Z , if H runs in polynomial time, and returns a feasible solution with cost ZH : Slide 2 ZH (1 + )Z For a maximization problem ZH (1 ; )Z 2.1 TSP 2.1.1 MST-heuristic Slide 3 Triangle inequality cij cik + ckj 8 i k j Find a minimum spanning tree with cost ZT Construct a closed walk that starts at some node, visits all nodes, returns to the original node, and never uses an arc outside the minimal spanning tree Each arc of the spanning tree is used exactly twice Total cost of this walk is 2ZT Because of triangle inequality ZH 2ZT But ZT Z , hence ZH 2ZT 2Z 1-approximation algorithm 1 Slide 4 2.1.2 Matching heuristic Find a minimum spanning tree. Let ZT be its cost Find the set of odd degree nodes. There is an even number of them. Why? Find the minimum matching among those nodes with cost ZM Adding spanning tree and minimum matching creates a Eulerian graph, i.e., each node has even degree. Construct a closed walk Performance ZH ZT + ZM Z + 1=2Z = 3=2Z 3 Local search methods Local Search: replaces current solution with a better solution by slight modi cation (searching in some neighbourhood) until a local optimal solution is obtained Recall the Simplex method 3.1 TSP-2OPT Two tours are neighbours if one can be obtained from the other by removing two edges and introducing two new edges Each tour has O(n2) neighbours. Search for better solution among its neighbourhood. Performance of 2-OPT on random Euclidean instances Size N 100 1000 10000 100000 1000000 Matching 9.5 9.7 9.9 9.9 2OPT 4.5 4.9 5 4.9 4.9 2 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 3.2 Extensions 4 Extensions Iterated Local Search Large neighbourhoods (example 3-OPT) Simulated Annealing Tabu Search Genetic Algorithms 4.1 Large Neighbourhoods Within a small neighbourhood, the solution may be locally optimal. Maybe by looking at a bigger neighbourhood, we can nd a better solution. Increase in computational complexity 4.1.1 TSP Again 3-OPT: Two tours are neighbour if one can be obtained from the other by removing three edges and introducing three new edges Slide 10 Slide 11 Slide 12 3-OPT improves on 2-OPT performance, with corresponding increase in execution time. Improvement from 4-OPT turns out to be not that substantial compared to 3-OPT. 5 Simulated Annealing Allow the possibility of moving to an inferior solution, to avoid being trapped at local optimum Idea: Use of randomization 3 Slide 13 5.1 Algorithm Starting at x, select a random neighbour y in the neighbourhood structure with probability qxy X qxy 0 y2N (x) Slide 14 qxy = 1 Move to y if c(y) c(x). If c(y) > c(x), move to y with probability e;(c(y);c(x))=T stay in x otherwise T is a positive constant, called temperature 5.2 Convergence We de ne a Markov chain. Under natural conditions, the long run probability of nding the chain at state x is given by e;c(x)=T A P ;c(z)=T with A = z e If T ! 0, then almost all of the steady state probability is concentrated on states at which c(x) is minimum But if T is too small, it takes longer to escape from local optimal (accept an inferior move with probability e;(c(y);c(x))=T ). Hence it takes much longer for the markov chain to converge to the steady state distribution 5.3 Cooling schedules T (t) = R= log(t). Convergence guaranteed, but known to be slow empirically. Exponential Schedule: T (t) = T (0)an with a < 1 and very close to 1 (a=0.95 or 0.99) commonly used. 4 Slide 15 Slide 16 5.4 Knapsack Problem X X max c x : a x b n i=1 i i n i=1 i i Let X = (x1 ::: xn) 2 f0 1gn Neighbourhood Structure: N (X ) = fY one entry has been changed Generate random Y = (y1 ::: yn): Choose j uniformly from 1 2 ::: n. yi = xi if i = 6 j . yj = 1 ; xj . P Accept if i ai yi b. 5.4.1 Example Slide 17 xi 2 f0 1g 2 f0 1gn : d(X Y ) = 1g. Exactly =(135, 139, 149, 150, 156, 163, 173, 184, 192, 201, 210, 214, 221, 229, 240) � =(70, 73, 77, 80,82, 87, 90,94, 98, 106, 110, 113, 115, 118, 120) � = 750 � � = (1 0 1 0 1 0 1 1 1 0 0 0 0 1 1), with value 1458 Cooling Schedule: T0 = 1000 probability of accepting a downward move is between 0.787 (ci = 240) and 0.874 (ci = 135). Cooling Schedule: T (t) = T (t ; 1), = 0:999 Number of iterations: 1000, 5000 Performance: 1000 iterations: best solutions obtained in 10 runs vary from 1441 to 1454 5000 iterations: best solutions obtained in 10 runs vary from 1448 to 1456. � c Slide 18 Slide 19 a b X 5 Slide 20 Slide 21