Instructor

Ashutosh Mahajan

Semester

Spring ‘21

Course Difficulty

This course is awesome. The right kind of content, right kind of applications, awesome prof, great teaching style, greatly planned evaluations. The course can be easily navigated just by paying attention in the lectures and solving assignments.

Time Commitment Required

2-3 hrs/week

Grading Policy and Statistics

Grading is absolute. There is a small group project component having about 15% weightage, which is not very rigorous. Easy to score well in exams, and the prof is generous in giving marks.

Attendance Policy

None. Prof doesn’t enforce anything.

Pre-requisites

Some basic knowledge of simplex and basic optimisation techniques is preferred.

Topics Covered in the Course

1. Effective modelling in integer programming: Modelling with integer variables: correct formulations; optimality, relaxation, bounds, search, branch-and-bound; choices in modelling: strong formulations, extended formulations, preprocessing of formulations.

2. Polyhedra and integer programming: Describing polyhedra with extreme points and extreme rays; affine independence, dimensions and faces of polyhedra; facets of polyhedra; projection of polyhedra onto subspaces; the polar of polyhedra; equivalence of separation and optimization for polyhedra; connections between polyhedra and integer programming.

3. Relaxation and decomposition methods for large{scale problems: Lagrangian relaxation and subgradient optimization; Dantzig Wolfe decomposition and column generation; Benders decomposition.

4. Cutting plane methods for unstructured problems: Gomory and Chvatal-Gomory cuts; Integer and mixed-integer rounding; Disjunctive cuts: lift-and-project cuts, split cuts, intersection cuts; the group approach to integer programming.

5. Cutting plane methods for structured problems: Valid inequalities for set packing and 0/1 knapsack problems and their separation; clique and odd-cycle inequalities; cover inequalities; sequential and sequence-independent lifting (with examples in the context of cover inequalities); applications in airline crew scheduling, production lot-sizing, facility location, and network design.

Teaching Style

Awesome prof. Live lectures, with comprehensive notes.

Tutorials/Assignments/Projects

Assignments are of moderate difficulty. Solving them prepares you for the exams. No other preparation is required.

Feedback on Exams

Open notes. Easy to moderate questions. Partially objective, partially subjective.

Motivation for taking this course

The applications. Many optimization problems require integer solutions (you cannot send 123.4 vaccines to a state!). Normal optimization methods may fail in such applications, and we need different techniques to get the optimal value. This course teaches such techniques.

When to take this course?

I took it in my 4th year. I’d recommend taking it in the 4th year, because undergrads generally get exposed to basic optimization in the third year.

Review By: Pruthak Joshi