Course Details for A.Y. 2011/2012

Course Content

• Formulations of Integer and Binary Programs: The Assignment Problem; Set Covering, Packing and Partitioning; Minimum Spanning Tree; Traveling Salesperson Problem (TSP); Formulations of logical conditions
• Mixed Integer Formulations: Modeling Fixed Costs; Uncapacitated Facility Location; Uncapacitated Lot Sizing; Discrete Alternatives
• Geometry of R^n: Linear and affine spaces; Polyhedra: dimension, representations, valid inequalities, faces, vertices and facets; Alternative (extended) formulations; Good and Ideal formulations
• Optimality, Relaxation and Bounds
• LP based branch-and-bound algorithm: Preprocessing, Branching strategies, Node and variable selection strategies, Primal heuristics; Software tools
• Cutting plane algorithm and branch-and-cut algorithm: Chvatal-Gomory cuts: definition and separation procedure; Gomory's fractional cutting plane algorithm; Strong valid inequalities: Clique inequalities for the maximum stable set problem, Subtour inequalities for the TSP, Cover inequalities for the 0-1 knapsack problem; Strengthening valid inequalities: the lifting procedure; Branch-and-cut algorithm
• Lagrangian Duality: Lagrangian relaxation; Lagrangian heuristics
• MIP-Based Heuristics: Dive-and-Fix, Relax-and-Fix, Cut-and-Fix; Local branching, feasibility pump, RINS
• Applications: telecommunication problems: Frequency assignment problem; Network design; Multicommodity flow; Spanning trees with side constraints

Textbooks

• L.A. Wolsey, Integer Programming , Wiley. 1998.    

Internet Resources

Course page updates

• A.Y. 2010/2011
• A.Y. 2011/2012
• A.Y. 2012/2013
• A.Y. 2013/2014
• A.Y. 2014/2015
• A.Y. 2015/2016
• A.Y. 2016/2017
• A.Y. 2017/2018
• A.Y. 2018/2019