Portale di Ateneo - En.Unibs.it

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-phase algorithm.
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 with Gomory cuts. 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. Assignment problem. Transportation problem.
Minimum cost path problem (applications, properties, Dijkstra's algorithm).
Minimal spanning tree problem (applications, properties, Kruskal's algorithm).
Traveling salesman problem (mathematical formulations, properties).

5) Use of dedicated software MPL/CPLEX for the solution of LP and ILP problems. Results interpretation and sensitivity analysis.