This course is an introduction to linear and linear integer optimization. It
is designed to provide students with modeling tools and solution
techniques (including exact and heuristic solution algorithms). The use of
optimization software is also provided.
Linear Programming theory including simplex method, post-optimality
analysis, dual theory, sensitivity analysis. Linear Integer Programming
theory including models formulation, exact solution algorithms (branch
and bound, cutting planes), heuristic approaches (local search, greedy
methods, approximation algorithms). Applications to engineering and
economic problems. Introduction to Graph Theory (minimum spanning
tree problem, minimum path problems). Introduction to the
Computational Complexity Theory.
1) Decisional processes and optimization models:
Decisional process main features. Models and algorithms, models
selection. Optimization models.
2) Linear Programming (LP):
Formulation and properties of an LP problem. Geometry of the Linear
Programming. Fundamental Theorem of LP and the equivalence
theorem. Solution of the LP problems: graphical solution, simplex
method, two pahses method. Dual theory and primal-dual relationships.
Dual simplex method. Sensitivity analysis (objective function coefficients
and right hand sides). Dual theory and sensitivity analysis. Examples of
applications.
3) Integer Linear Programming (PLI):
Properties and connections to LP. Mixed integer linear programming.
Exact solution methods: branch and bound, cutting planes con taglio di
Gomory. Heuristic solution algorithms and introduction to approximation
algorithms. Application examples.
Introduction to computational complexity theory.
4) Graph Optimization
Definitions and properties of graphs. Incidence and adiacence matrices. Definition and properties of total unimodular matrices (TUM). Polynomial
problems on graphs. Introduction to network flow problems. Assignement
problem. transportation problem. Minimum cost path problem
(application, properties, Dijkstra's algorithm). Maximum flow problem.
Minimal spanning tree problem (application, properties, Prim's algorithm,
Kruskal's algorithm). Traveling salesman problem. Properties and an
approximation algorithm (Tree algorithm).
5) Use of dedicated software MPL/CPLEX for the solution of LP and ILP
problems. Results interpretation and sensitivity analysis.
Matteo Fischetti, Lezioni di Ricerca Operativa, Edizioni Libreria Progetto,
Padova, 1995.
Frederick S. Hillier, Gerald J. Lieberman, Ricerca Operativa - Fondamenti
9/ed, Franco Angeli 2010.
Lectures and exercises. The use in class of specialized software for the
solution of Mixed Integer Linear Programming problems.
Written examination divided in theoretical demands and exercises. Oral
examination including a test on the use of the software presented in
class.
Slides of the course will be available on the E-learnig site.