UNIVERSITY OF UDINE

Degree in Computer Science

Course Syllabus

Operations Research

a.y. 1997-98

instr. Paolo Serafini

Aim: 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 the Lingo package.

1) INTRODUCTION TO LINEAR PROGRAMMING (12 hours)

Diet problem: Identification of objectives and constraints. Modeling as LP. Properties of LP. Sensitivity analysis. Generation of Pareto optima for the continuous poblem. Use of integer variables. Characterization of integer LP. New Pareto optima. Identification of new objectives. Extensions of the model.

Product mix problems. Assignment and Transportation models.

2) LINEAR PROGRAMMING PROPERTIES (6)

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

3) NETWORK FLOW MODELS (6)

Assignment. Transportation. Shortest Path. Max Flow. Network LP. Case studies.

4) COMBINATORIAL OPTIMIZATION MODELS (12)

Matching: LP relaxed model, cutting plane generation (`odd subsets'). TSP: relaxed model, cutting plane generation(`subtour elimination'). 3D assignment. Case studies. Set Packing, Covering and Partitioning models. Case studies. Cutting stock models. Column generation LP. Minimal spanning tree.

5) DETERMINISTIC DYNAMIC PROGRAMMING MODELS (4)

Optimality Principle. Recursive equation. Shortest paths (Floyd-Warshall). Knapsack problems. Other combinatorial examples.

6) STOCHASTIC DYNAMIC PROGRAMMING MODELS (4)

Markov chains. Finite horizon Markovian decision processes. Infinite horizon discounted Markovian decision processes. Policy evaluation. Optimum computation. Infinite horizon average gain Markovian decision processes. Linear Programming.

7) DECISION MODELS UNDER UNCERTAINTY (4)

Stochastic LP. Decision Trees. Utility function. Lotteries. Subjective probability. Bayesian techniques.

8) GAME THEORY (4)

Zero sum games. Extended and normal form. Equilibria. Pure and mixed strategies. Non zero sum games. Nash Equilibria. n-person games. Imputations. Shapley value.