Programme

PhD

Term

IV

Academic Year

2021-22

Course title

Mathematical Modelling for Integer Program & Theory of Valid Inequalities

Area

Production and Quantitative Methods

Credits

1.25

Instructor(s)

Prof. Sachin Jayaswal

Course Description & Objectives

Description: Mathematically modeling a problem is as much an art as it is a science, and there may be more than one way of modeling the same problem. While computationally, there may not be much difference between alternate models of the same problem when dealing with only continuous variables, the same is no longer true when dealing with integer/binary variables. While dealing with integer programs (IPs)/mixed integer programs (MIPs), one formulation may be far more efficient than the others, depending on how closely their constraints approximate the Convex Hull of the set of integer feasible solutions. For certain classes of problems involving integer/binary variables (for example, shortest path problem, min cost network flow problem, min-cut problem, matching problem, etc.), there exist Perfect Formulations, which completely characterize the Convex Hull of the integer feasible solutions, and hence can be solved very efficiently simply as Linear Programs (LPs). For other classes of problems, where Perfect Formulations are not known, it is desirable to have a formulation that can approximate the Convex Hull as closely as possible or have facet defining constraints. To that extent, modelling in IPs/MIPs becomes more of science than art, and one needs to have a good understanding of Polyhedral Theory. The objective of the course is to train the participants to develop IP/MIP models, to understand the differences between alternate model choices, and to be able to identify one that is computationally more efficient. To achieve the above stated objective, each session will typically take up an interesting modelling exercise, and try to come up with alternate formulations, if possible. To be able to appreciate the computational differences among alternate formulations, participants will be trained in the use of a AMPL (A Mathematical Modeling Language) for modeling and solving large problems arising in real world.