We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of nonbasic variables to generate new columns or to prove LP optimality at a node of the branchand-bound tree. We present classes of models for which this approach decomposes the problem, provides tighter LP relaxations, and eliminates symmetry. W e then discuss computational issues and implementation of column generation, branch-andbound algorithms, including special branching rules and e cient w ays to solve the LP relaxation. We also discuss the relationship with Lagrangian duality.
To solve integer programs with a huge number of variables, the present work use a Branch-and-Price (BnP) REF algorithm that combines Branch-and-bound with Column Generation.
Branch-and-price: Column generation for solving huge integer programs
Oper. Res
Computer Science Mathematics