How to solve an Integer Linear Programming Problem Using Branch and Bound

In this video, first, we give a brief introduction about the difference between the linear programming problem and Integer linear programming problem. Then, we learn the Branch and Bound method to solve integer linear programming problems. Please carefully watch 8:20-10:00. In this part, we show that solution 27 is the optimal solution. I continue branching for the sake of understanding, in case someone started off by the right branch before starting on the left branch.

[@Cplas783]

You wouldn’t normally need to investigate further branches under the first right branch (X2 >= 3) is that correct? The objective value in the relaxed subproblem (26.75) is less than the current best (27) therefore no further branch can possibly yield anything better.

[@sxmirzaei]

yes, I mention that in the video, and if you don't skip you will hear that as well. Thanks!

[@Cplas783]

Must have missed it. Thank you very much

[@bazingazeroni]

Damn

[@johnlloydperez9755]

@@bazingazeroni haha

[@mokoepa]

@@bazingazeroni

[@bm-ub6zc]

you made a thing, that all my professors make sound difficult, sound easy. you have a gift. thank you.

[@sxmirzaei]

Thanks for the feedback!

[@duytandoan1325]

That's amazing cause i had spent about 3 hours to re-learn this section in the classroom but you have just helped me to tackle it just in 17 mins. Thanks so much!

[@nnoh7363]

A solid hour of confusion gone in just 20 min.! You're a lifesaver thanks so much!!

[@IbrahimovichZlatan]

Literally, a life saver before my exams.. thank you

[@bram3205]

This is fantastic! I learned branch and bound in like 10 minutes because of you. I really thought it was hard but my lecture notes are just so unclear..

[@halitmadensoy6156]

I wish, there was more Integer Programming videos, that you made. Thanks Professor.

[@tamerabdelmaguid4024]

Thanks for the detailed description of the branch and bound algorithm. I just would like to make a small note for the given problem. Since the objective function is the result of summing up the multiplications of the integer decision variables by integer coefficients, the optimal objective function value must be an integer. Since the optimal LP relaxation solution at the root node (subproblem1) is 27.67, so we can claim that 27 is an upper bound. Since the solution of the subproblem at the first branch is found to be 27, we can stop without the need to explore the other branches. This is a detailed description of the previous comment by Lekshman Ramesh.

[@sxmirzaei]

Thank you and that is correct! I went through the whole branches for learning purposes and also in cases where the order of solving subproblems are so that one goes through the right branch before going to the left ones.

[@poppop-oj6by]

Thanks I was looking for confirmation

[@tacituskilgore288]

I'm watching your playlist approximately two hours before my test. Thanks for saving me!

[@drunkshakespearee]

exam is in two days, and I feel soooo relieved I found your videos before my exam!!!! Thank you so much, I struggled so hard with my notes and my teachers, but you managed to make it clear and simple!!! Thanks!!! I hope I’ll pass!!!

[@sxmirzaei]

glad that it was helpful!

[@misbahraja4867]

Thank you! I have an exam in 2 hours and you saved my life.

[@engineering.skills]

Thank you for the video, it's very clear and concise! I have an exam in a few days and you've saved me hours trying to understand my professor's explanation.

[@nanaabenanyamekye9708]

Your explanation is very clear and the problem is simple enough to follow. Thanks a ton!!! I really appreciate this.

[@erickarwa-0705]

It is my first time working on this popular algorithm and from your video, I feel like I understand it so well. Thank you.

[@rachelm884]

thank god i've found your video! i was getting frustrated but now.....FINALLY i understand what i must do in just 10minutes! didn't even know that it was this easy! your explanations are so clear !

[@dangtrinh7781]

thank you very much =)). I literally didn't understand a thing about IP until i watched your video

[@ilivedinamericafor4years383]

thank you so much for this video! I passed my course!

[@zahrakashkaki3278]

I was searching for a video about Branch & Bound Method and finally got here. It was the best of all. Simple and easy to understand. Thank you :)

