Quadratic assignment problems: bounds

This is part 3 of what will be a long series about how to solve QAPs using branch-and-bound. My goal to end up with a simple branch-and-bound algorithm in C#.  In my last post I wrote down the formulation for QAP, wrote a QAP class in C#, and showed how to create subproblems for branching.  Let’s focus on lower bounds for QAP.

We get a lower bound for QAP by relaxing some of the constraints of the problem, and then solving the relaxed version of the problem.  Different bounds  are obtained by relaxing the constraints in different ways.  Unfortunately in most cases the relaxations require a lot of math and are pretty darn hard to blog about.  So I will pick one of the oldest bounds for QAP, called the “Gilmore Lawler” bound, and try to sketch the motivation behind it.  I’m not going to try and prove anything about the bound – the point is that the relaxation that we end up with is fairly easy to code, which is exactly what I’m after.  If you’re after a nitty-gritty derivation of the bound, there’s the original paper by Lawler from 1963 (!), or check out Cela’s book on QAP.

In the case of QAP, the constraint is that “X” in our equation is a permutation matrix.  Permutation matrices are matrices where the rows and columns sum up to 1 and each entry is either a 0 or a 1.  The idea behind the bound is to not be so strict about these constraints.  Since QAP is a minimization problem, dropping constraints means that you’re going to get a solution whose value is lower than it would otherwise have been:  a lower bound.   Loosening these constraints (and here’s where it gets hand-wavy) results in a linear assignment problem – the matrix for the LAP is formed from the input matrices (A, B, C).  Solving the linear assignment problem gives us GLB.  A few months back I wrote some code to solve linear assignment problems, so now let’s use it to compute GLB.  The code is below.  A few notes:

• Just like the last post, LinearAlgebra.NewMatrix(n) creates a new matrix of size n.  In general, when I make reference to a method in LinearAlgebra, I assume you can write it yourself!
• LinearAssignment.ReducedCosts computes what is known as the “dual matrix” for the solution.  I won’t get into the details – the important fact is that each element of the dual matrix U_ij is a kind of prediction of how much the objective function will increase when i assign facility “i” to location “j”.  In other words, if U_ij is really big, then assigning facility i to location j is probably a bad idea.  For this reason, the dual matrix (I’ll just call it the “U matrix”) is very useful in a branch-and-bound algorithm: it helps us make branching decisions.
• UPDATED 7/21/2010: I have broken out AssignmentMatrix into a separate method. Other QAP bounds, such as the one referenced in the paper in this post, use this matrix.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NathanBrixius.AssignmentLib {
  /// <summary>Computes the Gilmore-Lawler bound.</summary>
  public class GilmoreLawler {
    /// <summary>Computes the Gilmore-Lawler bound.</summary>
    /// <param name="qap">The QAP.</param>
    /// <param name="p">Primal solution.</param>
    /// <param name="U">Reduced costs matrix (dual solution).</param>
    /// <returns>The Gilmore-Lawler bound of the QAP.</returns>
    public static double Bound(Qap qap, int[] p, double[][] U) {
      int n = qap.Size;

      double[][] L = AssignmentMatrix(qap);

      // Solve LAP(L) to get bound - U is the reduced costs matrix.
      int[] ip = new int[n];
      double[] ys = new double[n];
      double[] yt = new double[n];
      double bound = LinearAssignment.Solve(L, p, ip, ys, yt) + qap.Shift;
      LinearAssignment.ReducedCosts(L, U, ys, yt);
      return bound;
    }

    public static double[][] AssignmentMatrix(Qap qap) {
      int n = qap.Size;
      // copy all elements of B_i into br_i except B_ii
      double[][] br = LinearAlgebra.NewMatrix(n, n - 1);
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
          br[i][j] = qap.B[i][j];
        }
        for (int j = i + 1; j < n; j++) {
          br[i][j - 1] = qap.B[i][j];
        }
        Array.Sort(br[i]);
        Array.Reverse(br[i]); // descending
      }

      // L_ij = A_ii B_jj + _ + c_ij
      // (A'_i is computed inline below)
      double[][] L = LinearAlgebra.NewMatrix(n);
      double[] ar_i = new double[n - 1];
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
          ar_i[j] = qap.A[i][j];
        }
        for (int j = i + 1; j < n; j++) {
          ar_i[j - 1] = qap.A[i][j];
        }
        Array.Sort(ar_i); // ascending
        for (int j = 0; j < n; j++) {
          double l_ij = qap.A[i][i] * qap.B[j][j] + qap.C[i][j];
          for (int k = 0; k < n - 1; k++) {
            l_ij += ar_i[k] * br[j][k];
          }
          L[i][j] = l_ij;
        }
      }
      return L;
    }
  }
}

Quadratic Assignment Problems: branch and bound

In my last post I introduced quadratic assignment problems.  As I explained, the problem is to assign an equal number of facilities to locations, minimizing the transportation cost.  A compact way to write the problem is to store the “flows” in a matrix A, the “distances” in matrix B, and represent assignments as permutation matrices.  If you throw in a linear term C, then the problem can be written as:

Branch-and-bound algorithms are the most common technique for finding optimal solutions for QAP.  The next few posts will focus on describing how branch-and-bound works and will result in a complete implementation of a QAP solver in C#.  Branch-and-bound is a “divide and conquer” solution technique for combinatorial problems. Branch-and-bound repeatedly divides a problem into simpler subproblems of the same type, which are then solved or further subdivided. The search space of a problem is partitioned into search spaces for its subproblems. The algorithm generates a search tree with the root corresponding to the original problem to be solved.  At each node in the search tree, a relaxed version of the subproblem is solved, typically by loosening the constraints of the subproblem. The solution to the relaxation is a lower bound to the original subproblem. If a lower bound at a given node exceeds the value of a previously known solution, then continued searching on this path cannot lead to an improved solution, and there’s no need to continue searching on that node’s subtree (this is called “fathoming”).

