0
$\begingroup$

I was reading about cutting stock problem https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-Bound and delayed column generation... I read them but it all look same ...every case we break problem into sub problem

Can anyone shed some more light with some example.?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Wikipedia cites some references with more details. Did you read those? If not, that should be your next step. $\endgroup$
    – D.W. ♦
    Jul 1, 2016 at 15:13
  • $\begingroup$ DO you undestand what dynamic programming and branch & bound are, respectively? $\endgroup$
    – Raphael ♦
    Jul 3, 2016 at 16:53
  • $\begingroup$ Yes I know about Dynamic programming and Branch and Bound. My main doubt was regarding delayed column generation , when can we use that over DP and BB while solving algroithms? $\endgroup$
    – Lalita Kumar
    Jul 4, 2016 at 2:34

1 Answer 1

Reset to default
-1
$\begingroup$
  • Dynamic programming is a strategy which avoids explicit enumeration of all possible solutions in the cutting stock problem.
  • Branch and bound is a search based technique also based on pruning. However in branch and bound you might in the worst case need to search over all possible solutions.
  • Column generation is a variant of branch and bound where instead of creating all variables at once they are generated sequentially based on which ones are more "attractive".

In terms of implementation you can implement dynamic programming in any general purpose programming language like C or Java while for column generation you will need to use specialised linear programming solvers as also for Linear programming based branch and bound.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ "Dynamic programming is a divide and conquer strategy" -- that's a dangerous and misleading thing to say. "while for the other two approaches you will need to use specialised integer programming solvers." -- that's plain wrong. Branch-and-bound can be implemented in any language. $\endgroup$
    – Raphael ♦
    Jul 2, 2016 at 9:46
  • $\begingroup$ Well I was talking about the special case of branch and bound where the linear relaxation is used for the bounding. Have modified the answer since the "divide and conquer" part did seem subjective. $\endgroup$
    – wabbit
    Jul 2, 2016 at 10:29

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.