[@wyatt1339]

You make the best LP videos on TH-cam hands down. Thank you so much!

[@felixghandilyan3141]

Thanks a lot!! I have watched about 4 long videos and understood nothing. You made it in 10 minutes, finally I got the meaning of algorithm! Keep going that way, your approach of explaining the problems is really good 😊

[@sologirl3486]

Thank you so very much, I have an exam and you saved me

[@dalchemistt7]

I think there is a mistake @ 11:10, when you have found z= 26.75 for x1=1.75 and x2=3; you don't need to proceed further down since all the sub-problems of this branch will give solution z

[@TopDownApproach]

Lol! My OR teacher need to see this.
Thank you mam.

[@SequinBrain]

Not sure why textbooks can't be this clear, but thanks, that was amazing. Almost like they don't want you to know or something.

[@monicatran7162]

@3:25. for your optimal function. where did the 15 come from?

[@mervesafaarkan32]

To be able to find a point that maximizes our objective function, we started by putting the objective function equal to some arbitrary number.This arbitrary number is 15. You can put this function equal to any number that you would like.

[@betul3835]

@@mervesafaarkan32 thanks Merve!

[@michaelkam7449]

A very clear explanation with additional subtitle that really helped a lot. Thank you very much!

[@rabiadesue]

thank you so much for this video 🙏🏼 loved how you always put the graphics next to the branches and explained it so well and understandable 🙏🏼 thank you for your effort 😊

[@kamiliabedhief4598]

Thank you very much it's the best video,simple and very clear

[@enrico6505]

This is just such a great explanation, thank u so much!

[@debasish2205]

You got a sweet voice that makes learning quicker

[@yutaiyama7501]

your explanation is quite clear, thanks mirzaei!

[@LavkushSaraswat]

oh..really technique is good for explanation .im from india.you are a good teacher.😘😘😘

[@dps2]

Very nice explanation 👍

[@nguyenngoctosang7816]

Thank you for saving my final exam

[@jahidahmed7150]

Thanks very much. Very clear explanation and really helped to answer this method in my exam.

[@Caggen218]

Great explanation! Thank you!

[@truverol8205]

thank you, you are a lifesaver

[@_a_brightalireza122]

واقعا مفید و کمک کننده بود. ممنون👏🏻❤️

[@senaaydn9168]

Thank you, you make the best videos on TH-cam!

[@pouyaparseyan2464]

You are simply fantastic! Excellent lesson.

[@sxmirzaei]

Thank you!

[@berkarslan4353]

It is very well-prepared and helpful video, thanks for your work.

[@khaledsakkaamini4743]

thank you, better than my uni teacher

[@kabelomotloung9324]

Many thanks for sharing this. Very clear and concise.

[@ricardogonzalez8571]

how do you know which constraint to use, to replace the x values? because in some cases shes using constraint 2 and in the first case she used constraint 1

[@maryamahmadij.6752]

خیلی ممنون سرکار خانم میرزایی ^^ بسیار عالی بود

[@MazharAli-ld1si]

Love the way you teach...Hats off

[@poovizhip5136]

Thanks alot mam I'm so confused wd this because my staff was not perfectly teach this method .now I'm very clear 😍hpy to watch your videos once again Tqq so much mam

[@beoptimistic5853]

th-cam.com/video/fRyUf-GY754/w-d-xo.html ..💐

[@charliput4649]

So explanatory. I love you Abeg
. u 2 much ❤

[@charleena2319]

This video is amazing, thank you for a simple and straightforward explanation💚🦋

[@zakirasa4529]

Thank you for the clear explanation.

[@suciuandreicornel2746]

I WILL NOT FAIL MY EXAMS
GL YALL

[@samiehnajjaran8132]

Thank you for such a great explanation of this problem. 🙂

[@YeCheng-nm2uq]

