The notes are taken from the books required for the course:

• Course slides.

📚 Course Syllabus

According to the official course syllabus:

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.
   • An example of NP-hard network optimization problems: the Traveling salesman problem.
3. 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.
4. Integer Linear Programming (ILP)
   • ILP models for, among others, transportation, routing, scheduling and location problems.
   • Formulations and linear programming relaxation.
   • Exact methods: Branch-and-Bound algorithm, cutting plane method with fractional Gomory cuts.

Time permitting we will provide/review some basics of computational complexity (recognition problems, classes P and NP, polynomial-time reductions, NP-complete and NP-hard problems) and introduce basic heuristic algorithms (greedy and local search).

A couple of topics will be assigned for independent study (e.g. LP sensitivity analysis) prior to sessions devoted to exercises or computer laboratory activities. There will be computer lab meetings and computer lab assignments.

💾 Download

You can view an embedded PDF version here:

https://raw.githubusercontent.com/PoliMI-HPC-E-notes-projects-AndreVale69/HPC-E-PoliMI-university-notes/main/foundations-of-operations-research/notes/foundations-of-operations-research.pdf

Or you can download it directly here: