Course program
1. Introduction
2. Mathematical Programming
- Optimization Problems.
- Fundamental definitions.
- Classification of optimization problems.
- Mathematical Programming Models.
3. Linear Programming Models
- Generality. Structure of a Linear Programming model.
- Examples
4. Linear Programming
- Structure of a Linear Programming problem.
- Geometric interpretation of a Linear Programming Problem.
5. Linear Programming Theory
- Review of geometry. Convex sets. Vertices.
- Characterization and existence of the vertices of the feasible set of a Linear Programming problem.
- The Fundamental Theorem of Linear Programming.
6. The simplex method.
- The standard form and the feasible canonical form.
- Vertices and basic solutions.
- Phase II of the simplex method. Optimality criterion. Criterion of limitlessness.
- Convergence of the simplex method.
- Phase I of the simplex method.
7. Duality theory for Linear Programming
- Construction of the dual problem of a linear programming problem.
- Duality in weak form and sufficient condition of optimality.
- Duality in strong form and conditions of orthogonality.
8. Integer Linear Programming Models
- Integer variables to represent indivisible quantities.
- Binary variables to represent alternative choices.
- Binary variables such as indicator variables and logical relationships.
- Examples
9. Integer Linear Programming
- Relations between Integer Linear Programming and Linear Programming.
- Linear relaxations of Integer Linear Programming problems.
10. General methods for the solution of Integer Linear Programming problems
- The Branch and Bound technique.
- Examples.
11. Integer network flow problems
- Examples
- Formulation of the minimum cost integer flow problem
- Total unimodularity and integrality property
- Capacitated version
- Network Simplex
12. Local search algorithms
- Design of a local search algorithm
- Definitions of neighborhoods of a point in the discrete case
- Techniques to avoid bad quality local optimal solutions: multistart and local worsening
- General descent algorithm
- Traveling salesman problem and Lin and Kernighan algorithm
13. A glimpe on multi-objective programming
- Formulation of a multiobjective LP problem
- Efficient solutions and Pareto frontier
- Graphic resolution
- Weighted sum method and ε-constraint method
Prerequisites
Fundamentals of linear algebra, analytical geometry and mathematical analysis.
Books
All the slides taught in class and lecture notes can be found on the moodle webpage of the course "Ricerca Operativa"
Frequency
Attendance not mandatory but strongly encouraged.
Exam mode
To pass the exam, students must complete: (a) a written test with 4 exercises and 2 questions related to theoretical results and definitions introduced in the course (duration: 2 hours).
This test allows to verify both the acquisition of theoretical concepts and the ability to solve practical problems.
