Optimization

Code	14794
Year	3
Semester	S1
ECTS Credits	6
Workload	TP(60H)
Scientific area	Mathematics
Entry requirements	NA
Learning outcomes	1) Distinguish basic concepts of Graph Theory; 2) Formulate problems in Integer Linear Programming; 3) Find upper and lower bounds for unknown optimal values; 4) Differentiate Network Optimization problems; 5) Formulate problems as networks; 6) Apply and distinguish Network Optimization algorithms; 7) Differentiate Combinatorial Optimization problems; 8) Apply and differentiate heuristics for Combinatorial Optimization problems.
Syllabus	I. Introduction a) Graphs and Networks: basic concepts b) Integer Linear Programming Formulations c) Linear Relaxation vs Heuristics II. Network Optimization a) Shortest Path Problem i. Definition and formulation ii. Optimality conditions iii. Temporary and definitive labelling algorithms iv. Applications b) Maximum Flow Problem i. Definition and formulation ii. Optimality conditions iii. Minimum cut/maximum flow theorem iv. Ford-Fulkerson algorithm v. Particular cases vi. Applications c) Minimum-cost Flow Problem i. Definition and formulation ii. Simplex Algorithm iii. Particular cases iv. Applications III.Combinatorial Optimization a) Knapsack Problem i. Definition and formulation ii. Variants and heuristics iii. Applications b) Travelling Salesman Problem and Chinese Postman Problem i. Definitions and formulations ii. Heuristics iii. Applications c) Covering-Packing Problems, Districting Problem and Location Problem i. Definitions and formulations ii. Heuristics iii. Application
Main Bibliography	- Ahuja, R., Magnanti, T., Orlin, J. (1993). Network Flows: Theory, Algorithms, and Applications. Pearson. - Bazaraa, M., Jarvis, J., Sherali, H. (2010). Linear Programming and Network Flows. Wiley. - Lawler, E. (1976, 2011). Combinatorial Optimization: Networks and Matroids. Dover. - Papadimitriou, C., Steiglitz, K. (1998). Combinatorial optimization: algorithms and complexity. Dover. - Wolsey, L. (1998). Integer Programming. Wiley.
Language	Portuguese. Tutorial support is available in English.