branchandprice

Branch-and-price is a branch-and-bound algorithm that integrates column generation to solve large-scale integer programming problems. It is especially effective for problems that can be formulated as set partitioning or set covering with an enormous number of potential columns, such as configurations, routes, or patterns.

Instead of solving the full problem with all variables, branch-and-price iteratively solves a restricted master problem (RMP) consisting of a manageable subset of columns. The dual values from the RMP are used to drive a pricing subproblem, whose goal is to produce new columns with negative reduced cost. If the pricing subproblem cannot find any improving column, the current LP solution is optimal for the RMP; if the solution is integral, it is feasible for the original problem and optimal. Otherwise, branching is performed to enforce integrality, generating new subproblems with additional constraints or by branching on decision variables or on the structure of the pricing subproblem.

Common pricing subproblem forms include shortest-path problems with resource constraints, knapsack-type problems, or other domain-specific subproblems. The master problem usually takes a set-partitioning structure, where each column represents a feasible configuration such as a route or a schedule, and the objective is to cover or partition items exactly while minimizing cost.

Branch-and-price has been used for large-scale problems such as vehicle routing with time windows, crew scheduling, and cutting stock. It is related to branch-and-cut, which integrates cutting planes into the branch-and-bound framework, and to column generation more generally.