7
$\begingroup$

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?

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 :) $\endgroup$ Sep 26, 2022 at 16:15
  • $\begingroup$ Yes, you would need to do "branch-and-price" (embedding column generation in branch-and-bound). Glad to help. $\endgroup$
    – RobPratt
    Sep 26, 2022 at 16:20

Your Answer

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

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