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.

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

Download the example to experiment with it and to see additional details.