Project With Bird’s Eye View
Hello again! After talking about myself and training week in my last blog, I said that in my next articles I will explain the project. I keep my word and share the details of the project with you on this blog. Fasten your seatbelts!
What is Branch and Bound ?
Imagine that you are an owner of a machine shop. In addition you have $40,000 for buying new machines, 200 square feet of available floor space to your shop to get more money.
Machines Space Price Profit
- Press 15 $8,000 $100
- Lathe 30 $4,000 $150
If machines have features like these; of course you want to maximize the profit. First you have to have a solution and then change the number of presses and lathes to control if it is true or not. Branch and Bound works like this too! In order to get the best results Branch and Bound method, separates the calculated values into branches by constantly changing the variables and checks the results by comparing them.
Firstly it generates a root node with a upper and lower bound. Our aim is make upper and lower bound as close as possible. Then two new child node will generate. For example we can make number of lathes 4 for one, and 5 for other one.
These child nodes calculated and compare. Our lower bound is 928 so right child does not need to branch because it’s upper bound is 929. So next step will be branching left child node. This branching will continue until all leaf nodes ‘s upper bound are close to lower bound. These branching strategies may vary depending on the problem.
What is Max-cut Problem ?
Unfortunately, our problem with Branch and Bound is not the machine to buy, but the max-cut problem. This problem is based on graphs. Graphs consists of edges and vertices.
Now consider that you have to cut this graph into 2 and get the maximum weights. For example; Vertices 1,5 is one group and 2,3,4 is the other group. The sum of the weights of the edges between the 2 groups will be our result.
In our example we found 3. Is this the max-cut number? I leave it up to you to find its correctness. You can apply the branch and bound method to find it of course 🙂
Why parallelization?
In the example above there was a graph of 5 vertices and we were able to reach the solving by ourselves. This is actually very small next to the graphs we are dealing with. Therefore, the branch and bound methods applied to them do not end in a short time. We want to shorten this calculation time thanks to parallelization. What they said, many hands make light work !
Now we investigate parallelization approaches and trying to implement these to our code. I hope that I can write more about these approaches to my next blog. In the meantime, I leave the link for those who are curious about the construction of the stones above. See you! https://www.youtube.com/watch?time_continue=8&v=yUQC6PYn0uw&feature=emb_logo
Leave a Reply