Talk on Polyhedral Theory at LSO Advanced School 2026, IIT Roorkee
I gave a talk on Polyhedral Theory for Integer Programming on the opening day of the LSO Advanced School 2026 at IIT Roorkee (Sept 30 – Oct 4, 2026). This is the first in a new series of schools on advanced topics in large-scale optimization, following the introductory LSO Summer Schools. This edition focused on cutting planes and column generation.
The talk covered:
- Polyhedra as feasible sets of LPs and IPs, and the convex hull of integer points
- When the convex hull of integer points is a polyhedron: Meyer’s theorem and the role of rationality
- The resolution and Minkowski–Weyl theorems
- Comparing formulations by strength, and dominant and redundant valid inequalities
- Dimension, faces and facets of polyhedra, and why facets are necessary
- Proving a formulation gives the convex hull, via total unimodularity and total dual integrality
- Proving an inequality is facet-defining, with minimal cover inequalities for the binary knapsack set as the running example
It closed with a question on lifting minimal cover inequalities, which led into the sessions on valid inequalities and branch-and-cut that followed the next day. Kudos to the enthusiastic students and to Profs. Yogesh Agarwal, Sachin Jayaswal and Faiz Hamid, who stayed late into the evening and enjoyed discussing the definitions and theorems during the talk. Special thanks to Profs. Sumit Kumar Yadav and Manu Gupta and their team for the fantastic organization of the Advanced LSO School. ![]()