Optimization
Code: 42250 ECTS Credits: 62024/2025
| Degree | Type | Year |
|---|---|---|
| 4313136 Modelling for Science and Engineering | OB | 0 |
Contact
- Name:
- Albert Ruiz Cirera
- Email:
- albert.ruiz@uab.cat
Teachers
- Albert Ruiz Cirera
- Judit Chamorro Servent
Teaching groups languages
You can view this information at the end of this document.
Prerequisites
-
Mathematical knowledge at the level of Science or Engineering bachelor 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 and convex optimisation. The course will also cover some additional topics.
This course aims to give students the fundamental knowledge and resources they need to create software that can handle actual optimization challenges.
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
Main contents:
- Combinatorial Algorithms for graphs and routing: Dijkstra and A* algorithms. Optimisation over graphs.
- Deterministic optimization (constrained and non-constrained).
Possible additional topics:
- Genetic Algorithms.
- Simulated Annealing.
- Ant colony optimisation algorithms.
- Others.
Activities and Methodology
| Title | Hours | ECTS | Learning Outcomes |
|---|---|---|---|
| Type: Directed | |||
| Attending at the different sessions and related activities | 37.75 | 1.51 | 2, 1, 4, 3, 9, 8, 5, 6, 7, 10 |
| Evaluation of the teaching performance and the subject | 0.25 | 0.01 | |
| Type: Autonomous | |||
| Assignments (implementation of the algorithms – individual and group activities) | 42 | 1.68 | 2, 1, 4, 3, 8, 5 |
The methodology is based on lectures with slide presentations and blackboard, including master and practical sessions.
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.
Assessment
Continous Assessment Activities
| Title | Weighting | Hours | ECTS | Learning Outcomes |
|---|---|---|---|---|
| Delivery and presentation of the final project (four-person teams) | 30% | 21 | 0.84 | 2, 1, 4, 3, 9, 8, 5, 6, 7, 10 |
| Individual projects in realistic cases | 30% | 21 | 0.84 | 2, 1, 4, 3, 9, 8, 5, 6, 7, 10 |
| Projects in realistic cases in two-person teams (exceptionally, three-person) | 40% | 28 | 1.12 | 2, 1, 4, 3, 9, 8, 5, 6, 7, 10 |
There are three types of evaluation:
- Individual assigments: summary report and code solving a given problem.
- Two-person assigments: summary report and code soling a given problem.
- Four-person assigment: report, (may include code) and oral presentation.
Bibliography
- David Beasley, David R. Bully and Ralph R. Martinz, An Overview of Genetic Algorithms (Part 1: Fundamentals and Part 2: Research Topics).
- Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for industrial and applied mathematics.
- Borwein, J., & Lewis, A. (2006). Convex Analysis and Nonlinear Optimization. CMS Books in Mathematics. Springer, New York, NY.
- Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
- Marco Dorigoa and Christian Blum, Ant colony optimization theory: A survey, Theoretical Computer Science 344 (2005) 243 - 278.
- Hansen, P. C. (2010). Discrete inverse problems: insight and algorithms. Society for Industrial and Applied Mathematics.
- S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by Simulated Annealing, Science, May 1983, Vol. 220, no. 4598, 671-680.
- Melanie Mitchell, An Introduction to Genetic Algorithms, A Bradford Book, The MIT Press, Cambridge Massachusetts, 1999.
- Nocedal, J., & Wright, S. J. (2006). Quadratic programming. Numerical optimization, 448-492.
- Nocedal, J., & Wright, S. J. (2006). Sequential Quadratic Programming. Numerical Optimization, 529-562.
- Judea Pearl, A* Algorithms and such: Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
- 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.
- Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Numerical Mathematics, Texts in Applied Mathematics 37, Springer, 1991.
Software
Recommended sofware:
- C
- MATLAB
Language list
| Name | Group | Language | Semester | Turn |
|---|---|---|---|---|
| (TEm) Theory (master) | 1 | English | first semester | afternoon |