A little less formally, we take the search space and divide it into subregions.  Then for each piece, we solve a “relaxed” version of the problem to see if we can rule out the solution lying in that subregion.  If we can’t rule it out, we divide the subregion into pieces and repeat.  The “relaxation” part is bounding, the dividing is called branching.  The effectiveness of a branch-and-bound algorithm depends on 1) the strength of the bound, 2) how fast bounds can be computed, and 3) the branching decisions.  For example, if the bound is terrible we’ll never fathom subproblems and we’ll end up searching the entire tree.

So how do we apply branch-and-bound to QAP?  The solution to a QAP is an assignment of facilities to locations.  Therefore the subproblems are obtained by assigning some of the facilities to locations.  To branch, I can pick a facility and try assigning it to each of the available locations (or vice-versa).  As we will see, the logic for selecting which facility/location to branch on is extremely important.

Let’s start putting together some of the pieces of our branch-and-bound solver for QAP.  First, let’s define a QAP, which as I said before consists of the flow and distance matrices A and B, and a linear term C.

  // A quadratic assignment problem.
  public class Qap {
    // A (flow matrix).
    public double[][] A { get; set; }
    // B (distance matrix).
    public double[][] B { get; set; }
    // C (linear costs).
    public double[][] C { get; set; }
    // Constant term.
    public double Shift { get; set; }

    // Size of (A, B, C) matrices.
    public int Size {
      get { return A == null ? 0 : A.Length; }
    }

    // Compute tr AXBX' + CX', where the permutation matrix X is determined by p.
    public double Evaluate(int[] p) {
      double obj = this.Shift;
      for (int i = 0; i < A.Length; i++) {
        obj += this.C[i][p[i]];
        for (int j = 0; j < A[i].Length; j++) {
          obj += this.A[i][j] * this.B[p[i]][p[j]];
        }
      }
      return obj;
    }
}

To make the code shorter I am using C# 3.0 automatic properties. In addition to the matrices I have also added a constant term “Shift”, whose purpose will become clear in a moment.  I’ve also provided a method called Evaluate() that computes the objective given a permutation.  Let’s think about how branching works.  If we go back to the mathematical formulation of QAP at the start of this post, assigning a facility to a location means setting X_ij = 1.  If we plug X_ij into the formula above we see that we end up with a QAP of size n – 1 with:

A′ = A(ii)
B′ = B(jj)
C′ = C(ij) + 2 a_i b_j ,
Shift’ = A[i][i] B[j][j] + C[i][j] + Shift

Where  A(ij) denotes matrix A with row i and column j removed, a_i are the elements in row i of A, excluding A[i][i], and let b_j are the elements in column j of B, excluding b[j][j]. Here’s the code:

    private static Qap Reduce(Qap qap, int i, int j) {
      Qap r = new Qap();

      r.A = Reduce(qap.A, i, i);
      r.B = Reduce(qap.B, j, j);
      r.C = Reduce(qap.C, i, j);

      // Tack on: 2 a'_i b'_j (where a'_i is row i of A, with element i removed)
      for (int ii = 0; ii < r.Size; ii++) {
        for (int jj = 0; jj < r.Size; jj++) {
          r.C[ii][jj] += 2 * qap.A[i][ii < i ? ii : ii + 1] * qap.B[jj < j ? jj : jj + 1][j];
        }
      }

      r.Shift = qap.Shift + qap.A[i][i] * qap.B[j][j] + qap.C[i][j];

      return r;
    }

    private static double[][] Reduce(double[][] M, int i, int j) {
      double[][] R = LinearAlgebra.NewMatrix(M.Length - 1);
      for (int ii = 0; ii < R.Length; ii++) {
        for (int jj = 0; jj < R[ii].Length; jj++) {
          R[ii][jj] = M[ii < i ? ii : ii + 1][jj < j ? jj : jj + 1];
        }
      }
      return R;
    }

LinearAlgebra.NewMatrix() is a helper function that initializes the matrix. So now we have a data structure for QAP, and we now how to obtain subproblems.  Next time we’ll look at how to compute lower bounds.

Update 6/9/2010: Here is an additional method to read a problem in QAPLIB format.  It does not attempt to read the “C” matrix, and it is not totally robust. But it should work.

    public static Qap Read(StreamReader reader) {
      string content = reader.ReadToEnd();
      var tokens = content.Split(new char[] { ' ', '\n', '\r'}, StringSplitOptions.RemoveEmptyEntries);
      int k = 0;
      int size;
      if (Int32.TryParse(tokens[k++], NumberStyles.Integer, NumberFormatInfo.InvariantInfo, out size)) {
        Qap qap = new Qap();
        qap.A = ReadMatrix(size, size, tokens, ref k);
        qap.B = ReadMatrix(size, size, tokens, ref k);
        return qap;
      }
      throw new InvalidDataException("Invalid QAP size.");
    }

    private static double[][] ReadMatrix(int m, int n, string[] tokens, ref int k) {
      if (k + m * n > tokens.Length) {
        throw new InvalidDataException("Not enough matrix data.");
      }
      double[][] matrix = LinearAlgebra.NewMatrix(m, n);
      for (int i = 0; i < matrix.Length; i++) {
        for (int j = 0; j < matrix[i].Length; j++) {
          if (!Double.TryParse(tokens[k++], NumberStyles.Float, NumberFormatInfo.InvariantInfo, out matrix[i][j])) {
            throw new InvalidDataException("Invalid matrix entry.");
          }
        }
      }
      return matrix;
    }