Back close

Course Detail

Course Name Computational Method for Optimization
Course Code 18CS626
Credits Coimbatore
Year Taught 2018


Course Syllabus

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.

Text Books

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


‘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.

DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.

Admissions Apply Now