UNIVERSITY OF UDINE

Degree in Mathematics

Course Syllabus

Optimization

a.y. 1998-99

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)

BASICS OF GRAPH THEORY (4)

Fundamentals definitions. Circuits. Cuts. Incidence matrices.

BASICS OF COMPUTATIONAL COMPLEXITY (8)

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

BASICS OF CONVEX ANALYSIS (6)

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

DUALITY (14)

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.

INTEGER LINEAR PROGRAMMING (4)

Branch-and-bound. Lower bounds. Examples.

MODULE # 2

(F. Rinaldi)

COMBINATORIAL OPTIMIZATION (20)

Cutting planes. Branch-and-cut. Matroids and spanning trees. Matching problems. Polyhedral combinatorics.

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.

APPROXIMATE ALGORITHMS (16)

Definitions. Polynomial approximation schemes. Algoritmhs for Delta-TSP, Knapsack and Bin packing.

Evaluation:

The student may choose to be evaluated in one of the two alternative ways: an oral examination or (recommended procedure) a certain number of homeworks.

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)