Branch and price

The approach is based on the observation that for large problems most columns will be nonbasic and have their corresponding variable equal to zero in any optimal solution.

But, the decomposition usually contains many variables and so a modified version, called the Restricted Master Problem, that only considers a subset of the columns is solved.

Note that the pricing problem itself may be difficult to solve but since it is not necessary to find the column with the most negative reduced cost, heuristic and local search methods can be used.

Each time a column is found with negative reduced cost, it is added to the Restricted Master Problem and the relaxation is reoptimized.

[5] The branch and price method can be used to solve problems in a variety of application areas, including:

Outline of branch and price algorithm. Adapted from [ 1 ]
Graph of a strictly concave quadratic function with unique maximum.
Optimization computes maxima and minima.