I applied B&P algorithm in my master thesis years ago and read many of your works as the main references. Additionally, watching this video is very enlightening and inspiring (content- and explanation-wise). There are many things about column generation that I finally understand completely. In that regard, I would like to say thank you very very much, Sir! This is also one of my favs in CO@Work2020. Really can't wait for the Q&A session :)
What a coincidence! I just finished reading the thesis by Dr. M. Lübbecke on the GCG plugin in 2010. It is a complete work and detailed in implementations.Then I want to know more about the BP algorithm and I ran into this video! Also produced by the author!! Amazing. Thanks a lot! Very nice work!
Amazing lesson!! My favorite of this CO@Work2020! I will definitely try to think/study and implement a Brach&Price&Cut for my favorite problem! Maybe for my master thesis 😆 Really thank you🙏
Professor Lubbecke gives an excellent presentation. It is also a great resource to have softwares like SCIP and gcg !!!! I would like to know which decomposition techniques other than Dantzig Wolfe and Benders have been investigated for the exact solution of MIPs? Could you recommend me some bibliography on this subject? Thank you very much, greetings from the city of Medellin, Colombia.
I was looking for an example with Dantzig Wolfe decomposition with Big M method to solve infeasibility. If someone has any example file or solver code that will be great. thank you.
Hi! I am also a student so I might be a little off, but is something we learn when we study the Simplex method. From wikpedia: "reduced cost, or opportunity cost, is the amount by which an objective function coefficient would have to improve (so increase for maximization problem, decrease for minimization problem) before it would be possible for a corresponding variable to assume a positive value in the optimal solution." So, for a specific variable, if you have a negative reduced cost, tha means that it would only worsen the solution if it would have a negative value in solution. Since in the standart form of te simplex the variables are always positive, this will not happen and we can put the variable in the solution (base) and recompute it. If every variable that is not in the solution has a positive reduced cost, it means that there is no variable to put that will net a better solution, so we have a optimum solution. On column generation is pretty much the same. If a column have a negative reduced cost, it means that it will probably bring a better solution unless it takes a negative value (which doesn't happen due to constraint gamma>0) and we can put it in the problem. Likewise, if every column has positive reduced cost, that means that no column will net better results than what we already got and we ensure we have a optimum solution.
the reduced cost of a variable indicates the contribution to the objective if we increase one unit in that variable. More details can be found in Simplex method, in Chinese, 单纯型法。
Why do we ignore π₀ in the objective function of the DW pricing problem? If the minimum reduced cost is of an extreme ray, then there might be an extreme point with smaller reduced cost but we cannot determine that because we compute it without π₀? I do not know what I am missing?
Thank you my GOAT
I applied B&P algorithm in my master thesis years ago and read many of your works as the main references. Additionally, watching this video is very enlightening and inspiring (content- and explanation-wise). There are many things about column generation that I finally understand completely. In that regard, I would like to say thank you very very much, Sir!
This is also one of my favs in CO@Work2020. Really can't wait for the Q&A session :)
you are very welcome!
What a coincidence! I just finished reading the thesis by Dr. M. Lübbecke on the GCG plugin in 2010. It is a complete work and detailed in implementations.Then I want to know more about the BP algorithm and I ran into this video! Also produced by the author!! Amazing. Thanks a lot! Very nice work!
Hi, what's your major?
Amazing lesson!! My favorite of this CO@Work2020!
I will definitely try to think/study and implement a Brach&Price&Cut for my favorite problem! Maybe for my master thesis 😆
Really thank you🙏
thanks, Daniel, much appreciated
Awesome stuff with lovely explanations. Many thanks for sharing! :)
Glad you liked it!
Excellent presentation! thank you!
Incredible lecture! Thanks!
brilliant lecture!
Thnaks for this class!
Thanks! It helps a lot.
Professor Lubbecke gives an excellent presentation. It is also a great resource to have softwares like SCIP and gcg !!!! I would like to know which decomposition techniques other than Dantzig Wolfe and Benders have been investigated for the exact solution of MIPs? Could you recommend me some bibliography on this subject?
Thank you very much, greetings from the city of Medellin, Colombia.
I was looking for an example with Dantzig Wolfe decomposition with Big M method to solve infeasibility. If someone has any example file or solver code that will be great. thank you.
What is reduced cost? can someone explain it more?
Hi! I am also a student so I might be a little off, but is something we learn when we study the Simplex method.
From wikpedia: "reduced cost, or opportunity cost, is the amount by which an objective function coefficient would have to improve (so increase for maximization problem, decrease for minimization problem) before it would be possible for a corresponding variable to assume a positive value in the optimal solution."
So, for a specific variable, if you have a negative reduced cost, tha means that it would only worsen the solution if it would have a negative value in solution. Since in the standart form of te simplex the variables are always positive, this will not happen and we can put the variable in the solution (base) and recompute it. If every variable that is not in the solution has a positive reduced cost, it means that there is no variable to put that will net a better solution, so we have a optimum solution.
On column generation is pretty much the same. If a column have a negative reduced cost, it means that it will probably bring a better solution unless it takes a negative value (which doesn't happen due to constraint gamma>0) and we can put it in the problem. Likewise, if every column has positive reduced cost, that means that no column will net better results than what we already got and we ensure we have a optimum solution.
the reduced cost of a variable indicates the contribution to the objective if we increase one unit in that variable. More details can be found in Simplex method, in Chinese, 单纯型法。
Why do we ignore π₀ in the objective function of the DW pricing problem? If the minimum reduced cost is of an extreme ray, then there might be an extreme point with smaller reduced cost but we cannot determine that because we compute it without π₀? I do not know what I am missing?
Oops, I needed to wait for one more slide!