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!

[@nnoh7363]

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

[@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!

[@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..

[@IbrahimovichZlatan]

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

[@wyatt1339]

You make the best LP videos on KZbin hands down. Thank you so much!

[@nanaabenanyamekye9708]

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

[@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 :)

[@michaelkam7449]

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

[@tacituskilgore288]

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

[@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.

[@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 😊

[@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 !

[@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 😊

[@dangtrinh7781]

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

[@halitmadensoy6156]

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

[@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 🙋🏼‍♂️

[@jahidahmed7150]

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

[@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.

[@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

[@sologirl3486]

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

[@berkarslan4353]

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

[@yutaiyama7501]

your explanation is quite clear, thanks mirzaei!

[@charleena2319]

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

[@senaaydn9168]

Thank you, you make the best videos on KZbin!

[@misbahraja4867]

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

[@maryamahmadij.6752]

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

[@MazharAli-ld1si]

Love the way you teach...Hats off

[@kabelomotloung9324]

Many thanks for sharing this. Very clear and concise.

[@DanielAlvarez-fb7jk]

Thank you so much. This video had been really helpful

[@_a_brightalireza122]

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

[@TopDownApproach]

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

[@LavkushSaraswat]

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

[@alexenax1109]

Best! Thanks a lot Shokoufeh Mirzaei!!!

[@dariobressan8928]

Thank you, you are great explaining.

[@MrsPaulinaaaaaaa]

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

[@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!

[@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

[@omidmokhtari1066]

Hello. Thanks for your complete explanation. Could you mention a good article or book which has used Branch and Bound in an algorithm? I have a MIP problem with a huge amount of binary variables that can't be solved without any iterative algorithms.

[@enrico6505]

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

[@adityajain7151]

Amazing Explanation! Great job

[@ilivedinamericafor4years383]

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

[@anhtientran3158]

Thank you for your illustrative and useful tutorial video

[@samiehnajjaran8132]

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

[@pouyaparseyan2464]

You are simply fantastic! Excellent lesson.

[@sxmirzaei]

Thank you!

[@charliput4649]

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

[@yarooshshartooh7526]

Omg you've saved my day!! Thank you very 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.

[@Caggen218]

Great explanation! Thank you!

[@dinathaib631]

a very clear explanation ... thank you so much

[@kamiliabedhief4598]

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

[@stefanlionar2335]

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

[@zakirasa4529]

Thank you for the clear explanation.

[@arthurchome4118]

This video is sooooo good. Thanks alot!

[@laulaintymak1132]

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

[@cenzowm]

Ohhhh thank you a lot from Italy!

[@syasyanasuha854]

Thanks so much.. Now I can understand so well

[@khaledsakkaamini4743]

thank you, better than my uni teacher

[@aaallami]

very nice but do you know how to calculate the time complexity of B&B algorithm any clue I would appreciate that. I found that all they mention is exponential but how did they come up with that. thanks

[@AliVaseghnia]

Well made, thanks Shokoufeh. :)

[@khalidzyar292]

Well explained , thank you !

[@Alfonso00MA]

Great explanation. Thanks!

[@truverol8205]

thank you, you are a lifesaver

[@Owen7768]

Hey I have a question: In my exercise I got two options in the end of the tree: 1) (2,3) with z = 5 2) (3,2) with z = 5 how can I know which of these two points is the correct one? ty

[@sayalideo7823]

Very well explained. Thankyou. 😊

[@TimilehinOlaokun]

Thank you. This helped me a lot

[@nadatika]

Thank you so much this helps a lot!

[@nguyenngoctosang7816]

Thank you for saving my final exam

[@debasish2205]

You got a sweet voice that makes learning quicker

[@YeCheng-nm2uq]

Thanks! It`s very useful!

[@the_ruling_alpha1156]

explain very well thank you so much

[@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

[@matiastret]

Yo made a really nice video, thanks for your help

[@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!

[@Chanezk]

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

[@berdanakyurek7804]

Perfect. Thank you very much.

[@AVZ841]

very clear, thank you!

[@dps2]

Very nice explanation 👍

[@farhanhyder7304]

Thanks, It was easy to follow

[@umutbicakci]

Thank you for your help! 🙏

[@adesojialu1051]

at time 13:23 you said you will add X1 is less than or equal to 3, where did this come from?

[@ahmedyehia7940]

@Shokoufeh Mirzaei It's very useful and easy to learn with your teaching. thanks! is there any videos for Travelling Salesman Problem?

[@gorkemozcan7638]

How did you decide that you'd continue with x_2 = 3 at 6:50 ?

[@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]

kzbin.info/www/bejne/nIPchpljfL5qa5Y ..💐

[@mrsmith782]

very well explained!

[@hasanshahzad4624]

if it had been a minimization problem, just for my learning sake would you have chosen X1=2.33 instead of X1=2.66 in the first iteration. Or we just go with the higher value even if minimization problem. Please i have an exam tomorrow, can you please clarify my problem

[@jessamaelastimoso1448]

Thank you!

[@user-EricLin0619]

It's great !!! thank you!!

[@akosirey3289]

BIG THANK YOU FOR THIS

[@sirona22]

lovely presentation ma'am

[@abdulmajeeda6682]

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

[@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!

[@berfingul6298]

Are you going to make a video for "binary" integer programming problem with using B&B tree solution?

[@shengxue4844]

Thank you so much ！

[@agustinvidalmusic]

superb explanation

[@my_religion]

Thanks alot. So helpful

[@ritikanegi1604]

Thank you so much ma'am.

[@broccoli322]

wow, really great video.