I am building a program that uses branching-and-bounding to find an optimal path in a complete graph (the heuristic, faster algorithm is the second part). I have to begin and end at node 0. I was given a large hint that eliminating "hopeless" branches early in the algorithm will lead to an overall much faster runtime. I have tried several things: greedily selecting the smallest edge as either the first or last edge in the tour, branching into two subsets of solutions with one branch being solutions including the smallest available edge and the other being solutions that exclude the largest available edge. Neither have proved to be worth any salt, and I was wondering if there were any clever optimizations to branch-and-bound I could implement to help speed up my program. Any help will be appreciated!

Edit: any advice on computing better bounds and how to use them effectively is also welcomed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.