OPERATIONS RESEARCH

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.