Course Unit
Catalogue
Combinatorial optimisation
- Unit Coordinator: Albert Ruiz Cirera, Judit Chamorro Servent
- ECTS Credits: 6
- Semester: 1
- Year: 2
- Campus: Autonomous University of Barcelona
- Language: English
- Aims:
The objective of this course is to study and practise the paradigmatic problems (Routing, Scheduling, Location, Packing), relevant in logistics, that lead to discrete and combinatorial optimisation models, intrinsically difficult in practice due to its huge input size.
The modern metaheuristics for approximating the solutions of such problems, like Evolutionary Algorithms, Tabu Search, Particle Swarm, or Ant Colony will be introduced
- 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 optimization.
- Neural Networks in optimization.
- Scheduling.
- Machine learning trough neural networks.
- Pre-requisites:
Mathematical knowledge at the level of Science degree. Programming skills
- Reading list:
- Judea Pearl, A* Algorithms and such: Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
- Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Numerical Mathematics, , Texts in Applied Mathematicsm 37, Springer, 1991.
- Sean Luke, Essentials of Metaheuristics, 2009: http://cs.gmu.edu/∼sean/book/metaheuristics/
- David Beasley, David R. Bully and Ralph R. Martinz, An Overview of Genetic Algorithms (Part 1: Fundamentals and Part 2: Research Topics)
- S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by Simulated Annealing, Science, May 1983, Vol. 220, no. 4598, pp. 671-680.
- 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.
- Marco Dorigoa and Christian Blum, Ant colony optimizationtheory: A survey, Theoretical Computer Science 344 (2005) 243 - 278.
- 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).
- 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
- Kate Smith, Marimuthu Palaniswami and Mohan Krishnamoorthy. Neural Techniques for Combinatorial Optimization with Applications
- Lecture notes provided by the teacher.
