Optimization
Code: 42250 ECTS Credits: 6| Degree | Type | Year | Semester |
|---|---|---|---|
| 4313136 Modelling for Science and Engineering | OB | 0 | 1 |
Contact
- Name:
- Lluís Alseda Soler
- Email:
- Lluis.Alseda@uab.cat
Use of Languages
- Principal working language:
- english (eng)
Teachers
- Albert Ruíz Cirera
Prerequisites
-
Mathematical knowledge at the level of Science degree
-
Programming skills
Objectives and Contextualisation
The course is devoted to study and practise several heuristic and combinatorial optimisation algorithms with special emphasis on routing, graph, network optimisation and scheduling.
The lectures are based based in slides presentations and internet material.
The theoretical material will be complemented with some assignments (at leats one) for every subject to be developed individually by the students. This is a critical part of the learning process.
Competences
- Analyse, synthesise, organise and plan projects in the field of study.
- Apply logical/mathematical thinking: the analytic process that involves moving from general principles to particular cases, and the synthetic process that derives a general rule from different examples.
- Apply specific methodologies, techniques and resources to conduct research and produce innovative results in the area of specialisation.
- Apply techniques for solving mathematical models and their real implementation problems.
- Conceive and design efficient solutions, applying computational techniques in order to solve mathematical models of complex systems.
- Formulate, analyse and validate mathematical models of practical problems in different fields.
- Isolate the main difficulty in a complex problem from other, less important issues.
- Present study results in English.
- Use appropriate numerical methods to solve specific problems.
Learning Outcomes
- Analyse, synthesise, organise and plan projects in the field of study.
- Apply logical/mathematical thinking: the analytic process that involves moving from general principles to particular cases, and the synthetic process that derives a general rule from different examples.
- Apply optimisation techniques to study models associated with practical problems.
- Apply specific methodologies, techniques and resources to conduct research and produce innovative results in the area of specialisation.
- Identify problems that require optimisation techniques to build models associated with practical problems.
- Implement the algorithms that are present in the programme.
- Implement the proposed solutions reliably and efficiently.
- Isolate the main difficulty in a complex problem from other, less important issues.
- Present study results in English.
- Use specific software to solve optimisation problems..
Content
- Combinatorial Algorithms for graphs and routing: Dijstra and A* algorithms. Optimisation on graphs.
- Deterministic optimization for nonlinear problems (constrained and non-constrained)
- Genetic Algorithms
- Simulated Annealing
- Ant colony optimisation algorithms
- Particle swarm optimisation
- Neural Networks in optimisation
- Scheduling
- Machine learning trough neural networks
Methodology
The methodology is based on master classes which consist in the presentation of the theory, examples and some case studies for every algorithm of the syllabus.
Students will have to implement independently the algorithms studied in realistic situations as a crucial part of the learning process.
Activities
| Title | Hours | ECTS | Learning Outcomes |
|---|---|---|---|
| Type: Directed | |||
| Attending lectures and activities | 38 | 1.52 | 2, 1, 4, 3, 9, 8, 5, 6, 7, 10 |
| Type: Autonomous | |||
| Assignments (implementation of the algorithms – self-activities) | 42 | 1.68 | 2, 1, 4, 3, 8, 5 |
Assessment
There are 7 practical realistic home assignments which consist on a report and a functioning program. Three of them will be compulsory and four optional.
The optional assignments are to be done individually and can increment the final mark up to 20%.
Assessment Activities
| Title | Weighting | Hours | ECTS | Learning Outcomes |
|---|---|---|---|---|
| Implementation of algorithms in realistic cases in individual projects | 50% | 35 | 1.4 | 2, 1, 4, 3, 9, 8, 5, 6, 7, 10 |
| Implementation of algorithms in realistic cases in team projects | 50% | 35 | 1.4 | 2, 1, 4, 3, 9, 8, 5, 6, 7, 10 |
Bibliography
Combinatorial Algorithms
Judea Pearl, A* Algorithms and such: Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
Deterministic optimization for nonlinear problems
Numerical Mathematics, Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Texts in Applied Mathematicsm 37, Springer, 1991.
Convex Optimization (Notes of Lieven Vandenberghe)
Karush-Kuhn-Tucker conditions (Notes of Geoff Gordon & Ryan Tibshirani)
Penalty and Barrier Methods for constrained optimization
Genetic Algorithms
Sean Luke,Essentials of Metaheuristics, 2009.
http://cs.gmu.edu/∼sean/book/metaheuristics/
Melanie Mitchell, An Introduction to Genetic Algorithms, A Bradford Book, The MIT Press, Cambridge Massachusetts, 1999.
David Beasley, David R. Bully and Ralph R. Martinz, An Overview of Genetic Algorithms (Part 1: Fundamentals and Part 2: Research Topics)
Simulated Annealing algorithm
S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by Simulated Annealing, Science, May 1983, Vol. 220, no. 4598, pp. 671-680.
François Bergeret and Philippe Besse, Simulated Annealing, weighted simulated annealing and genetic algorithm at work.
William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, Numerical Recipes in C. The Art of Scientific Computing (second edition)}, Cambridge University Press.
Ant colony algorithms
Marco Dorigoa and Christian Blum, Ant colony optimizationtheory: A survey, Theoretical Computer Science 344 (2005) 243 – 278.
Scheduling
Ronald L. Graham, Combinatorial Scheduling Theory
R. Gary Parker, Deterministic Scheduling Theory, Chapman Hall.
Peter Brucker, Scheduling Algorithms, Fourth Edition, Springer
R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Khan, Optimization and approximation in deterministic sequencing and scheduling: a survey
Peter Brucker, Scheduling Algorithms, Springer-Verlag, 2007, Berlin Heidelberg New York (ISBN 978-3-540-69515-8).
Neural Networks for Combinatorial Optimization
Jean-Yves Potvin, Kate A. Smith, Artificial Neural Networks for Combinatorial Optimization
Kate Smith, Neural Networks for Combinatorial Optimization: A Review of More Than a Decade of Research 1999.
Kate Smith, Marimuthu Palaniswami and Mohan Krishnamoorthy. Neural Techniques for Combinatorial Optimization with Applications
The originals of some of these references as presentation slides and other bibliography can be found in the web page of the subject:
http://mat.uab.cat/~alseda/MasterOpt/