Course: 2020/2021

Heuristics and Optimization

(15976)

Students are expected to have completed

Programming, Algorithms and Data Structures, Logic, Discrete Mathematics and Artificial Intelligence

ObjectivesFurther information on this link

* Generic competences
o Analysis (POs a)
o Abstraction (POs a)
o Problem solving (POs a, b, e)
o Application of methods to real-world problems (POs a, b, d, e, g, h)
o CGB1: Capacity for solving numerical engineering problems. Ability to apply knowledge from different fields such as linear algebra, diferential and integral calculus, numerical methods, statistics and optimization.
o CGB3: Capacity for understanding and managing the basic principles of discrete mathematics, logic, algorithms and computational complexity and its application for effectively solving engineering problems.
* Specific competences
o Cognitive
+ Introduction to the main mathematical concepts for the analysis, representation and resolution of optimization problems. (POs a, b, h, j)
+ Introduction to heuristic techniques and approximate solutions for solving problems of high complexity (POs e, h, j)
o Procedural
+ Ability to identify and apply the best suited optimization procedure to a particular problem. (POs a, e, g, h)
+ Ability to use specific computer software to solve optimization problems (POs b, e, h)
o Behavioural
+ Ability to foster new ideas (creativity). (POs d, e, g)
+ Ability to dimensionate new problems (POs b, d)
+ To boost the interest for researching and finding solutions to new and challenging problems. (POs e, g, j, k)
o CECRI6. Knowledge and applicabilty of the basic algorithmic principles in computer science technologies to design effective solutions and to analyze the suitability and complexity of the algorithms proposed
o CECRI15. Knowledge and applicability of the fundamental principles and techniques based on intelligent systems for their practical implementation.

Description of contents: programme

1. Dynamic Programming
2. Linear Programming
3. Boolean Satisfiability
4. Constraints Programming
5. Search
6. Stochastic Local 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.
* 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 30
- % of continuous assessment (assigments, laboratory, practicals...) 70

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