Turing data science class: Delayed column generation in large scale integer optimization problems

Speaker: Raphael Hauser (Turing Fellow, University of Oxford)

Date: 9 March 2018

Time: 13:00 – 16:00

Registration: Online registration is required

In the event this class is livestreamed, you will be able to view it on our YouTube page


Mixed linear integer programming problems play an important role in many applications of decision mathematics, including data science. Algorithms typically solve such problems via a sequence of linear programming approximations and a divide-and-conquer approach (branch-and-bound, branch-and-cut). The simplex algorithm is preferred for the solution of the LP subproblems, due to its ability to take previous computations into account in warm-starts of subproblems with additional constraints. For very large scale problems this approach would be limited by memory constraints, but the so-called delayed column generation approach makes it possible to get away with only holding a small part of the problem parameters in memory and generating the required data on the fly. To make this approach viable, the IP problem needs special structure based on partial decoupling of the decision variables, which is often present in big data problems. After a short recap of the simplex method and branch-and-bound for general integer programming problems, we discuss delayed column generation in the context of the classical cutting stock problem, before discussing the branch-and-price method in a general setup.

This is an advanced session