# How do we branch a Cutting Stock problem using Branch and Price?

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 $$A_0=[2e_1,2e_2,2e_3,3e_4]$$ and solve $$\min_x \sum_1^4 x_j \text{ subject to } A_0x=b=[301,401,201,501]^\text{T}$$ 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...).

• I don't think this is such a straightforward question as you assume. Nov 17, 2022 at 18:20
• At each tree node, you need to exclude any existing columns that violate the branching and generate new columns that respect the branching. Nov 17, 2022 at 19:03
• @RobPratt Is there a standard algorithmic way to do this? Would I start with $A_2$ and edit the columns or start from scratch? Nov 17, 2022 at 19:06
• I recommend keeping a global pool of columns that can be accessed throughout the tree. Even when you solve the root node, it is probably better to keep all the columns rather than keeping the size of $A_2$ fixed, Nov 17, 2022 at 19:11

• you could keep variables continuous, perform proper branch-and-price, and branch on the variables of your master problem ($$x_i$$), but this is typically not efficient