# OPERATIONS RESEARCH

## Learning outcomes of the course unit

The student should be able to execute all the usual steps in an analytical approach to the solution of decision problems, i.e.:

1) building a mathematical model for a real problem;

2) detection of a suitable algorithm for the solution of the model;

3) analysis of the algorithm's output.

## Prerequisites

Basic linear algebra and calculus notions.

## Course contents summary

Introduction to Operations Research: from

the real problem to algorithms

Mathematical models. Basic components and their translation in the mathematical language.

The modeling language AMPL

Mathematical models' examples: flow problems, travelling salesman problem, vehicle routing

Linear Programming (LP). Canonical form. Feasible region and set of optimal solutions.

Properties of the feasible region. Vertices and extreme rays. The representing theorem.

Graphical solution method and the different forms of the set of optimal solutions.

The LP fundamental theorem and its algorithmic implications.

Basic notions for the introduction of the simplex algorithm. Bases and basic solutions. Reduced costs.

The pivot operation. The simplex algorithm's main steps.

Finiteness of the simplex algorithm and comments about its complexity.

Unique and multiple optimal solutions.

Detecting a feasible basis: the two-phase method.

Intger Linear Programming (ILP). Theoretical aspects. Convex hulls.

Totally unimodular matrices. "Simple" ILP problems

Branch-and-bound algorithms.

Cutting plane algorithms

Introduction to complexity. Algorithms' complexity.

Algorithms for the shortest path problem.

Algorithms for the minimum spanning tree problem.

The class P of polynomially solvable problems. Class NP

and NP-complete problems

Polynomial reductions. Instances of NP-complete problems.

Approximation problems. FPTAS, PTAS and inapproximability results.

Approximation algorithm for metric TSP.

FPTAS for the KNAPSACK problem.

Dynamic programming.

Basic components for problems solvable by dynamic programming techniques.

A dynamic programming

algorithm for the KNAPSACK problem.

Nonlinear problems. Local and global optima. Difficulty of the problems. Convex problems.

Unconstrained problems: first- and second-order necessary and sufficient conditions for local optimality.

Unconstrained problems: line search and trust region methods.

Constrained problems. Lagrangian function.

Optimality conditions (KKT conditions). Wolfe's dual.

## Recommended readings

Professor's online published notes.

## Teaching methods

Theoretical and practical lessons.

## Assessment methods and criteria

Written exam with questions about theory.

Solution of a small project at home with final discussion.