Branch-and-bound algorithms for QAP

This is part 4 in a series of posts laying out a simple branch-and-bound solver for QAP in C#. Last time (several months ago!) I provided a simple bounding procedure for QAP.  I want to take a step back and give the high-level algorithm, then in subsequent posts I will fill in the implementation.

Branch-and-bound algorithms are a general framework for solving combinatorial optimization problems.  The idea is to repeatedly subdivide the search space into smaller subproblems of the same time.  For each subproblem we compute bounds, which may allow us to determine that the subproblem cannot lead to an improved solution to the original problem.

  /// Solves QAP using branch-and-bound. /// 
  public class BranchAndBound {

    private readonly Qap _qap;
    private BranchAndBoundResults _results;

    /// Create a new instance. /// 
    public BranchAndBound(Qap qap) {
      _qap = qap;
    }

    /// Solve a QAP to optimality. /// 
    public void Solve() {

      _results = new BranchAndBoundResults();
      Stack stack = new Stack(); stack.Push(new BranchAndBoundNode(_qap)); while (stack.Count > 0) { BranchAndBoundNode node = stack.Pop(); if (node.LowerBound <= _results.Objective) { if (node_is_easy_to_solve) { EnumerateSolutions(node, _results); } else { node.LowerBound = GLB.Bound(node.Qap, U); if (node.LowerBound <= _results.Objective) { foreach (BranchAndBoundNode subNode in Branch(node, U).OrderBy(n => n.LowerBound)) { stack.Push(subNode); } } } } } } } /// A subproblem in a branch-and-bound algorithm. ///  public class BranchAndBoundNode { private readonly Qap _qap; /// The size of the subproblem. ///  public int Size { get { return _qap.Size; } } /// The lower bound of the subproblem. ///  public double LowerBound { get; set; } /// The QAP subproblem. ///  public Qap Qap { get { return _qap; } } } /// Branch-and-bound solution information. ///  public class BranchAndBoundResults { public int[] p { get; set; } public double Objective { get; set; } } 

Let’s work through the pseudocode.  Our stack will contain the current set of subproblems that need to be solved.  We initialize the stack with our QAP instance, wrapping it inside a BranchAndBoundNode data  structure.  We’ll develop this data structure as we go, but from the code we can already see two uses:

  • It stores the subproblem (a QAP),
  • It stores the lower bound computed by the code from my last post.

The other thing we do is allocate a data structure which stores the results: the best assignment found so far, and the best objective value.  In the main loop of Solve() we repeatedly pop nodes from the stack.  We first compare the node’s lower bound to the best objective (also called the incumbent).  If the lower bound exceeds the incumbent value, there is no way this subproblem can lead to a better result, so we need not process it.  The incumbent value may have changed since the subproblem was created.  Then we check to see if the subproblem is “easy” – if so, we can simply enumerate over all possible solutions for the subproblem and update the results if needed.  Otherwise, we use our GLB code to compute a bound.  Again, we check the lower bound to see if we can eliminate (or fathom) the subproblem.  If not, we need to subdivide the node into subproblems, and push them onto the stack.

The top-level algorithm itself is not all that complicated!  It’s also quite general.  We have already described how to compute bounds, so all we need to do is specify:

  • How to enumerate solutions for small problems.
  • How to branch – i.e. how to subdivide BranchAndBoundNodes.

The motivation and code for enumerating and branching will be the subject of the next two posts.

Author: natebrix

Follow me on twitter at @natebrix.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s