# Branch and Price algorithm is exact?

I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver the exact solution when integer variables come into the problem and we have actually MILP? Does Branch and Price algorithm deliver the exact solution? What extra must I do in implementing dual optimization problems (subproblems of the algorithm) when there are integer variables?

To answer your question, it is good to have in mind the following concepts:

1. Dantzig-Wolfe decomposition : in essence, this is a change of variables. The initial variables are expressed as a convex combination of the extreme points of the polygon defined by the constraints of the problem.

2. Column generation : once this change of variables has been done, you are often left with a problem with an exponential number of variables and typically you cannot solve it as is. This is where column generation comes in: variables of this huge problem are dynamically created. Once you have generated all of your "good" columns, you have everything you need to solve your continuous problem. If the problem has integer variables, typically the continuous relaxation of the problem will not yield integer variables.

3. Branch-and-price : after doing your column generation, you typically have a fractional solution, so you have to embed this procedure in a branch-and-bound tree. Branch-and-price refers to this branching tree, where at every node, a column generation algorithm is used to compute the continuous solution.