Programme PhD Term V Academic Year 2021-22

Course title Large Scale Optimization Area Production and Quantitative Methods Credits 1.50

Prof. Sachin Jayaswal,
Prof. Goutam Dutta

Course Description & Objectives

Real world optimization problems often tend to be large Integer Program/ Mixed Integer Program (IP/MIP) problems, often to an extent that even the standard IP/MIP solvers, which use Branch & Bound and Branch and Cut algorithms, fail to solve them in reasonable time. In this course, students learn how to take advantage of the often hidden special structures of such problems either by relaxation or by decomposition into relatively easier/smaller problems, which can be solved efficiently using their special structures. The challenge then is how to recover the solution to the original problem from the solution to its relaxation/decomposition. To this end, the course introduces several decomposition techniques, namely, Lagrangian Relaxation, Benders Decomposition, Column Generation, and Dantzig-Wolfe Decomposition methods, Cutting Plane Method, and Generalized Benders for MIPs and Mixed Integer Nonlinear Programs (MINLPs).

Towards the end, the course also introduces Stochastic Optimization. First, we discuss the concept of Multi stage stochastic Programming, and introduce the concept of Value of Stochastic Solution (VSS), Expected value of Perfect Information (EVPI), and Stochastic freeze (SF). Then, we discuss the concept of scenario generation; discuss problems associated with scenario tree; and how we can use it for VaR and CvaR. We discuss two applications, one in finance domain and another in manufacturing.

This is an applied course, and hence its focus is more on understanding and applications of the techniques rather than on formal proofs. The course introduces several practical applications from Hub-and-Spoke Network Design, Facility Location, Telecommunication Network Design, etc.