On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm

Dantzig-Wolfe decomposition as applied to an integer program is a specific form of problem reformulation that aims at providing a tighter linear progr amming relaxation bound. The reformulation gives rise to an integer master problem, whose typically large number of variables is dealt with implicitly by using an integer programming column generation procedure, also known as branch-and-price algorithm, There is a large class of integer programs tha t are well suited for this solution technique. In this paper, we propose to base the Dantzig-Wolfe decomposition of an integer program on the discreti zation of the integer polyhedron associated with a subsystem of constraints (as opposed to its convexification). This allows us to formulate the integ rality restriction directly on the master variables and sets a theoretical framework for dealing with specific issues such as branching or the introdu ction of cutting planes in the master. We discuss specific branching scheme s and their effect on the structure of the column generation subproblem. We give theoretical bounds on the complexity of the separation process and th e extent of the modifications to the column generation subproblem. Our comp utational tests on the cutting stock problem and a generalisation-the cutti ng strip problem-show that, in practice, all fractional solutions can be el iminated using branching rules that preserve the tractability of the subpro blem, but there is a trade-off between branching efficiency and subproblem tractability.