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

[partition problem]

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 much better bound than the previous method that puts everything in set 1.

If you compare the best solution values shown by this program and the previous version in the Output window, you'll see that this program updates the best solution much less often. However, the total run time of this program is only a little better than the previous version. Even the previous version skips large parts of the search tree after it works through a few test solutions and finds a decent bound.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, mathematics and tagged , , , , , , , , , , , , , , , , , , , , . Bookmark the permalink.

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

  1. Anti CounterFit Solutions

    BLOG.CSHARPHELPER.COM: Use branch and bound with an initial heuristic to solve the partitioning problem in C#

Leave a Reply

Your email address will not be published. Required fields are marked *