# Can't solve a specific instance of Gilmore & Gomory Cutting Stock with Delayed Column Generation

I am now somewhat comfortable with delayed column generation, but one specific example has been bugging me, as it's quite simple (on the second iteration we stop) and I can't reach the optimal solution.

The instance has the following settings:

item_width = [13,16] demand = [3,3] roll_width = 46

The optimal solution is (1,2) + (2,1). But let's take it step by step. I start with an initial set of patterns, P = [(3,0),(0,2)] and compute the restricted master problem

$$\text{minimize} \quad x_{0} + x_{1}$$ $$\text{s.t.}\quad 3\times x_{0} \geq 3$$ $$\quad 2\times x_{1} \geq 3$$

Which gives us the dual values of $$\pi_{0} = \frac{1}{3}$$ and $$\pi_{1} = \frac{1}{2}$$. The pricing problem is then

$$\text{maximize} \quad \frac{1}{3}\times y_{0} + \frac{1}{2}\times y_{1}$$ $$\text{s.t.} \quad 13\times y_{0} + 16 \times y_{1} \leq 46$$

Where we get the new pattern (1,2). For the second and final iteration, the RMP becomes

$$\text{minimize} \quad x_{0} + x_{1} + x_{2}$$ $$\text{s.t.} \quad 3\times x_{0} + x_{2} \geq 3$$ $$2\times x_{1} + 2\times x_{2} \geq 3$$

With the dual values $$\pi_{0} = \frac{1}{3}$$, $$\pi_{1} = \frac{1}{3}$$. If we update the pricing problem, multiple patterns yield the optimal solution: (1,2), (2,1), (3,0). If I pick the pattern that I know should be in the optimal solution, then sure, I can reach the optimal solution, but I don't understand how that can have the same reduced cost as a pattern that I have already considered. I know that there is something I am doing wrong, but I can't see what.

If the pattern (2,1) is part of the original set of Patterns in the first iteration, then I can solve the problem without issues, but that shouldn't be necessary, right?

What you have done is correct, but the final pricing problem has optimal objective value $$1$$, which corresponds to reduced cost $$1-1=0$$, so you do not generate a new pattern, and you have solved the master LP, which has optimal objective value $$2$$. The resulting restricted master ILP has optimal objective value $$3$$. This is a case where the "price-and-branch" heuristic does not yield an optimal integer solution.

• Ah, that never crossed my mind, thank you! I see that I now have to branch, and so there's quite a bit more to go. As a side note, I would also like to thank you for an answer you gave me last year, that helped me with my master's thesis :) Sep 26, 2022 at 16:15
• Yes, you would need to do "branch-and-price" (embedding column generation in branch-and-bound). Glad to help. Sep 26, 2022 at 16:20