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;
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] = c[perm3[i, j]];
}
obj = 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] = 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:

• Linear assignment problem solver.

• QAP object.

• QAP Gilmore-Lawler bound.

• Branch-and-bound skeleton.

• Vector and matrix utilities.

• Branching.

• Strong and weak branching.

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!