Delayed column generation in large scale integer optimization problems - Professor Raphael Hauser

Описание: 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.