UNIVERSITY OF UDINE

Degree in Mathematics

Course Syllabus

Optimization

a.y. 2001-02

instructors: Paolo Serafini e Franca Rinaldi

Aims: "Operations Research ... aims to provide rational bases for decision making by seeking to understand and structure complex situations and to use this understanding to predict system behavior and improve system performance. Much of this work is done using analytical and numerical techniques to develop and manipulate mathematical and computer models of organizational systems composed of people, machines, and procedures..."(INFORMS, What is OR/MS?)

Optimization is one of the main theoretical disciplines which provide the analytical tools to Operations Research. In the course the fundamental topics of Optimization will be covered with emphasis on the mathematical and algorithmic properties.

MODULE # 1

(P. Serafini)

INTRODUCTION TO OPTIMIZATION PROBLEMS (4 hours)

BASICS OF COMPUTATIONAL COMPLEXITY (12)

Algorithm complexity. Problem complexity. Class P. Class NP. Trasformations. NP-complete problems .

BASICS OF CONVEX ANALYSIS (6)

Definitions. Separation theorem. Supporting planes. Convex functions.

DUALITY (8)

Dual problem. Optimality Conditions. Examples. Duality and convexity. Differential properties of duality. Duality and sensitivity.

LINEAR PROGRAMMING (18)

Geometric properties. Algebraic properties. Complementarity. Simplex method. Variants of the Simplex method. Interior point methods.

MODULE # 2 - First part

(F. Rinaldi)

NETWORK FLOWS (12)

Optimality conditions: Gamma curve. Residual network. Polynomial algorithms for Shortest Path (Dijkstra) and Max Flow. Network Simplex.

DETERMINISTIC DYNAMIC PROGRAMMING (16)

Optimality principle. Bellman's equation. Bellman-Ford algorithm for general networks. Algorithm for acyclic and layered networks. Floyd-Warshall algorithm. Knapsack problems. Combinatorial problems.

COMBINATORIAL OPTIMIZATION (20)

Matching problems. Matroids and spanning trees. Polyhedral combinatorics.

MODULE # 2 - Second part

(P. Serafini)

INTEGER LINEAR PROGRAMMING (20)

Cutting planes. Branch-and-bound. Branch-and-cut.

HEURISTICS (12)

Local Search. Greedy methods. Disaggregation.

Textbook: Paolo Serafini, Ottimizzazione , Zanichelli, Bologna 2000.

Evaluation: oral examination for each teaching period. The grade of the second module is the average of the grades of the first and second part.

Information on Operations Research and Optimization may be found at INFORMS (Institute for Operations Research and Management Science) or at CIRO (Centro Interuniversitario in Ricerca Operativa)