Algorithmic Methods for Mathematical Models

You are here

Credits
6
Types
Compulsory
Requirements
This subject has not requirements, but it has got previous capacities
Department
DAC;CS
The task of building mathematical models that represent real-world problems and using existing tools for solving such models is an ubiquitous task in computer science. Knowledge about such tools and algorithms allows one to weigh up the balance between how precisely we formalize the problem and how tractable the resulting model is.

With an special emphasis on their application to concrete computer science problems, this course will review some of these mathematical models and algorithms. First of all, we will review the basics of linear and non-linear programming. Then, metaheuristic algorithms will be presented as an alternative to the previous methods for combinatorial optimization problems.

Teachers

Person in charge

  • Enric Rodriguez Carbonell ( )

Others

  • Luis Domingo Velasco Esteban ( )

Weekly hours

Theory
3
Problems
0
Laboratory
0.9
Guided learning
0.1
Autonomous learning
4

Competences

Technical Competences of each Specialization

Computer networks and distributed systems

  • CEE2.1 - Capability to understand models, problems and algorithms related to distributed systems, and to design and evaluate algorithms and systems that process the distribution problems and provide distributed services.

Advanced computing

  • CEE3.2 - Capability to use a wide and varied spectrum of algorithmic resources to solve high difficulty algorithmic problems.

Generic Technical Competences

Generic

  • CG1 - Capability to apply the scientific method to study and analyse of phenomena and systems in any area of Computer Science, and in the conception, design and implementation of innovative and original solutions.
  • CG3 - Capacity for mathematical modeling, calculation and experimental designing in technology and companies engineering centers, particularly in research and innovation in all areas of Computer Science.

Transversal Competences

Teamwork

  • CTR3 - Capacity of being able to work as a team member, either as a regular member or performing directive activities, in order to help the development of projects in a pragmatic manner and with sense of responsibility; capability to take into account the available resources.

Reasoning

  • CTR6 - Capacity for critical, logical and mathematical reasoning. Capability to solve problems in their area of study. Capacity for abstraction: the capability to create and use models that reflect real situations. Capability to design and implement simple experiments, and analyze and interpret their results. Capacity for analysis, synthesis and evaluation.

Objectives

  1. Modelling in various mathematical formalisms the problems arising in different computer science disciplines
    Related competences: CG1, CG3, CEE2.1, CTR3, CTR6,
  2. Becoming familiar with state-of-the-art tools used to solve various mathematical models
    Related competences: CG3, CEE2.1, CEE3.2, CTR3, CTR6,
  3. Understanding the basics of the algorithms used for solving various mathematical models
    Related competences: CEE2.1, CEE3.2,

Contents

  1. Linear Programming
    Basics on linear programming. Modelling examples. The simplex algorithm. Duality.
  2. Integer linear programming
    Modelling examples. Branch-and-bound, cuts and branch-and-cut.
  3. Non-linear programming
    Basics on non-linear programming. Modelling examples.
  4. Metaheuristics
    Constructive procedures. Local search. Metaheuristics: GRASP, Simulated Annealing, Tabu Search, Genetic algorithms, Ant Colony, Path Relinking, etc.

Activities

Activity Evaluation act


Linear programming


Objectives: 1 3
Theory
11.5h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Integer Linear Programming


Objectives: 1 3
Contents:
Theory
13h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
9h

Linear Programming Laboratory


Objectives: 2
Contents:
Theory
0h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
0h

Metaheuristics


Objectives: 1 3
Contents:
Theory
14h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
9h

Metaheuristics Laboratory


Objectives: 2
Contents:
Theory
0h
Problems
0h
Laboratory
6h
Guided learning
0h
Autonomous learning
6h

Project


Objectives: 1 2
Week: 16
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
1h
Autonomous learning
16h

Exam


Objectives: 1 2 3
Week: 18
Type: final exam
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Teaching methodology

Since the goal of the course is to provide the students with the necessary expertise to use different formalisms and tools to solve concrete problems, the teaching methodology will take that into account. Theory classes will always use motivating examples. In these sessions, students will solve simple exercises that will be key ingredients of more complicated algorithms.

In the laboratory sessions the students will become familiar with tools for solving problems computationally.

In the development of the project the students will be supervised by the instructors.

Evaluation methodology

The final grade of the course will take into account:

A) A practical work (project): 40%

B) A final exam: 60%

Bibliography

Basic:

Complementary:

Previous capacities

Students should be familiar with basic concepts in linear algebra: vector, matrix, rank, matrix inverse and solving systems of linear equations.

Addendum

Contents

No hi ha canvis respecte la informació publicada a la Guia Docent. There are no changes with respect to the information published at the Teaching Guide. No hay cambios respecto la información publicada en la Guía Docente.

Teaching methodology

No hi ha canvis respecte la informació publicada a la Guia Docent. There are no changes with respect to the information published at the Teaching Guide. No hay cambios respecto la información publicada en la Guía Docente.

Evaluation methodology

No hi ha canvis respecte la informació publicada a la Guia Docent. There are no changes with respect to the information published at the Teaching Guide. No hay cambios respecto la información publicada en la Guía Docente.

Contingency plan

En cas que no es pugui dur a terme la docència de forma presencial, les classes (de teoria i laboratori) s'impartiran de forma remota mitjançant Google Meet; els continguts, la metodologia docent i el mètode d'avaluació continuaran igual. In the circumstance where teaching cannot be carried out in person, the classes (theory and laboratory) will be taught remotely by means of Google Meet; the contents, the teaching methodology and the evaluation method will not change. En caso de que no se pueda llevar a cabo la docencia de forma presencial, las clases (de teoría y laboratorio) se impartirán de forma remota mediante Google Meet; los contenidos, la metodología docente y el método de evaluación continuarán igual.