Course

Effective modeling in integer programming-Modeling with integer variables: correct formulations, Optimality, relaxation, bounds, search: branch–and–bound, Choices in modeling: strong formulations, extended formulations, Preprocessing of formulations. Relaxation and decomposition methods for large–scale problems-Describing polyhedra with extreme points and extreme rays, Connections between integer programming and polyhedral, Lagrangian relaxation, Subgradient optimization-Applications: traveling salesman problem, facility location problems, generalized assignment problem, Dantzig–Wolfe decomposition, column generation, Applications: generalized assignment and multicommodity flow problems, Benders decomposition, Applications: facility location, network design problems. Cutting plane methods for unstructured problems-Integer and mixed–integer rounding, Gomory cuts, disjunctive cuts. Cutting plane methods for structured problems-Affine independence, dimension and faces of polyhedral Strong valid inequalities, facets, Valid inequalities for set packing and 0–1 knapsack problems and their separation, Sequential lifting, Sequence independent lifting, Applications: airline crew scheduling, production lot–sizing, facility location problems, network design.