Index Books FAQ Contact About Rod

# Title: Use branch and bound with an initial heuristic to solve the partition problem in C#

The post Use exhaustive search to solve the partition problem in C# explains the partition problem and how you can use an exhaustive search to find solutions for it.

The post Use branch and bound to solve the partition problem in C# uses the branch and bound technique to solve larger instances of the problem. Branch and bound avoids visiting branches in a search tree if that branch cannot possibly improve the best solution found so far. However, the initial implementation of branch and bound begins by recursively always assigning items to set 1. That means the first test solution places every item in set 1, and that's a pretty terrible solution. That means the program doesn't have a tight bound on the best possible solution so it cannot skip visiting many branches, at least in the beginning.

This example users a heuristic to find an initial solution to set a lower bound on the best possible error. That lets it avoid visiting more branches in the tree.

The heuristic simply examines the items and adds an item to the set with the smaller total value at the time.

// Use a greedy heuristic to find an initial solution. // Method: Loop through the items adding the next item to // whichever set has the smaller total value so far. private void PartitionValuesGreedy(int[] values, bool[] best_assignment, ref int best_err) { // Initialize the sets' total values. int total1 = 0, total2 = 0; // Add the items. for (int i = 0; i < best_assignment.Length; i++) { if (total1 <= total2) { // Add item i to set 1. best_assignment[i] = true; total1 += values[i]; } else { // Add item i to set 2. //best_assignment[i] = false; total2 += values[i]; } } // Set the best error. best_err = Math.Abs(total1 - total2); }

This heuristic is simple, fast, and provides a better bound than the previous method that puts everything in set 1.

The followig table shows the number of times the programs added a value to the test solution and their total times.

MethodNodes VisitedTime (sec)
Exhaustive2,147,483,64613.89
Branch & Bound58,571,1320.55
B & B w/Heuristic58,568,4360.45
You can see that Branch and Bound makes an enormous difference. Adding the heuristic first pass only made a small difference, and even then I needed to work hard to find a set of values where it made any noticeable difference at all. (You can try to figure out what's special about those values.) It is possible that the heuristic helps for some very large data sets, but it's likely that it will provide only a small benefit.

For more information on algorithms such as these, see my book Essential Algorithms.