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 a wide range of important applications in engineering and management science. 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

Optimum spanning trees. Shortest path problems: algorithms for the main variants (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. Economic 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 programming relaxation. Exact methods: Branch & Bound algorithm, cutting plane method with fractional Gomory cuts. 

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

The examination consists of a written exam and computer laboratory tests.

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 computer laboratory tests, which will be scheduled during the semester, aim to evaluate the ability of the students to solve assigned decision-making problems with the modeling language and optimization solver used in the laboratory sessions (AMPL and CPLEX).

The final grade is obtained by adding the grade of the written exam and the points obtained in the computer laboratory tests.

The material will be made available progressively during the semester

First edition: Prentice Hall, 1982