Metaheuristics methods Helena Ramalhinho Outline Optimization Problems Metaheuristics brief introduction TSP an example Local Search LP ILP introduction 1 LP ILP introduction 2 Helena Ramalhinho Louren o 2022 1 Solution Methods For ILP and CO models Local Search Methods Metaheuristics Integer Programming Exact Methods LP ILP introduction 3 Solution Methods Local Search Methods Metaheuristics Local Improvement Tabu Search Iterated Local Search Simulated annealing Genetic Algorithms Evolutionary algorithms Ant Colony Optimization Scatter Search Memetic Algorithms Etc LP ILP introduction 4 Helena Ramalhinho Louren o 2022 2 Solution Methods Branch and bound Branch and cut Column generation Cutting and price Dynamic programming Lagrangian relaxation Linear relaxation Surrogate relaxation Etc Integer Programming Exact Methods LP ILP introduction 5 Solution Methods Local Search Methods Metaheuristics optimal solutions Mathematical proved Important information on the characteristics and properties of the problem Good solutions for complex and large scale problems Short running times Easily adapted Integer Programming Exact Methods LP ILP introduction 6 Helena Ramalhinho Louren o 2022 3 Metaheuristics Four attributes of Heuristics and Metaheuristics Accuracy Close to optimal Speed Small computational time Simplicity Flexibility No parameters adjustment easy to program Easy to adapt to other real problems Cordeau JF Gendreau M Laporte G Potvin JY Semet F 2002 A guide to vehicle routing heuristics J Oper Res Soc 53 512 522 LP ILP introduction 7 Algorithms Metaheuristics Have been designed to attack complex and large scales optimization problems where classical heuristics and optimization have failed so far to be effective and efficient When implementing a metaheuristic begin with a simple method and then turn if necessary to a more complicated one or refine the first implementation LP ILP introduction 8 Helena Ramalhinho Louren o 2022 4 Metaheuristics for real problems Metaheuristics Highly effective on hard problems Modularity Easy implementation Short updates Robust Able to give good solutions in short time Real Problems Complex problems Large scale problem Rapid changes in reality Need to quick implementation Different aspects in different sectors Need to quick answer and multiple scenarios LP ILP introduction 9 Local optimization algorithms Given a solution attempts to improve this solution by making local modifications at each iteration Neighborhood N A 2A subset of feasible solutions Define a local modification move the neighborhood of a solution x is the subset of feasible solutions obtained from applying this move to x Local optima solution x c x c y for all y N x Search Strategy the name of the metaheuristic come usually from the type of search LP ILP introduction 10 Helena Ramalhinho Louren o 2022 5 Local optimization algorithms Local search heuristic 1 Get a initial solution x current solution Use a constructive 2 Search the neighborhood While there is an untested neighbor of x 2 1 Let x be an untested neighbor of x 2 2 If c x c x set x x x is the new current solution 3 Return x local optimal solution LP ILP introduction 11 Local optimization algorithms Design of a local optimization algorithm Obtain an initial solution Heuristic Random solution Define the neighborhood Specific for each problem How to search the neighborhood Complete search First improvement LP ILP introduction 12 Helena Ramalhinho Louren o 2022 6 Traveling Salesman Problem Traveling Salesman Problem Given a number of cities and the costs distances of traveling from any city to any other city What is the least cost round trip route that visits each city exactly once and then returns to the starting city http www math uwaterloo ca tsp 12 10 5 8 10 18 14 LP ILP introduction 13 Traveling Salesman Problem Traveling Salesman Problem Traveling Salesman Problem A set of nodes cities E set of edges each has a cost c e F any subset of E forming a Hamilton cycle a feasible solution is closed loop through a graph that visits each node exactly once Minimize c F total cost of the edges in F 12 10 5 8 10 18 14 LP ILP introduction 14 5 6 5 6 Helena Ramalhinho Louren o 2022 7 Traveling Salesman Problem Mathematical programming model xij ji is if 1 otherwise 0 in the tour of number m number of n cost dista c edges vertices of nce ij edge ji min n n xc ij ij 1 i 1 j st n xij i 1 n j 1 n 1 1 i 1 n S 1 i j S xij 0 1 xij xij j 1 for all S 1 n i 1 n j 1 n LP ILP introduction 15 Traveling Salesman Problem Problem difficult to solve the size of the solution space is O n for n 2 where n is the number of cities NP hard problem P vs NP http news mit edu 2009 explainer pnp New York Times http www nytimes com 2009 10 08 science Wpolynom html http www claymath org millennium problems p vs np problem Play a game http www math uwaterloo ca tsp games index html LP ILP introduction 16 Helena Ramalhinho Louren o 2022 8 Neighborhood Traveling Salesman Problem 2 Opt Move Neighborhood Traveling Salesman Problem 3 Opt Move LP ILP introduction 17 LP ILP introduction 18 Helena Ramalhinho Louren o 2022 9 Local Search Examples Construction heuristics 2 opt local search method http www e uni magdeburg de mertens TSP TSP html Example TSP local search application LP ILP introduction 19 Initial solution and current solution Nearest neighbor heuristic The closest vertex to Berlin is Paris The closest vertex to Paris is Londres The closest vertex to Londres is Sevilla The closest vertex to Sevilla is Roma The closest vertex to Roma is Moscow The nearest to the initial vertex is Moscow SOLUTION Nearest Neighbor Route Berlin Paris Londres Sevilla Roma Moscow Berlin Length 65 LP ILP introduction 20 Helena Ramalhinho Louren o 2022 10 Example TSP local search application 2 opt neighborhood 9 neighbors Neighbor 1 Cost 69 Example TSP local search application 2 opt neighborhood 9 neighbors Neighbor 2 Cost 69 LP ILP introduction 21 LP ILP introduction 22 Helena Ramalhinho Louren o 2022 11 Example TSP local search application 2 opt neighborhood 9 neighbors Neighbor 3 Cost 78 Example TSP local search application 2 opt neighborhood 9 neighbors Neighbor 4 Cost 67 LP ILP introduction 23 LP ILP introduction 24 Helena Ramalhinho Louren o 2022 12 Example TSP local search application 2 opt neighborhood 9 neighbors Neighbor 5 Cost 63 Example TSP local search application 2 opt neighborhood 9 neighbors Neighbor 6 Cost 73 LP ILP introduction 25 LP ILP introduction 26 Helena