Optimisation
Code: 42250 ECTS Credits: 6| Degree | Type | Year |
|---|---|---|
| Modelización para la Ciencia y la Ingeniería / Modelling for Science and Engineering | OB | 1 |
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 dedicated to studying and practicing various deterministic and heuristic optimization methods, with special emphasis on routing and convex optimization. The course will also cover other optimization topics.
This course aims to provide students with the necessary knowledge and basic tools to model and solve optimization problems.
Learning Outcomes
- CA01 (Competence) Integrate specific optimisation tools with the aim of improving the efficiency and accuracy of different mathematical modelling processes.
- CA02 (Competence) Communicate the results obtained from addressing specific optimisation problems to an expert audience.
- CA03 (Competence) Work in multidisciplinary teams to develop optimisation solutions in the modelling of processes and problems in applied and/or professional contexts.
- KA01 (Knowledge) Identify the most common programming environments to solve optimisation problems.
- KA02 (Knowledge) Identify the structure and functionality of the main mathematical optimisation algorithms.
- SA01 (Skill) Apply specific software to solve optimisation problems.
- SA01 (Skill) Apply specific software to solve optimisation problems.
- SA02 (Skill) Apply optimisation techniques that provide an adequate response to particular problems.
- SA03 (Skill) Interpret the results obtained from implementing optimisation algorithms in particular 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 | |
| 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 |
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 | CA01, CA02, CA03, KA01, KA02, SA01, SA02, SA03 |
| Individual projects in realistic cases | 30% | 21 | 0.84 | CA01, CA02, KA01, KA02, SA01, SA02, SA03 |
| Projects in realistic cases in two-person teams (exceptionally, three-person) | 40% | 28 | 1.12 | CA01, CA02, CA03, KA01, KA02, SA01, SA02, SA03 |
The assessment has three parts:
- Individual assigments: summary report and code solving a given problem.
- Two-person assigments (if necessary due to the number of students, a group of 3 would be accepted): summary report and code soling a given problem.
- Four-person assigment (if necessary due to the number of students, a group of 3 or 5 would be accepted): report, (may include code) and oral presentation.
The final grade for the subject will be:
- The weighted average according to the weight of each part for those students who have taken 3.5 or more in all parts.
- The minimum between 3.5 and the weighted average according to the weight of each part for those students who have done at least two of the parts and in some of the parts do not reach 3.5.
- Not assessable for those students who have done less than two of the parts.
Students who, despite having been evaluated in at least two of the three parts, do not pass the subject may ask the teaching staff to be re-evaluated in the parts they have not passed (this re-evaluation may include assignments and an oral exam).
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.
- Anders Hansson, Martin Andersen, Optimization for Learning and Control, John Wiley & Sons, Inc., 2023.
- 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
Groups and Languages
Please note that this information is provisional until 30 November 2025. You can check it through this link. To consult the language you will need to enter the CODE of the subject.
| Name | Group | Language | Semester | Turn |
|---|---|---|---|---|
| (TEm) Theory (master) | 1 | English | first semester | afternoon |