Mathematical modeling of combinatorial optimization problems, in the realm of areas such as Biology, Networks, time-dependent processes, resources allocation, game theory, etc. Study of techniques to tackle such problems, as branch and bound, heuristics, probabilistic techniques, linear/convex programming. Exploiting the limitations of these techniques and case study of resent developments. Approximation algorithms, polynomial time approximation schemes. Local search methods, PLS- -completeness, neighborhood structures. Local search methods in the perspective of game theory.

When the student completes the course successfully:

• She will have the knowledge to model as a linear/convex program some of the most important problems of the combinatorial optimization.
• She will have the skills to apply techniques and algorithms that solve linear/convex programs.
• She will have the capability to solve problems of linear/convex programming.

Not required.

Combinatorial optimization: algorithms and complexity. C. Papadimitriou, K. Steiglitz

Combinatorial Optimization: Polyhedra and Efficiency. Schrijver, Alexander

Journal of combinatorial optimization

Work in classroom. Final exams.

Face-to-face