# Branch-and-Price algorithms for IP/MIP

I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer problems.

Dantzig-Wolfe decomposition for traditional LPs I'm O.K. with.

In general, I've found very little specific information on how B&P works. I have a good book which only explains it briefly across two pages, and I have a book which spends a lot longer on it but is poorly written (and the book actually is littered with errors so I'm hesitant to trust it). I've also found a few lecture notes on the Internet from various university courses.

Across all my readings, I get the overall impression that B&P simply involves using a completely traditional Branch-and-Bound algorithm, with the exception that instead of using a linear relaxation (dropping integrality constraints) to get bounds at each node, we use some sort of decomposition and column generation algorithm instead - typically Dantzig-Wolfe. i.e. Do an ordinary Branch-and-Bound, but instead of solving the linear relaxation, solve the Dantzig-Wolfe decomposed relaxation.

Is this correct? If so, what possible advantage is there for using Dantzig-Wolfe decomposed linear relaxation as opposed to the original problem's linear relaxation? Surely if the LP relaxation of an IP is too large to solve without decomposition, then we can't even hope to solve the original IP to optimality?

I did read somewhere (and I don't remember where), that in many cases the Dantzig-Wolfe decomposed linear relaxation will give a tighter bound on the original IP. If this is true then there would be an advantage in using it as more branches of the decision tree can be dropped, decreasing the total computation necessary to solve the problem.

I was thinking that if the branching occurred on the lambda variables in the reduced master problems rather than the original problem's decision variables, then there would be something unique in Branch-and-Price versus Branch-and-Bound. Actually, very few resources I read mentioned this as an option at all, and one book said that it is possible but often a bad idea as it unbalances the decision tree and it's difficult to prevent that lambda from staying fixed at the 0- or 1-value.

-