Descripción y contextualización de la asignatura

Combinatorial optimization problems are ubiquitous in these days. They appear in the field of engineering, in finance or in science. These problems are characterized for having a finite or countable infinite search space. Examples of these problems are routing, scheduling or packing problems to name a few. Traditional Operations Research has exactly solved these problems by using branch-and-bound type algorithms. However, this kind of algorithms cannot solve medium-large instances due to the computation time required. In fact, most of these problems belong to a class called NP-complete. All the problems in this category share a property: there is not known polynomial algorithm able to solve all possible instances of the problem. Furthermore, if there would be a polynomial algorithm for one instance, then all the problems could be solved in polynomial time. In this topic, our goal is to present heuristics algorithms. These algorithms are characterized for producing good solutions in affordable computation times. Contrary to branch-and-bound algorithms, these methods are not based on strong mathematical roots, however they obtained competitive results in practice.



The relevance of this subject in the context of the master is twofold: on the first hand most of the combinatorial optimization problems that are currently solved in industry or economy make use of this kind of algorithms. Secondly, heuristics are a basic tool for other subjects: for instance most of the models in the field of machine learning or data mining are learnt by the use of heuristics. Similarly, the field of computer vision uses systematically heuristics to carry out, for instance segmentation of images or feature extraction.

Convocatoria ordinaria: orientaciones y renuncia

The student has to carry out a practical work that consists in the solution of a academic combinatorial optimization problem by means of several metaheuristic algorithms. In order to do that, the students, will have to mathematically formalize the problem, design appropriate algorithms and codify them in the computer. In addition they will carry out comparison between the different designed and implemented algorithms.



In a fixed day at the beginning of the course, the student will provide the instructor with a report of the work done together with the source code. Finally the students will do a presentation of the work carried out.

Temario

Tema 1 INTRODUCCIÓN A LA OPTIMIZACIÓN

Tema 2 ALGORITMOS DE BÚSQUEDA LOCAL

Tema 3 ALGORITMOS POBLACIONALES E HÍBRIDOS

Tema 4 OPTIMIZACIÓN MULTIOBJETIVO

Tema 5 EVALUACIÓN DE LA OPTIMIZACIÓN

Bibliografía

Bibliografía básica

1. C.R. Reeves (Ed.), Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publications,1993.



2. A. Díaz (Ed.), Optimización Heurística y Redes Neuronales en Dirección de Operaciones e Ingeniería.Editorial Paraninfo, 1996.



3. P.J.M. Van Laarhoven & E.H.L. Aarts, Simulated Annealing: Theory and Applications. D. Reidel

Publishing Company, Dordretch, Holland, 1987.



4. D. Goldberg, Genetic Algorithm in search, optimization and machine learning. Addison-Wesley, 1989.



5. T. Back, Evolutionary Algorithms in Theory and Practice. Oxford University Press, 1996.



6. F. Glover, M. Laguna, Tabu Search. Kluwer Academic Publishers, 1997.

Bibliografía de profundización

7. M. Laguna, R. Mart¿¿ & V. Campos, Intensification and Diversification with Elite Tabu Search Solutions for the Linear Ordering Problem. Computers and Operations Research 26, pp. 1217-1230, 1999.







8. M. Dorigo, V. Maniezzo & A. Colorni, The Ant System: Optimization by a colony of cooperating



agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 1, pp. 1-13, 1996.







9. M. Laguna and R. Martí, Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers, 2003.







10. P. Larrañaga & Jose A. Lozano (Ed.) Estimation of Distribution Algorithms. Kluwer Academic Publishers, 2002.







11. B. Melián, J.A. Moreno Perez, J. Marcos Moreno-Vega, J.(Ed.) Revista Iberoamericana de Inteligencia Artificial 19, 2, 2003.















12. H.H Hoos, T. Stuztle, Stochastic local search. Foundations and applications. Morgan Kaufmann, 2005.

Revistas

* IEEE Trans. on Evolutionary Computation



* Evolutionary Computation Journal



* Journal of Heuristics



* European Journal of Operations Research



* Computers and Operations Research



* Swarm and Evolutionary Computation

Enlaces

https://en.wikipedia.org/wiki/Metaheuristic