Course Title: 
Computational Method for Optimization
Course Code: 
Year Taught: 
Postgraduate (PG)
School of Engineering

'Computational Method for Optimization' is a Soft Core course offered for the M. Tech. in Computer Science and Engineering program at School of Engineering, Amrita Vishwa Vidyapeetham.

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.


  1. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1999.