Branch and price

Branch and price is a method of combinatorial optimization for solving integer linear programming and mixed integer linear programming problems that have very many variables. It is a hybrid of branch and bound and column generation. At each node of the branch and bound search tree it works with a restricted linear programming relaxation that holds only some of the columns, and it adds further columns only when needed, because in a large problem most columns are nonbasic and take the value zero in an optimal solution. A reformulation such as Dantzig-Wolfe decomposition usually produces a master problem, and a pricing problem is solved to find a column with negative reduced cost to enter the restricted master problem. When no column can enter and the solution is still fractional, the method branches. Most implementations are specific to a problem. Typical uses include graph multi-coloring, vehicle routing and the generalized assignment problem. When cutting planes are added the method is called branch price and cut.