Quadratic Assignment Problems: solution enumeration

In the last few posts we have given code for computing the Gilmore Lawler bound for quadratic assignment problems, and described two different branching techniques.   In this post we show how to enumerate solutions of a small QAP.  The possible solutions to a QAP range over permutations over unassigned facilities and locations.   If lower bounds do not increase after repeated branching, we may eventually assign nearly all the facilities to locations.  If there are only 2 or 3 remaining, we may as well just enumerate all the possible solutions and pick the best.   In practice, we hope that we will rarely have to do this, otherwise the branch-and-bound tree will be too large to process efficiently.  Here is a procedure that enumerates over all solutions of a size 3 QAP.  Iterating over permutations is a standard textbook problem, so maybe you can write cleaner code than I did here!

/// <summary>
/// Assume that all facilities have been assigned to locations,
/// except three. EnumerateSolutions enumerates all six remaining assignments
/// returns the best.
/// </summary>
private double EnumerateSolutions(Qap q, BranchAndBoundNode node, int[] pBest) {
double objBest;
int nPerm = perm3.GetLength(0);
int n = perm3.GetLength(1);
double[] obj = new double[nPerm];
int[] r = node.p.UnusedIndices().ToArray();
int[] c = node.pInv.UnusedIndices().ToArray();
int[] p = (int[])node.p.Clone();
Debug.Assert(r.Length == n, “Only call me for size “ + n + ” QAPs.”);

// Try all the possible permutations.
for (int i = 0; i < nPerm; i++) {
for (int j = 0; j < n; j++) {
p[r[j]] = c[perm3[i, j]];
}
obj[i] = q.Evaluate(p);
}

// Get the best permutation and objective.
int best = obj.ArgMin(out objBest);
p.CopyTo(pBest, 0);
for (int j = 0; j < n; j++) {
pBest[r[j]] = perm3[best, j];
}
return objBest;
}

If you combine the code from the following posts you will see that we almost have a working B&B solver:

In my next post I will fill in a couple of the gaps, and then I will re-post all of the code.  Then we’ll think about what we can actually do with a QAP solver!

Author: natebrix

Follow me on twitter at @natebrix.

3 thoughts on “Quadratic Assignment Problems: solution enumeration”

  1. It’s just that I’ve been hacking around with your solver snippets and there are a few gaps that I’d love to get clarified!

    And congrats for the blog it is awesome.

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