Learning objectives
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 unit content
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.
Full programme
- - -
Bibliography
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.
Other information
- - -
