Method of Column Generation Used in Integer Programming

Models of operation research with discrete variables represent the NP-hard problems. Huge practical applications are unsolvable even with the use of powerful hardware and software. The branch-and-bound method is the general method used for solving problems with discrete variables. However, it is a non-polynomial algorithm. The paper describes methods for making this approach more effective. The principal feature of the methods is to reduce the number of branches during searching the set of feasible solution. Branch-and-price algorithm (column generation) uses Dantzig-Wolfe decomposition of a linear programming problem based on the elimination of some variables, i.e. columns, from the original model. The eliminated columns are progressively added to the model after computing their reduced costs. Re-optimization of the extended model follows.