Thanks! It`s very useful!

[@dinathaib631]

a very clear explanation ... thank you so much

[@Stayawayfrommyname]

I believe you mentioned that the optimum has to be at a vertex because it's a convex set, at 2:18, but I think that you have to require a concave objective function for that to be true.

[@alexenax1109]

Best! Thanks a lot Shokoufeh Mirzaei!!!

[@dariobressan8928]

Thank you, you are great explaining.

[@laulaintymak1132]

thank you soooooo much ! This is really helpful! you saved me 😢

[@yarooshshartooh7526]

Omg you've saved my day!! Thank you very much ❤️❤️❤️❤️

[@syasyanasuha854]

Thanks so much.. Now I can understand so well

[@akosirey3289]

BIG THANK YOU FOR THIS

[@DanielAlvarez-fb7jk]

Thank you so much. This video had been really helpful

[@adityajain7151]

Amazing Explanation! Great job

[@agustinvidalmusic]

superb explanation

[@sayalideo7823]

Very well explained. Thankyou. 😊

[@Alfonso00MA]

Great explanation. Thanks!

[@xijieliu4996]

In 15:47, x2>=4 while x1 = 1 is already the previous constraint, how can you get another branch with x1=0 and x2 = 4? I believe it is not fathomed, it is already infeasible.

[@hamednajand8327]

That was really clear and you made it so much easy to understand. Thank you for helping us to understand this topic very well 🙋🏼‍♂️

[@abdulmajeeda6682]

How did you get to make the objective function equal to 15 at 3:14

[@cenzowm]

Ohhhh thank you a lot from Italy!

[@MrsPaulinaaaaaaa]

Thank you so much, you made it so amazingly easily understandable! :)

[@my_religion]

Thanks alot. So helpful

[@farhanhyder7304]

Thanks, It was easy to follow

[@stefanlionar2335]

Thanks! The explanation is very clear. You sound like Francesca from Master of None, btw.

[@mathematicsandabstractions]

REally Amazing

[@broccoli322]

wow, really great video.

[@anhtientran3158]

Thank you for your illustrative and useful tutorial video

[@linussimon9210]

Thank you well done!

[@berdanakyurek7804]

Perfect. Thank you very much.

[@TimilehinOlaokun]

Thank you. This helped me a lot

[@sirona22]

lovely presentation ma'am

[@user-EricLin0619]

It's great !!!
thank you!!

[@satyanarayanbarik1701]

Thank you ma'am ☺️

[@Chanezk]

Such a great video thanks a lot for sharing it ♥️♥️

[@HamidAli-hs5gs]

I do not understand how you put x1=3 for the objective function value? As in your "How to Solve a Linear Programming Problem Using the Graphical Method" lecture, you said the optimal solution will be an intersection of constraint 1 and constraint 2. why not in this case? why we don't use a value of x1 = 7/3 and x2 8/3, for objective function value as you do in your Graphical method lecture?

[@tonyparkthechanger]

You saved me❤

[@RedPoppyblog]

خیلی ممنونم :)

[@the_ruling_alpha1156]

explain very well thank you so much

[@Purpleismyfavoritecolor63]

Thanks alot Mirzei....

[@khalidzyar292]

Well explained , thank you !

[@arthurchome4118]

This video is sooooo good. Thanks alot!

[@AVZ841]

very clear, thank you!

[@hoomanseyfi1941]

Very well explained thank you. Norouz mobarak :-)

[@sxmirzaei]

Thanks! likewise :)

[@Luk0nline]

Thank you! Very great explanation.

[@rionturner594]

This was an excellent explanation! I am taking Operations Research at the University of Maine at Augusta and I sure wish you were an instructor there. This is much more straightforward than our instructors' lectures! Fantastic right before an exam, thank you!

[@nadatika]

Thank you so much this helps a lot!

[@jessamaelastimoso1448]

Thank you!

[@selmaessafi1471]

THANK YOU SO SO MUCH

[@asiyanmaral2829]

Thank you very very very much!!

[@emrekara1824]

It WAS EASY MAN

[@AliVaseghnia]

Well made, thanks Shokoufeh. :)