Benders Decomposition: An Easy Example

[@TheWombatGuru]

I only learned about this decomposition technique today, and this tutorial has helped me greatly in understanding the relation between the master and subproblems. Thank you!

[@srinivasanbalan2469]

You are an excellent teacher. I appreciate your efforts, Dr. Zhang.

[@tuongnguyen9391]

This video make it so easy to understand bender decomposition because the linking constraint has been simplify to a form that is so simple with only one variable y

[@mesuraion8862]

Dude, why did you stop making videos? This is a great explanation. KIndly make more videos, please

[@rexnice5]

Hey, i want to ask about u*. How do you get the Extreme Ray ?? I know you have answered someone else by using simplex method, i've used simplex method but i dont know what to do next. Can you explain to me in detail ? Really appreciate it cause i need it for my college exam, thank you

[@srinivasanbalan5903]

Hi Dr. Zhang, can you explain benders decomposition for a real world supply chain problem?

[@minglee5164]

播主理解的相当到位

[@CTT36544]

8:24 the sign of the first constraint of the dual should be >=

[@maddalenanonato3031]

indeed, when then he writes the full dual with the actual coefficients, there it's correct

[@maverck8518]

Can you upload similar explanation for Lagrangian relaxation technique and column-generation technique for similar simple example?

[@srinivasanbalan2469]

Dr. Zhang, Could you provide a lecture for Dantzig Wolfe decomposition?

[@garychen6367]

Great job! Clear and well-organized video. And now I am heading to learn what is the dual problem. There are some typos I would like to point out, but correct me if I am wrong.
8:45： 1, There should be a Transpose Symbol at the right of the square brackets in the Min Function；
2, "u1+u10>=1.1" should be "u1+u11>=1.1"

[@databuck1599]

Another typo: at 8:27 the dual problem is incorrect -> the constraint should be >=, not

[@WorldVievv]

at 8:45, u1>=1.045 ? but value of u1 is 0 in second iteration. I think there is something wrong.

[@cristiancamilomarincano7929]

I am solving this example, I watched the same error!.u1>=1,045 should not exist at the beginning of first iteration

[@ohayane504]

all right, u1 >= 1.045 shouldn't exist in the first iteration (if you watch the next you'll remark that it was ignored in the next iterations).

[@ashkan67m]

Amazing work... what do you specialise in if I can ask?

[@youkaiwu4236]

I like your presentation. It does help me a lot.

[@supakarnsompasong4813]

I have a question can this algorithm implement with 2 integer variables (y1 and y2)?

[@ziyejia8621]

Thanks a lot for your clear explanation. And I have a question: could you please further explain the difference between Benders and Dantzig-Wolfe decomposition ? This problem confuses me so much.

[@unknown-utuber9186]

one is row generation (new constraints); one is column generation (new variables)

[@日出东方-k9w]

Many thanks for your great presentation! I just learn optimization~ At 6:47, why y_star=1500? Should y be less than 1000? Many thanks for all your response :)

[@muhammadyasirroni5280]

It's a random guess (as far as I understand).

[@danielx5447]

because the dual of the subproblem made y is not involved with constraints anymore but it moved to the objective function. In the master problem, y just need to greater than zero. Therefore, he can give any value to y as long as it is greater than zero.

[@farhanhyder7304]

Thank you. It was very helpful and intuitive

[@hzg4013]

thanks, it quickly referesh my memory on it

[@PengkaiShi]

讲的很清楚，感谢

[@abdallahjarray884]

Very nice explanation thank you Dr!

[@harrykacper]

Thanks for tutorial, it helps me a lot, still there is a one thing which is confusing for me. Why u* after first step when the problem of SB is not unbound is equal u* = (1,0,0....) if u1 = 1 it is violate constraints u1>=1.045

[@harrykacper]

ok, one more thing, dual after a second interation is min(100u2 +...+100u11) with assumption of y*=1000 so there is no u1 which accordign to the constraints should be u1 =

[@harrykacper]

and why u is not unbounded in this case?

[@zhj8242]

We should always keep the MP from generating unbounded dual sub problem.

[@harrykacper]

Thank you!

[@harrykacper]

One more think, could you write me some clues how to get extreme ray? I don't understand it :/ Thank you in advance!

[@jiayining7949]

hmmm UP 主可以介绍一下 Dantzig Wolfe Decomposition 吗 谢谢谢谢谢谢~

[@mauriciovalarezo9006]

Thanks so much, that was very useful to me!

[@ryan_soo6655]

Thank you!!

[@gaocai2265]

can you expain how you get the first cut? I am quite confused about analysing case when the unbounded dual occurs. It seems you jump a little bit.

[@zhj8242]

The extreme ray can be derived using simplex method or use cplex. The first cut is formulated to avoid the unbounded dual.

[@negarhaghighi2247]

Thank you very much, It was very helpful

[@aliasgharTofighian]

thank you so much, but i didn't understand substitution in cuts at all, would you please calculate one fully ? for example how z

[@zhj8242]

Hi Ali, Since f, b, B an u* are all known, these numerical values can be computed. I was lazy and used matlab to do the linear algebra :)

[@aliasgharTofighian]

张戬 Thanks a lot for your kind respond, but i am using "Lingo" and it gives some other answers, but at the end both have same answers !
oh and about "ybar" or fixed y, correct answer is found in reduced cost instead of real value ! which is wired, and means at the end of problem, real answers should be exchanged with reduced ones ! i wondered what is happen !
by the way very good course and nice framework, thanks a lot Dear Doctor.

[@王月月鸟-e9g]

讲的很清楚哦，谢谢

[@cahau8393]

may i know how you reach the equation for the feasibility cut?

[@anverHisham]

Nice video. Thanks a lot :-)

[@chenyuting5372]

很清晰

[@wuzhai2009]

Duel != Dual