Selected Topics in Column Generation I: Discretization — Every Integer Point of a Rational Polyhedron Is a Generating Integer Point Plus an Integer Combination of Integer RaysResearch Paper
Dantzig–Wolfe decomposition and column generation solve large integer programs by replacing a set of "easy" constraints with a description of its feasible points, and then pricing out the points one at a time. For linear programs this rests on the Minkowski–Weyl representation: every point of a polyhedron is a convex combination of its extreme points plus a…