Branch-and-price: Column generation for solving huge integer programs
C Barnhart, EL Johnson, GL Nemhauser… - Operations …, 1998 - pubsonline.informs.org
C Barnhart, EL Johnson, GL Nemhauser, MWP Savelsbergh, PH Vance
Operations research, 1998•pubsonline.informs.orgWe discuss formulations of integer programs with a huge number of variables and their
solution by column generation methods, ie, implicit pricing of nonbasic variables to generate
new columns or to prove LP optimality at a node of the branch-and-bound tree. We present
classes of models for which this approach decomposes the problem, provides tighter LP
relaxations, and eliminates symmetry. We then discuss computational issues and
implementation of column generation, branch-and-bound algorithms, including special …
solution by column generation methods, ie, implicit pricing of nonbasic variables to generate
new columns or to prove LP optimality at a node of the branch-and-bound tree. We present
classes of models for which this approach decomposes the problem, provides tighter LP
relaxations, and eliminates symmetry. We then discuss computational issues and
implementation of column generation, branch-and-bound algorithms, including special …
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 branch-and-bound tree. We present classes of models for which this approach decomposes the problem, provides tighter LP relaxations, and eliminates symmetry. We then discuss computational issues and implementation of column generation, branch-and-bound algorithms, including special branching rules and efficient ways to solve the LP relaxation. We also discuss the relationship with Lagrangian duality.