Column Generation for the Cutting Stock Problem

แชร์
ฝัง
  • เผยแพร่เมื่อ 30 ธ.ค. 2024

ความคิดเห็น •

  • @reconshunter
    @reconshunter 3 ปีที่แล้ว +12

    Thank you sooo much Sergiy, I'm currently studying in germany and my Professor could'nt explain it half as understandable as you in 1 hour of time!
    You saved me a lot of nerves!

  • @AsadAli-tb7hy
    @AsadAli-tb7hy 3 ปีที่แล้ว +7

    This is probably the best video on this topic. Such a difficult topic is made so easy.

  • @ritsaartbergsma5396
    @ritsaartbergsma5396 4 หลายเดือนก่อน

    Great video and explaination, probably the best on youtube. What makes it great is the really thorough explanation of all steps. A lot of tutors too quickly assume that students are completely up to speed on all "preliminaries". Thank you!

  • @ameyamunagekar3795
    @ameyamunagekar3795 2 ปีที่แล้ว

    Fantastic explanation! The example really helped. Thank you!

  • @miikenaeko
    @miikenaeko 3 ปีที่แล้ว +1

    I am an undergraduate student in Japan. I am doing my own research on this issue.
    I wish I could have seen this wonderful video in my own language.

  • @tanvirkaisar7245
    @tanvirkaisar7245 2 ปีที่แล้ว +1

    hello Professor, thank you so much for the great explanation! I have some questions, I would be grateful if you could take the time to answer them.
    1. @28:00 Since you enumerated all the patterns, and used those patterns to see which pattern gives you the highest objective of CGSP, does not that defeat the whole purpose of not relying on storing the whole matrix A?
    2. @35:13, should not we drop the exiting basic variable from the RMP? otherwise, at each iteration the RMP will get larger, which means A will keep growing?

    • @sergiybutenko
      @sergiybutenko  2 ปีที่แล้ว +3

      1. Yes, you are right; in this toy example this is done for illustration purposes, since the complete LP is small enough to show it entirely.
      2. You could do that, but that (keeping only basic variables in the RMP) would be one of the two extremes, the other one being keeping all the columns introduced in the process. In the first extreme case you may end up spending more time on solving the subproblem, whereas in the second one the RMP may become too large. In practice one usually tries to balance between the two extremes (say, drop a nonbasic column from the RMP if it does not reenter the basis for a certain number of iterations).

    • @tanvirkaisar7245
      @tanvirkaisar7245 2 ปีที่แล้ว

      Thanks a ton!!

  • @lopyus
    @lopyus 2 ปีที่แล้ว

    15:55 how did you say that optimal dual solution is y=c_B^{T} B^{-1}? Why substituting c_B^{T} B^{-1} with y is useful? Thank you

    • @lopyus
      @lopyus 2 ปีที่แล้ว

      Nevermind, I think you mentioned it somewhere in your Dual Simplex video. Anyways, thanks for uploading this great course!

  • @jameszack7158
    @jameszack7158 2 ปีที่แล้ว +1

    Can column generation method only be used by computer software or can a person use this method on paper to solve LP problems?

  • @apprentice5271
    @apprentice5271 11 หลายเดือนก่อน

    Hi thanks for the lesson! I have a question. What happens if the solution of the CGSP is not a pattern of the problem. Suppose you solve the CGSP with knapsack and the solution is not one of your column.

    • @sergiybutenko
      @sergiybutenko  11 หลายเดือนก่อน

      The solution to the CGSP must be a feasible pattern, by design.

  • @danielmaia9336
    @danielmaia9336 3 ปีที่แล้ว

    Thank you! From Brazil!

  • @the_presenter5602
    @the_presenter5602 2 ปีที่แล้ว +1

    Best Explanation

  • @konstantinkuchenmeister1400
    @konstantinkuchenmeister1400 3 ปีที่แล้ว

    Best video on this topic!

  • @HUARASTACA
    @HUARASTACA ปีที่แล้ว

    i would like to see a CODE to find all the useful patterns and their waste

  • @blendmeister
    @blendmeister 2 ปีที่แล้ว

    Excellent video, it would great if you could extend it by doing a video on branch and price or even branch price and cut.
    Thanks!

  • @kamillebidan8410
    @kamillebidan8410 ปีที่แล้ว

    Can the number of columns being used actively increase? If the number of columns increases to 4, then matrix B would be a 4*3 matrix and it would be impossible to inverse?

    • @sergiybutenko
      @sergiybutenko  ปีที่แล้ว

      Matrix B contains only the columns corresponding to basic variables.

  • @Mattykkk25
    @Mattykkk25 2 ปีที่แล้ว

    Can you offer this in an excel sheet w solving formula?

  • @sungodfatih
    @sungodfatih 2 ปีที่แล้ว

    Thank you my man!

  • @hayataatafay3668
    @hayataatafay3668 2 ปีที่แล้ว

    what if we have more than 3 lengths, is there a way to determinate the pattern?

    • @sergiybutenko
      @sergiybutenko  2 ปีที่แล้ว +1

      Yes, the process of determining the feasible patterns would pretty much be the same.

  • @Snowmanver2
    @Snowmanver2 2 ปีที่แล้ว

    Thank you for the video!

  • @CharleConinx
    @CharleConinx 7 หลายเดือนก่อน

    legend!

  • @mrkunalgoswami2010
    @mrkunalgoswami2010 3 ปีที่แล้ว +1

    is it Gilmore-Gomory model ?

    • @sergiybutenko
      @sergiybutenko  3 ปีที่แล้ว +1

      Yes, the idea was originally proposed by Gilmore and Gomory in 1961.

  • @nagihanbostan2023
    @nagihanbostan2023 3 ปีที่แล้ว

    Thanks for video :)
    What is the C matrix and z used in the equation.

    • @sergiybutenko
      @sergiybutenko  3 ปีที่แล้ว

      You mean vector c? Check this video: th-cam.com/video/QAR8zthQypc/w-d-xo.html

    • @nagihanbostan2023
      @nagihanbostan2023 3 ปีที่แล้ว

      @@sergiybutenko Thanks a lot.

    • @nagihanbostan2023
      @nagihanbostan2023 3 ปีที่แล้ว

      @@sergiybutenko When I change the number of cuts (80, 50, 100) when I look at probabilities with a maximum of 3 waste, the number of pieces does not integer in the equation.
      Is it because my solution of the equation is wrong or because these probabilities are not enough for each number of pieces?
      do i have to look at more probabilities.

    • @sergiybutenko
      @sergiybutenko  3 ปีที่แล้ว +1

      We do not impose the integrality constraints in this formulation, so you can get non-integer solutions.

  • @abdulrahman-cb9uo
    @abdulrahman-cb9uo 2 ปีที่แล้ว

    sir i have a question, do u have code Column Generation for the Cutting Stock Problem for matlab?

  • @harunyucel354
    @harunyucel354 3 ปีที่แล้ว

    Will you consider to give online live training/courses. I would like to take because i have questions and need to understand also 2D cut and stock problems.

    • @sergiybutenko
      @sergiybutenko  3 ปีที่แล้ว

      You should come to Texas A&M and take the class :).

    • @harunyucel354
      @harunyucel354 3 ปีที่แล้ว

      @@sergiybutenko Thanks for you reply. and woow it is long way :))) Hello from Turkiye :) I need to understand this type of question for my thesis and i am really struggling- suffering :) In youtube you are the only one , explain fluent and detailed but i have missing part in basic knowledge about integer linear programming. Now i am watching other videos of you to figure out dual problems. I think you used duality in this example. (at least you can give such small trick :D:D )

    • @sergiybutenko
      @sergiybutenko  3 ปีที่แล้ว +1

      @@harunyucel354 yes, definitely study the duality material. Best of luck with your studies!

    • @harunyucel354
      @harunyucel354 3 ปีที่แล้ว

      @@sergiybutenko Sir , i handled 1D cutting stock problem.Thanks for you help via video. At final calculation i used excel solver and got good results. Thanks again. But now i need to understand 2D cut and stock problems. Cutting of rectangular stock plate in identical rectangular small pieces. Do you have any suggestion about this problem. Where should i start ? Do you have any idea about such problems ? Thanks in advance.

    • @s.butenko
      @s.butenko 3 ปีที่แล้ว

      @@harunyucel354 There is a universal method, called Feynman Problem-Solving Algorithm. Check it out :).

  • @top1ry0maDongLao
    @top1ry0maDongLao 22 วันที่ผ่านมา

    thank you sir

  • @pakwidi531
    @pakwidi531 ปีที่แล้ว

    Thank you sir.

  • @RayRay-yt5pe
    @RayRay-yt5pe ปีที่แล้ว

    What I do not like is you dancing in between notations without telling us what they mean. Otherwise great video.