Ficha

Versión en español

Course: 2024/2025

Heuristics and Optimization

(15976)

Bachelor in Computer Science and Engineering (Plan: 489 - Estudio: 218)

Coordinating teacher: LINARES LOPEZ, CARLOS

Department assigned to the subject: Computer Science and Engineering Department

Type: Compulsory

ECTS Credits: 6.0 ECTS

Course: 3º

Semester: 1º

Requirements (Subjects that are assumed to be known)

Programming (Course: 1 / Semester: 1) Algorithms and Data Structures (Course: 1 / Semester: 2) Logic (Course: 1 / Semester: 2) Discrete Mathematics (Course: 1 / Semester: 2) Artificial Intelligence (Course: 2 / Semester: 2)

Objectives

The objective of this course is to familiarize the student with the fundamental techniques of discrete optimization as well as with the fundamental algorithms for solving satisfiability problems.

Skills and learning outcomes

Link to document

¿	Know the main mathematical and computational methods of analysis, formulation and resolution of satisfiability and optimisation problems.
¿	Apply the most appropriate method to solve a given problem using a computer.

Description of contents: programme

1. Dynamic Programming 2. Linear Programming 3. Boolean Satisfiability 4. Constraints Programming 5. Search

Learning activities and methodology

* Theory lectures: 1 ECTS. They are aimed at reaching the specific cognitive competences of the subject as much as analysis and abstraction. * Practical lectures: 1 ECTS. They are thought to reach the specific practical skills as much as problem resolution and knowledge applicability * Continuous evaluation: 1,5 ECTS. They will start during the practical sessions but should be completed as homework. They are expected to complete both the cognitive competences and the practical skills including problem resolution and knowledge applicability * Final practice: 2 ECTS. To be done without the direct assistance of a professor, they are aimed to complete and integrate all the specific competences and skills by solving two practical cases. The statements of these problems, the resolution method, the results obtained and its interpretation shall be well documented. * Tutoring: TUTORING. Individualized assistance (individual tutoring) or group (collective tutoring) to students by the teacher. * Final exam: 0,5 ECTS. It strengths and complements the development of both the specific cognitive and procedural capacities.

Assessment System

% end-of-term-examination 40
% of continuous assessment (assigments, laboratory, practicals...) 60

Calendar of Continuous assessment

EVALUATION SYSTEMS

FINAL EXAM. [40 %]
Global assessment of knowledge, skills and capacities acquired throughout the course.

CONTINUOUS EVALUATION. [60 %]
Assesses papers, projects, class presentations, debates, exercises, internships and workshops throughout the course.

Minimum score in the final exam: 4 (over 10)
Minimum score in the lab assignments: average of 3,5 (over 10) over all lab assignments

Extraordinary call: regulations

Basic Bibliography

Frederick S. Hiller and Gerald J. Lieberman. Introduction to operations research. McGraw-Hill. 2005
Holger Hoos, Thomas Stützle. Stochastic Local Search: Foundations and Applications. Morgan Kaufmann. 2005
Jongen, H. Th.. Optimization Theory. Kluwer Academic. 2004
Rina Dechter. Constraint Processing. Morgan Kaufmann. 2003
Stefan Edelkamp, Stefan Schrödl. Heuristic Search: Theory and Applications. Morgan Kaufmann. 2012
Steven S. Skiena. The Algorithm Design Manual. Springer. 2008
Sundaram, Rangarajan K.. A first course in optimization theory. Cambridge University Press. 2006
Victor W. Marek. Introduction to Mathematics of Solvability. CRC Press. 2009

The course syllabus may change due academic events or other reasons.