The course is taught in English.
The aim of the course is to provide students with theoretical and operational tools for modeling and solving optimization problems in information and communication engineering.
The optimization provides powerful mathematical methods (mathematical models, algorithms, and software) for solving complex problems involving the minimization (or maximization) of objective functions, subject to appropriate constraints.
Starting from real-life problems, such as the design of computer or telecommunication networks, data base management, and network flows, the theory and algorithms for solving the optimization problems which underlie those problems will be studied. Particular attention will be paid to the problem computational complexity and the required solution methods.

Expected knowledge:
Students will study methods and algorithms for solving constrained optimization problems. They will learn how to use linear continuous and integer programming and develop the most suitable solution method to solve the problem. Particular attention will be given to graph problems such as the min cost flow problem and the max flow problem. The computational complexity of optimization problems, which affects the choice of suitable solving algorithms, will be studied. The considered solution methods are both exact (Branch and Bound, Dynamic Programming, and Branch and Cut) and approximated (heuristics and metaheuristics).

Expected skills:
The skills developed by students will consist of the construction of mathematical models and related algorithms for solving optimization problems of information and communication engineering, such as flows on networks, network design, location, scheduling, and routing.

Prerequisites - Students must know at least one of the following programming languages: C, C++, and Java.
The only prior knowledge are those already acquired in the first years courses.

1. Linear programming: modeling techniques, basic concepts of the Simplex method (10% of the course).
2. Computational complexity: problem classes P, NP, NP-complete, and CoNP-complete (10% of the course).
3. Exact optimization methods: Branch and Bound, Dynamic Programming, and Branch and Cut (25% of the course).
4. Heuristic Optimization methods: greedy algorithms, GRASP, Beam Search, meta-heuristics (Tabu Search, Simulated Annealing, Genetic Algorithms, ACO, VNS, RBS), and math-heuristics (45% of the course).
5. Network flow problems: min cost flow and max flow (10% of the course).

The course integrates teaching hours and hours of practice, to the extent of about 60% and 40% of the course, respectively. The exercises are carried out in the classroom and follow the lecture topics. In the laboratory LADISPE http://www.ladispe.polito.it/ up-to-date optimization solvers to solve real-size problems are available to the students. Instructions for their use will be provided in the classroom.
Students are requested to form groups and prepare an assignment during the course. The assignment consists in developing a heuristic and related software (in C, C++, or preferably in Java) for solving a given optimization problem. The assignment results will be presented by each group to the whole class at the end of the course. Student who belong to the same group may work together using long distance communication tools (i.e. Skype, email etc.), so that also long distance students can prepare the assignment. Moreover, it is not necessary that the final presentation of the assignment results is given by the whole group.

R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010.
R. Tadei, F. Della Croce, A. Grosso, Fondamenti di Ottimizzazione, Progetto Leonardo, Editrice Esculapio, Bologna, 2005.
M. Ghirardi, A. Grosso, G. Perboli, Esercizi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009.
R.K. Ahuja et al., Network Flows, Prentice Hall, New Jersey, 1993.
D. J. Luenberger, Linear and Nonlinear Programming, Springer, 3rd ed., 2008.
G.L. Nemhauser, L.A. Wolsey, Integer Programming, Wiley, 1998.
Other learning material and examples of previous exams will be available on the course website.

The assessment is composed by two parts: the written test (2/3 of the final grade) and the assignment (1/3 of the final grade).
The written test is composed by three to four questions related both to the theory and the practice of the course.
The assignment, which consists in developing a heuristic and related software (in C, C++, or preferably in Java) for solving a given optimization problem, will be developed during the whole course and the results, obtained by the students organized in groups, will be discussed and evaluated at the end of the course.