Programme Algorithms And Models For Discrete Optimization:
AMOD is a master's course on the theory and applications of discrete optimization. After a review of the basic notions of linear programming and the simplex method, integer (and mixed integer) linear programming (MIP) are addressed in more detail together with some references to problems on networks.
MIP methods: Chvatal-Gomory cuts, implicit enumeration methods, branch and bound and combinatorial branch and bound, Dynamic Programming. Linear formulation of a MIP and its quality. Non Compact formulations. Explicit and implicit descriptions of a polyhedron. Column generation methods (pricing problems) and constraint generation (Separation). Examples: Cutting Stock, Shortest (s, t)-path. Relaxation of an integer optimization problem (Lagrangian, surrogate, relaxations etc.) Approximation algorithms: basic notions and algorithms examples for Vertex-Cover and Euclidean TSP. Primal-dual approximation methods: Weighted Vertex-Cover. Randomized algorithms for deterministic discrete optimization. Case study: Facility Location and dual ascent methods. Vehicle Routing: Formulations and Heuristics. Network optimization: min-cost flow problems. Network simplex method.
English
Italiano