UNIVERSITY OF UDINE

Degree in Mathematics

Course Syllabus

Optimization

a.y. 2000-01

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 (8)

BASICS OF GRAPH THEORY (8)

Fundamentals definitions. Circuits. Cuts. Incidence matrices.

BASICS OF COMPUTATIONAL COMPLEXITY (12)

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

BASICS OF CONVEX ANALYSIS (12)

Definitions. Separation theorem. Supporting planes. Convex functions. Subgradients.

DUALITY (8)

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

MODULE # 2 - First part

(F. Rinaldi)

LINEAR PROGRAMMING (18)

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

NETWORK FLOWS (18)

Optimality conditions: Gamma curve. Residual network. Polynomial algorithms for Shortest Path (Dijkstra) and Max Flow. `Out of kilter' method. Scaling algorithms. Bipartite matching. Network Simplex.

DETERMINISTIC DYNAMIC PROGRAMMING (12)

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

MODULE # 2 - Second part

(P. Serafini)

COMBINATORIAL OPTIMIZATION (20)

Matching problems. Matroids and spanning trees. Polyhedral combinatorics.

INTEGER LINEAR PROGRAMMING (12)

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

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)