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 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.