Aim

Operations Research (O.R.) is the branch of applied mathematics dealing with quantitative methods to analyze and solve complex real-world decision-making problems. The course covers some of the fundamental methods of O.R. The focus is on optimization models and algorithms with important applications in computer science, telecommunications and engineering. During the computer laboratory sessions the students will learn to use the AMPL modeling language and state-of-the-art commercial solvers to tackle optimization problems arising in a variety of fields of application.

Detailed program

1. Introduction

Decision-making problems. Main steps of an O.R. study. Different types of optimization (mathematical programming) problems. Optimization models (decision variables, objective function, constraints) and modeling techniques.

2. Graph and network optimization

Algorithms for the optimum spanning tree and shortest path problems (including Dynamic programming for acyclic graphs). Application to project scheduling: critial path method and Gantt diagrams. Maximum flows: Ford-Fulkerson algorithm and maximum flow-minimum cut theorem. Minimum cost flows, matching in bipartite graphs.  

3. Basics of computational complexity

Recognition problems, classes P and NP, NP-complete and NP-hard problems. Traveling salesman problem, Integer Linear Programming and other examples.

4. Linear Programming (LP)

LP models. Geometric aspects (vertices of the feasible region) and algebraic aspects (basic feasible solutions). Fundamental properties of linear programming. The Simplex method. LP duality theory: pair of dual problems, weak and strong duality, complementary slackness conditions. Economical interpretation. Sensitivity analysis. Special cases: assignment and transportation problems.

5. Integer Linear Programming (ILP)

ILP models for, among others, routing, scheduling and location problems. Formulations and linear relaxation. Exact methods: Branch & Bound algorithm and relaxations, cutting plane method with Gomory cuts. 

Time permitting: introduction to heuristic algorithms (greedy and local search).

The examination consists of a written exam and an optional computer laboratory exam.

The written exam, which covers all the material presented in the lectures, exercise and computer laboratory sessions, includes several problems to be solved in class during the allotted time. The maximum grade is 27. The grade remains valid during one academic year (until the September exam session).

The computer laboratory exam is optional and the maximum grade is 4. During each exam session, there will be a single call for the computer laboratory exam.

The final grade is obtained by adding the grades of the written exam and of the computer laboratory exam (if any).

The material will be made available progressively during the semester

First edition: Prentice Hall, 1982