I'm sure this is a straightforward question, but since I started learning integer programming recently this isn't clear to me.
Consider solving a 1 dimensional cutting stock problem using delayed column generation / branch and price. You start by considering possible combinations of trivial patterns and through checking reduced costs and REPLACING columns, you eventually deduce an optimal solution for the LP relaxation with fractional numbers of rolls.
I have seen 3 resources online, all of which say something to the effect of:
The correct thing to do would be to apply Branch and Bound to the LP-optimal solution, but ...
and then proceed to use a rounding / observation argument.
My question is, how do we apply branch and bound?
Say we are in a 'nice' situation where we have found the LP-optimal solution with a square matrix and column vector where the column vector is positive and fractional. Do we simply choose a fractional entry of the vector and split into the two natural cases?
An example that I have been practising with is:
We have access to rolls of length 20. Minimise the number of rolls required for 301 length-9 rolls, 401 length-8 rolls, 201 length-7 rolls, and 501 length-6 rolls.
I start with A0=[2e1,2e2,2e3,3e4] and solve min and replace columns twice to obtain A_2= \begin{pmatrix} 2&0&0&0\\ 0&2&0&1\\ 0&0&2&0\\ 0&0&1&2 \end{pmatrix} \text{} x_2=\begin{pmatrix} 150.5\\100.375\\100.5\\200.25\end{pmatrix} as an optimal solution after checking all dual constraints are satisfied.
So how exactly do I proceed from this stage in a Branch and Bound fashion?
Say we branch into the 2 cases with the first variable \leqslant 150 and \geqslant 151.
From my understanding, the first case means we add an extra constraint to the problem and hence an extra slack variable giving the system \begin{pmatrix} 2&0&0&0&0\\ 0&2&0&1&0\\ 0&0&2&0&0\\ 0&0&1&2&0\\ 1&0&0&0&1 \end{pmatrix} x = \begin{pmatrix}301\\401\\201\\501\\150 \end{pmatrix} however it's clear this can't be right since the exact solution in this case still gives the first variable as 301/2>150 and the slack variable is negative. Or even just noting that only column 1 contributes to the 301 orders of length-9 rolls so we certainly can't solve the problem with these patterns in this case.
I'm unsure if I should classify this case as infeasible since it's probably just because I don't have the right columns generated (assuming I've done this correctly in the first place...).