Delayed Column Generation in Large Scale Integer Optimization Problems

Explore delayed column generation techniques for solving large-scale mixed linear integer programming problems in this comprehensive lecture. Delve into the importance of these problems in decision mathematics and data science applications. Learn about algorithms that utilize linear programming approximations and divide-and-conquer approaches like branch-and-bound and branch-and-cut. Understand why the simplex algorithm is preferred for LP subproblems and how delayed column generation overcomes memory constraints in very large-scale problems. Examine the special structure required in IP problems for this approach, often present in big data scenarios. Begin with a brief review of the simplex method and branch-and-bound for general integer programming problems. Then, investigate delayed column generation in the context of the classical cutting stock problem before exploring the branch-and-price method in a general setup. Gain valuable insights into advanced optimization techniques from Professor Raphael Hauser of the Alan Turing Institute in this 2-hour 41-minute lecture.