Degree | Type | Year | Semester |
---|---|---|---|
4313136 Modelling for Science and Engineering | OB | 0 | 1 |
Mathematical knowledge at the level of Science degree
Programming skills
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.
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.
Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.
Title | Hours | ECTS | Learning Outcomes |
---|---|---|---|
Type: Directed | |||
Attending lectures and activities | 37.75 | 1.51 | 2, 1, 4, 3, 9, 8, 5, 6, 7, 10 |
Evaluation of the teaching performance and evaluation of the subject or module | 0.25 | 0.01 | |
Type: Autonomous | |||
Assignments (implementation of the algorithms – self-activities) | 42 | 1.68 | 2, 1, 4, 3, 8, 5 |
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%.
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 |
All the necessary bibliography is and will be on the course's web page https://mat.uab.cat/~alseda/MasterOpt/
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/
All programs used in the subject are "do it yourself"