Quadratic Assignment Problem Branch And Bound Search

  • 1.

    S.H. Bokhari . Assignment problems in parallel and distributed computing. The Kluwer International Series in Engineering and Computer Science. Kluwer Academic Publishers, Boston/Dordrecht/Lancaster, 1987.Google Scholar

  • 2.

    Brian Borchers and John E. Mitchell. Using an interior point method in a branch and bound algorithm for integer programming. Technical report, Rensselaer Polytechnic Institute, July 1992.Google Scholar

  • 3.

    R.E. Burkard and U. Derigs. Assignment and matching problems: Solution methods with Fortran programs, volume 184 of Lecture Notes in Economics and Mathematical Systems. Springer, Berlin, 1980.Google Scholar

  • 4.

    R.E. Burkard, S. Karisch, and F. Rendí. QAPLIB — A quadratic assignment problem library. European Journal of Operational Research, 55:115–119,1991. Updated version — Feb. 1994.MATHCrossRefGoogle Scholar

  • 5.

    R.E. Burkard find F. Rendl. A thermodynamically motivated simulation procedure for com-binatorial optimization problems. European Journal of Operational Research, 17: 169–174, 1984.Google Scholar

  • 6.

    J. Clausen . Announcement on Discrete Mathematics and Algorithms Network ( DIMANET ), Feb. 1994.Google Scholar

  • 7.

    Z. Drezner. Lower bounds based on linear programming for the quadratic assignment problem. Technical report, Dept. of Management Science, California State University, Fullerton, CA 92634, 1994. To appear in Computational Optimization & Applications.Google Scholar

  • 8.

    C.S. Edwards. A branch and bound algorithm for the Koopmans-Beckman quadratic assign-ment problem. Mathematical Programming Study, 13: 35–52, 1980.MATHGoogle Scholar

  • 9.

    C. Fleurent and J.A. Ferland. Genetic hybrids for the quadratic assignment problem. In P.M. Pardalos and H. Wolkowicz, editors, Quadratic assignment and related problems, volume 16 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pages 173–187. American Mathematical Society, 1994.Google Scholar

  • 10.

    R. Fourer, D.M. Gay, and B.W. Kernighan. AMPL — A modeling language for mathematical programming. The Scientific Press, South San Francisco, CA, 1993.Google Scholar

  • 11.

    R.L. Francis and J.A. White. Facility layout and location. Prentice-Hall, Englewood Cliffs, N.J., 1974.Google Scholar

  • 12.

    P.C. Gilmore. Optimal and suboptimal algorithms for the quadratic assignment problem. J. SI AM, 10: 305–313, 1962.MathSciNetMATHGoogle Scholar

  • 13.

    L.J. Hubert . Assignment methods in combinatorial data analysis. Marcel Dekker, Inc., New York, NY 10016, 1987.MATHGoogle Scholar

  • 14.

    T. Ibaraki. Theoretical comparisons of search strategies in branch-and-bound algorithms. International Journal of Computer and Information Sciences, 5 (4): 315–344, 1976.MathSciNetMATHCrossRefGoogle Scholar

  • 15.

    N.K. Karmarkar and K.G. Ramakrishnan. Computational results of an interior point algorithm for large scale linear programming. Mathematical Programming, 52: 555–586, 1991.MathSciNetMATHCrossRefGoogle Scholar

  • 16.

    T.C. Koopmans and M.J. Beckmann. Assignment problems and the location of economic activities. Econometrica, 25: 53–76, 1957.MathSciNetMATHCrossRefGoogle Scholar

  • 17.

    J. Krarup and P.M. Pruzan. Computer-aided layout design. Mathematical Programming Study, 9: 75–94, 1978.MathSciNetGoogle Scholar

  • 18.

    E.L. Lawler. The quadratic assignment problem. Management Science, 9: 586–599, 1963.MathSciNetMATHCrossRefGoogle Scholar

  • 19.

    Y. Li, P.M. Pardalos, K.G. Ramakrishnan, and M.G.C. Resende. Lower bounds for the quadratic assignment problem. Annals of Operations Research, 50: 387–410, 1994.MathSciNetMATHCrossRefGoogle Scholar

  • 20.

    Y. Li, P.M. Pardalos, and M.G.C. Resende. A greedy randomized adaptive search procedure for the quadratic assignment problem. In P.M. Pardalos and H. Wolkowicz, editors, Quadratic assignment and related problems, volume 16 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pages 237–261. American Mathematical Society, 1994.Google Scholar

  • 21.

    T. Mautor and C. Roucairol. Difficulties of exact methods for solving the quadratic assignment problem. In P.M. Pardalos and H. Wolkowicz, editors, Quadratic assignment and related problems, volume 16 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science, pages 263–274. American Mathematical Society, 1994.Google Scholar

  • 22.

    T. Mautor and C. Roucairol. A new exact algorithm for the solution of quadratic assignment problems. Discrete Applied Mathematics, 1994. To appear.Google Scholar

  • 23.

    H. Mawengkang and B.A. Murtagh. Solving nonlinear integer programs with large-scale optimization software. Annals of Operations Research, 5:425–437, 1985/6.MathSciNetGoogle Scholar

  • 24.

    E.J. McCormik. Human factors engineering. McGraw-Hill, New York, 1970.Google Scholar

  • 25.

    John E. Mitchell . Interior point algorithms for integer programming. Technical report, Rensselaer Polytechnic Institute, June 1994. To appear in Advances in linear and integer programming, Oxford University Press, 1995.Google Scholar

  • 26.

    B.A. Murtagh, T.R. Jefferson, and V. Sornprasit. A heuristic procedure for solving the quadratic assignment problem. European Journal of Operational Research, 9: 71–76, 1982.MATHCrossRefGoogle Scholar

  • 27.

    P.M. Pardalos and J. Crouse. A parallel algorithm for the quadratic assignment problem. In Proceedings of the Supercomputing 1989 Conference, pages 351–360. ACM Press, 1989.CrossRefGoogle Scholar

  • 28.

    P.M. Pardalos, K.G. Ramakrishnan, M.G.C. Resende, and Y. Li. Implementation of a variance reduction based lower bound in a branch and bound algorithm for the quadratic assignment problem. Technical report, AT & T Bell Laboratories, Murray Hill, NJ 07974, 1994.Google Scholar

  • 29.

    P.M. Pardalos and H. Wolkowicz, editors. Quadratic assignment and related problems, volume 16 of DIMACS Series on Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1994.Google Scholar

  • 30.

    M.G.C. Resende, P.M. Pardalos, and Y. Li. FORTRAN subroutines for approximate solution of dense quadratic assignment problems using GRASP. ACM Transactions on Mathematical Software, To appear.Google Scholar

  • 31.

    M.G.C. Resende, K.G. Ramakrishnan, and Z. Drezner. Computing lower bounds for the quadratic assignment problem with an interior point algorithm for linear programming. Operations Research, To appear.Google Scholar

  • 32.

    C. Roucairol. A parallel branch and bound algorithm for the quadratic assignment problem. Discrete Applied Mathematics, 18: 211–225, 1987.MathSciNetMATHCrossRefGoogle Scholar

  • 33.

    J. Skorin-Kapov. Tabu search applied to the quadratic assignment problem. ORSA Journal on Computing, 2 (l): 33–45, 1990.MATHGoogle Scholar

  • 34.

    E. Taillard. Robust tabu search for the quadratic assignment problem. Parallel Computing, 17: 443–455, 1991.MathSciNetCrossRefGoogle Scholar

  • 35.

    Thonemann, U.W. and Bolte, A.M. An improved simulated annealing algorithm for the quadratic assignment problem. Technical report, School of Business, Dept. of Production and Operations Research, University of Paderborn, Germany, 1994.Google Scholar

  • 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.publicclass Qap { // A (flow matrix).publicdouble[][] A { get; set; } // B (distance matrix).publicdouble[][] B { get; set; } // C (linear costs).publicdouble[][] C { get; set; } // Constant term.publicdouble Shift { get; set; } // Size of (A, B, C) matrices.publicint Size { get { return A == null ? 0 : A.Length; } } // Compute tr AXBX' + CX', where the permutation matrix X is determined by p.publicdouble 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:

    privatestatic 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; } privatestaticdouble[][] 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.

    publicstatic Qap Read(StreamReader reader) { string content = reader.ReadToEnd(); var tokens = content.Split(newchar[] { ' ', '\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; } thrownew InvalidDataException("Invalid QAP size."); } privatestaticdouble[][] ReadMatrix(int m, int n, string[] tokens, refint k) { if (k + m * n > tokens.Length) { thrownew 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])) { thrownew InvalidDataException("Invalid matrix entry."); } } } return matrix; }

    Like this:

    LikeLoading...

    Related

    0 thoughts on “Quadratic Assignment Problem Branch And Bound Search

    Leave a Reply

    Your email address will not be published. Required fields are marked *