Quadratic assignment problems: branching

(This is part of a long-running series on quadratic assignment problems in C#.  Click here to catch up.)

Branching means to divide the search space represented by a node into subnodes.  QAP is about making assignments of facilities to locations, so two possible approaches come to mind:

  1. Branch into two subproblems: one where an assignment i -> j is allowed, and another where it is disallowed.
  2. Pick a facility and try assigning it to all possible locations, creating N subproblems.  (Or pick a location and assign all facilities to it…)

The second approach, called polytomic branching, turns out to be more effective.  The problem with the first (“single assignment branching”) is that the subproblems aren’t that much easier than the parent problem.  You’ll have to branch a whole bunch of times before you are able to determine anything.

We still need to decide whether to fix a facility (“row branching”) or a location (“column branching”).  And after that we need to figure out which particular facility or location is best.  At this point you may be wondering, “does it even matter?”  The answer is that, yes, branching decisions are earth shatteringly important.  Where’s what I mean: if you make bad branching choices it could take a thousand times longer to solve the problem, or more!  This is part of the reason why QAP (and branch-and-bound) are so interesting.  Bad branching decisions lead to subproblems that are just about as hard as the original problem.  It’s kind of like this. Here is a data structure that represents the results of a polytomic branching decision.

 

/// <summary>A branching decision, the result of applying a branching rule.
/// </summary>
internal class BranchingDecision {
/// <summary>If true, enumerate over all unassigned rows.
/// </summary>
public bool IsRowBranch { get; set; }
/// <summary>The row or column index.
/// </summary>
public int Index { get; set; }
/// <summary>Create a new instance.
/// </summary>
public BranchingDecision(bool isRowBranch, int index) {
IsRowBranch = isRowBranch;
Index = index;
}
}

Ultimately we want to write methods that produce BranchingDecisions.  The following delegate represents such a method (we will write two methods in the next blog post):

 

/// <summary>Makes a branching decision.
/// </summary>
internal delegate BranchingDecision Branch(BranchAndBoundNode node, double bound, double[][] U);

If you accept the claim that branching choices make a big difference, then it is clear that we want to branch so we get the easiest subproblems possible.  That is, nodes that will be processed by the branch-and-bound algorithm as quickly as possible.  We don’t know how to measure that directly (why?), so we have to guess.  A general framework for polytomic branching is to compute a score for each of the N^2 subproblems, and store it in a matrix.  S_ij is the score for the subproblem created by fixing facility i to location j.  Then compute the row and column sums of S, and branch on the row or the column with maximum sum.  Making a branching choice reduces to computing scores on subproblems.

The next step will be to write methods that compute scores and return BranchingDecisions.  We’ll look at two common ways to do that next time.  We’re about two or three posts away from having a pretty decent branch-and-bound solver for QAP.

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