ENGINEERING TRIPOS PART IIB - 2012 / 2013    (new module: not before 2012/13)

Module 4M17 - Practical Optimization

AIMS

This module aims to teach some of the optimization methods used to tackle difficult, real-world optimization problems, to develop an appreciation of practical issues associated with their implementation,and to provide experience in applying such methods on challenging problems and in assessing and comparing the performance of different algorithms.

LECTURE SYLLABUS

• Common Issues: performance measures, archiving, convergence criteria, treatment of constraints
• Line search and bracketing methods
• Direct search methods (Hooke & Jeeves, Nelder-Mead)
• Practical implementation of gradient-based methods for high dimensionality problems
• Practical issues in exploiting computational resources
• Combinatorial optimization (the knapsack problem) and greedy optimization
• Monte Carlo Sampling: basic concepts, solution representation and generation, sampling biasing
• Simulated Annealing: basic concepts, solution representation and generation, the annealing
schedule, enhancements and modifications
• Parallel Tempering: basic concepts, theory, choice of temperatures, sampling methods, global optimization
• Genetic Algorithms: basic concepts, solution representation, selection, crossover, mutation
• Tabu Search: basic concepts, solution representation, local search, intensification, diversification
• Multiobjective Optimization: archiving, multiobjective simulated annealing, multiobjective
genetic algorithms
• Case Study: multiobjective optimization of pressurised water reactor reload cores

Coursework exercises

1. Production of a 2D or 3D embedding of a graph (25%)
2. Solution of a large Travelling Salesman Problem (25%)
3. Investigation of the performance of two stochastic optimization methods on a hard problem (50%)

REFERENCES

Please see the Booklist for Group M Courses for references for this module.

Last updated: February 2012