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?
