Competitive Programming II

Recommended Prerequisites

Not applicable.

Teaching Methods

Tutorial sessions are used to introduce theoretical concepts and to discuss approaches to particular problems. Lab sessions consist in solving programming problems, individually and in a team, while paying special attention to problem statement interpretation, problem modelling, and implementation issues. The assessment takes into account the grades obtained in solving several programming problems and in individual defences.

Learning Outcomes

To develop skills in solving programming problems based on engineering challenges where optimal solutions cannot usually be found in a suitable amount of time. Problems of this kind regularly arise in the context of programming and solver competitions such as the Google Hash Code and the ROADEF/EURO challenges. From a description of a problem, the successful student should be able to, individually and in a team, relate it to other known problems, identify appropriate heuristic approaches to address it, develop a suitable problem model, and implement an effective solution approach in an efficient manner.

Work Placement(s)

No

Syllabus

1. Introduction 1.1. Optimisation problems in programming competitions 1.2. Constructive heuristics and improvement heuristics 1.3. Heuristic principles 1.4. Strategies for solving competition problems 2. Problem modelling 2.1. Definition of the decision space 2.2. Solution representation 2.3. Evaluation of solution quality 2.4. Construction rules and neighbourhood structures 2.5. Constraint handling 3. Heuristics and meta-heuristics 3.1. Constructive methods: greedy construction, ant colony optimisation, beam search 3.2. Improvement methods: hill climbing, iterated local search, evolutionary algorithms, tabu search 4. Performance issues 4.1. Memoisation, lazy evaluation, and incremental evaluation 4.2. Parameter tuning and parameter adaptation.

Head Lecturer(s)

Carlos Manuel Mira da Fonseca

Assessment Methods

Assessment
The assessment takes into account the grades obtained in solving several programming problems and in individual defences: 100.0%

Bibliography

George Polya, How to Solve It: A New Aspect of Mathematical Method. Princeton University Press, 1945. Reprinted by Penguin Books, 1990. Fred Glover and Manuel Laguna,Tabu Search, Kluwer, 1997. Thomas Bäck, David B Fogel, and Zbigniew Michalewicz (eds.), Evolutionary Computation 1 - Basic Algorithms and Operators, CRC Press, 2000. Thomas Bäck, David B Fogel, and Zbigniew Michalewicz (eds.), Evolutionary Computation 2 - Advanced Algorithms and Operators, CRC Press, 2000. Marco Dorigo and Thomas Stützle, Ant Colony Optimization, MIT Press, 2004. Holger H. Hoos and Thomas Stützle, Stochastic Local Search, Morgan Kaufmann, 2014. Mauricio G. C. Resende and Celso C. Ribeiro, Optimization by GRASP, Springer, 2016. Rafael Martí, Panos M. Pardalos, Mauricio G. C. Resende, Handbook of Heuristics, Springer, 2018.