4
$\begingroup$

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...).

$\endgroup$
4
  • $\begingroup$ I don't think this is such a straightforward question as you assume. $\endgroup$
    – Kuifje
    Nov 17, 2022 at 18:20
  • $\begingroup$ At each tree node, you need to exclude any existing columns that violate the branching and generate new columns that respect the branching. $\endgroup$
    – RobPratt
    Nov 17, 2022 at 19:03
  • $\begingroup$ @RobPratt Is there a standard algorithmic way to do this? Would I start with $A_2$ and edit the columns or start from scratch? $\endgroup$
    – 133crem
    Nov 17, 2022 at 19:06
  • $\begingroup$ 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, $\endgroup$
    – RobPratt
    Nov 17, 2022 at 19:11

1 Answer 1

2
$\begingroup$

At this stage you have the following options :

  • you could solve the restricted master problem with integer variables (this is also called price-and-branch). In this case you are using classical branch-and-bound, but potentially with not the right variables to reach optimality. So this is a heuristic.
  • 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
  • you could keep variables continuous and branch differently, within the subproblem.
$\endgroup$
4
  • $\begingroup$ Thank you for your answer! I think in the context of what I'm studying I am focusing on the second option (branch and price) albeit not efficient. I have edited my question to hopefully give more information on why I am unsuccessful in doing this. $\endgroup$
    – 133crem
    Nov 17, 2022 at 18:35
  • $\begingroup$ The second option, branching on columns, is viable only if you can afford to generate all columns (and therefore the column generation procedure is not useful). It might be the case if your cutting stock problem has few items with large quantities, and few items in each pattern. $\endgroup$
    – fontanf
    Nov 17, 2022 at 20:48
  • $\begingroup$ In the case of a bin packing (cutting stock with unitary demands), the standard way to branch in a branch-and-price is to force two items to be in the same bin, or to force them to be in different bins. But this branching rule changes the sub-problem. It becomes a knapsack problem with conflicts, which is strongly NP-hard. I don't know if there is an efficient way to generalize this rule for a cutting stock problem with non-unitary demands $\endgroup$
    – fontanf
    Nov 17, 2022 at 20:50
  • $\begingroup$ Option 2 doesn't work because there is no way to enforce a lower bound : it's impossible (very, very hard, I guess) to prevent the subproblem from generating an existing column. You can filter these out but then how do you prove optimality? $\endgroup$
    – fredq
    Feb 9 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.