How to solve an Integer Linear Programming Problem Using Branch and Bound
Вставка
- Опубліковано 3 січ 2018
- 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.
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.
yes, I mention that in the video, and if you don't skip you will hear that as well. Thanks!
Must have missed it. Thank you very much
Damn
@@bazingazeroni haha
@@bazingazeroni
you made a thing, that all my professors make sound difficult, sound easy. you have a gift. thank you.
Thanks for the feedback!
A solid hour of confusion gone in just 20 min.! You're a lifesaver thanks so much!!
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!
Literally, a life saver before my exams.. thank you
You make the best LP videos on UA-cam hands down. Thank you so much!
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..
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 :)
I'm watching your playlist approximately two hours before my test. Thanks for saving me!
Your explanation is very clear and the problem is simple enough to follow. Thanks a ton!!! I really appreciate this.
A very clear explanation with additional subtitle that really helped a lot. Thank you very much!
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.
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 😊
It is my first time working on this popular algorithm and from your video, I feel like I understand it so well. Thank you.
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 !
thank you very much =)). I literally didn't understand a thing about IP until i watched your video
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!!!
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 😊
I wish, there was more Integer Programming videos, that you made. Thanks Professor.
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.
Thank you so very much, I have an exam and you saved me
Thanks very much. Very clear explanation and really helped to answer this method in my exam.
That was really clear and you made it so much easy to understand. Thank you for helping us to understand this topic very well 🙋🏼♂️
Thank you! I have an exam in 2 hours and you saved my life.
It is very well-prepared and helpful video, thanks for your work.
your explanation is quite clear, thanks mirzaei!
This video is amazing, thank you for a simple and straightforward explanation💚🦋
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.
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.
Thanks I was looking for confirmation
Thank you, you make the best videos on UA-cam!
خیلی ممنون سرکار خانم میرزایی ^^ بسیار عالی بود
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.
Many thanks for sharing this. Very clear and concise.
واقعا مفید و کمک کننده بود. ممنون👏🏻❤️
Love the way you teach...Hats off
oh..really technique is good for explanation .im from india.you are a good teacher.😘😘😘
Best! Thanks a lot Shokoufeh Mirzaei!!!
thank you so much for this video! I passed my course!
This is just such a great explanation, thank u so much!
Lol! My OR teacher need to see this.
Thank you mam.
Amazing Explanation! Great job
You are simply fantastic! Excellent lesson.
Thank you!
Thank you very much it's the best video,simple and very clear
Thank you so much. This video had been really helpful
Thank you so much, you made it so amazingly easily understandable! :)
Thank you, you are great explaining.
Thank you for such a great explanation of this problem. 🙂
So explanatory. I love you Abeg
. u 2 much ❤
Great explanation! Thank you!
Thank you for your illustrative and useful tutorial video
Omg you've saved my day!! Thank you very much ❤️❤️❤️❤️
You got a sweet voice that makes learning quicker
Thanks! The explanation is very clear. You sound like Francesca from Master of None, btw.
Ohhhh thank you a lot from Italy!
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
a very clear explanation ... thank you so much
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
thank you, better than my uni teacher
Thank you for the clear explanation.
thank you soooooo much ! This is really helpful! you saved me 😢
Thanks so much.. Now I can understand so well
This video is sooooo good. Thanks alot!
Well made, thanks Shokoufeh. :)
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
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.
Great explanation. Thanks!
Very well explained. Thankyou. 😊
Thank you for saving my final exam
Well explained , thank you !
Thanks! It`s very useful!
thank you, you are a lifesaver
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
Thank you so much this helps a lot!
Thank you. This helped me a lot
Very nice explanation 👍
at time 13:23 you said you will add X1 is less than or equal to 3, where did this come from?
Would it be possible to abort the calculations after finding that x_2 >= 3 gives an optimal solution of 26.75? Because we know that anything after it will be worse and therefore also worse than the solution found with x_2
lovely presentation ma'am
Such a great video thanks a lot for sharing it ♥️♥️
very clear, thank you!
Thanks, It was easy to follow
How did you decide that you'd continue with x_2 = 3 at 6:50 ?
very well explained!
explain very well thank you so much
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
Perfect. Thank you very much.
Thank you for your help! 🙏
Thank you! Very great explanation.
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!
Yo made a really nice video, thanks for your help
BIG THANK YOU FOR THIS
It's great !!!
thank you!!
superb explanation
wow, really great video.
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
ua-cam.com/video/fRyUf-GY754/v-deo.html ..💐
@Shokoufeh Mirzaei
It's very useful and easy to learn with your teaching. thanks!
is there any videos for Travelling Salesman Problem?
Please ma'am I'm a bit confused about the inequality signs starting from the sub-problem 1 where X2 = 3 ...
REally Amazing
Great stuff!
Thanks alot. So helpful
@3:25. for your optimal function. where did the 15 come from?
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.
@@mervesafaarkan32 thanks Merve!
Thank you!