UNIVERSITY of UDINE

Degree in Computer Science

Syllabus of the course on

Opeations Research

a.y. 2000-2001

instructor: Paolo Serafini

Aims:Operations Research deals with efficient management problems via a mathematical and algorithmic approach. The course will focus on the modeling approach rather than stressing abstract mathematical and algorithmic techniques. Several examples will be provided which will motivate the theory. All models will be solved by using Linear Programming packages.

1) INTRODUCTION TO LINEAR PROGRAMMING (6 hours)

General modelling issues: constraint identification, soft and hard constraints; objective identification; objectives and constraints. Explicit objectives: Pareto optima. Example of the diet problem: modelling via linear programming and resolution with a package. Sensitivity analysis. Identification od further objectives Efficient frontier identification Integrality constraints. Model refinement.

2) LINEAR PROGRAMMING PROPERTIES (6 ore)

Geometric structure. Vertices and basis solutions. Dual problem. Complementarity. Overview of simplex method. Overview of branch and bound methods for integer variables.

3) ROUTING MODELS (14)

Shortest paths (Dijkstra algorithm) and longest paths. Dynamic programming. Opitmality principle. Recursive equation. Shortest paths (Floyd- Warshall). Travelling salesman problem (cutting plane formulation). Eulerian circuits. Matching. Minimal spanning trees(Kruskal and Prim algorithms). Network flow problems Min cost flows Max Flow Trasporto.

4) ALLOCATION MODELS (12)

Assignment. Tridimensional assignment . Knapsack. Bin packing. Staffing models. LP with column generation: cutting stock, max flow, crew scheduling.

5) SCHEDULING (12)

Infinite resource scheduling: PERT. Finite resource scheduling: one machine problems, parallel machine problems, flow-shop, job-shop and open-shop.

Main textbook references:

Paolo Serafini, Ottimizzazione , Zanichelli, Bologna 2000.

L. Schrage, LINDO: An optimization modeling system, Palo Alto Scientific Press, 1991;

Exam: Oral examination. Students willing to develop a medium size project are advised to enroll in the course "Laboratorio di Ricerca Operativa"

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)