Approximation Algorithms and Heuristics

Many discrete optimisation problems encountered in practice are too difficult to solve exactly in a reasonable time frame. Approximation algorithms and heuristics are the most widely used approaches for obtaining reasonably accurate solutions to such hard problems. This subject introduces the basic concepts and techniques underlying these “inexact” approaches. We will address the following fundamental questions in the subject: How difficult is the problem under consideration? How closely can an optimal solution be approximated? And how can we go about finding near-optimal solutions in an efficient way? We will discuss methodologies for analysing the complexity and approximability of some important optimisation problems, including the travelling salesman problem, knapsack problem, bin packing, scheduling, network design, covering problems and facility location. We will also learn about various metaheuristics (simulated annealing, Tabu search, GRASP, genetic algorithms) and matheuristics (relax-and-fix, fix-and-optimise, local branching) that are widely used in solving real-world optimisation problems.