Logo UAB
2022/2023

Optimization

Code: 42250 ECTS Credits: 6
Degree Type Year Semester
4313136 Modelling for Science and Engineering OB 0 1

Contact

Name:
Albert Ruiz Cirera
Email:
albert.ruiz@uab.cat

Use of Languages

Principal working language:
english (eng)

Teachers

Albert Ruiz Cirera
Judit Chamorro Servent

Prerequisites

  • Mathematical knowledge at the level of Science 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

  1. Analyse, synthesise, organise and plan projects in the field of study.
  2. 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.
  3. Apply optimisation techniques to study models associated with practical problems.
  4. Apply specific methodologies, techniques and resources to conduct research and produce innovative results in the area of specialisation.
  5. Identify problems that require optimisation techniques to build models associated with practical problems.
  6. Implement the algorithms that are present in the programme.
  7. Implement the proposed solutions reliably and efficiently.
  8. Isolate the main difficulty in a complex problem from other, less important issues.
  9. Present study results in English.
  10. Use specific software to solve optimisation problems..

Content

Main contents:

  • Combinatorial Algorithms for graphs and routing: Dijstra and A* algorithms. Optimisation over graphs.
  • Deterministic optimization (constrained and non-constrained).

Possible additional topics:

  • Genetic Algorithms.
  • Simulated Annealing.
  • Ant colony optimisation algorithms.
  • Others.

Methodology

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.

Activities

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

Assessment

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, code and oral presentation.

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, 8, 5, 6, 7, 10
Individual projects in realistic cases 40% 28 1.12 2, 1, 4, 3, 8, 5, 6, 7, 10
Projects in realistic cases in two-person teams (exceptionally, three-person) 30% 21 0.84 2, 1, 4, 3, 9, 8, 5, 6, 7, 10

Bibliography

  • David Beasley, David R. Bully and Ralph R. Martinz, An Overview of Genetic Algorithms (Part 1: Fundamentals and Part 2: Research Topics).
  • Marco Dorigoa and Christian Blum, Ant colony optimization theory: A survey, Theoretical Computer Science 344 (2005) 243 - 278.
  • 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.
  • 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