Management Engineering

On successful completion of this course, the student should be able to: Recognize the basic features of a combinatorial optimization problem with linear objective function belonging to the wide class of Maximum Weight Independent Set Problems (MWIS) (matching, stable-set, knapsack, spanning forests, spanning connected graph etc.); Construct effective linear formulations (polyhedra) for MWIS problems (Rank Formulation, Circuit Formulation) and compute effective bounds with the Dynamic Simplex Algorithm to be used in the framework of Branch&Bound algorithm; Recognize an Independent System which is a Matroid and prove that the well known "greedy algorithm" always find an optimal solution for the MWIS problem if the Independence System is a Matroid. Compute heuristic solution with guaranteed approximation by means of a Primal-Dual Approximation Algorithm proposed by Goemans and Williamson; Compute effective bounds with the Lagrangean Relaxation Method and compute the Lagrangean Dual solution with the "cutting plane method" and the "subgradient method"; Solve applied problems by making a combined use of the tools described above (bounds, approximate solutions, linear formulations etc.). Among them: designing the optimal crew-scheduling in airlines; designing a path of minimum cost with "transit time" constraint etc. Have a complete understanding of a a real life problem solvable with the above tools. This year: Design of an Optimal Network by means of a "Branch&Cut" algorithm based on the SemiMetric Formulation of the Network Loading Problem;