Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem

DOI10.1137/0110022zbMath0118.15101OpenAlexW2049299385MaRDI QIDQ5728874

Paul C. Gilmore

Publication date: 1962

Published in: Journal of the Society for Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0110022

zbMATH Keywords

applications of probability theory and statistics

Related Items (98)

Taking advantage of symmetry in some quadratic assignment problems ⋮ Strengthening Gilmore's bound for the quadratic assignment problem ⋮ Lower bounds for the quadratic assignment problem ⋮ The facility layout problem ⋮ A new exact algorithm for the solution of quadratic assignment problems ⋮ Mathematical modeling and efficient optimization methods for the distance-dependent rearrangement clustering problem ⋮ Disentangling relationships in symptom networks using matrix permutation methods ⋮ A parallel branch and bound algorithm for the quadratic assignment problem ⋮ Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem ⋮ Lower bounding procedures for the single allocation hub location problem ⋮ The quadratic three-dimensional assignment problem: exact and approximate solution methods ⋮ A survey for the quadratic assignment problem ⋮ A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives ⋮ Variable neighborhood search for the workload balancing problem in service enterprises ⋮ A Lagrangian relaxation algorithm for sparse quadratic assignment problems ⋮ A heuristic method for the multi-story layout problem ⋮ Lower bounds and exact algorithms for the quadratic minimum spanning tree problem ⋮ Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation ⋮ Lower bounds for the quadratic assignment problem via triangle decompositions ⋮ Quadratic assignment problems ⋮ Location and layout planning. A survey ⋮ Solution methods for the balancing of jet turbines ⋮ A level-2 reformulation-linearization technique bound for the quadratic assignment problem ⋮ Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers ⋮ Optimal sequences in stochastic single machine shops ⋮ The quadratic cycle cover problem: special cases and efficient bounds ⋮ An algorithm for quadratic assignment problems ⋮ A parallel depth first search branch and bound algorithm for the quadratic assignment problem ⋮ Generating QAP instances with known optimum solution and additively decomposable cost function ⋮ Gilmore-Lawler bound of quadratic assignment problem ⋮ An efficient heuristic for the \(k\)-partitioning problem ⋮ Multiple objective programming for the quadratic assignment problem ⋮ Contributions to the quadratic assignment problem ⋮ A branch-and-bound algorithm for the single-row equidistant facility layout problem ⋮ Global optimality conditions and optimization methods for quadratic assignment problems ⋮ A quadratic simplex algorithm for primal optimization over zero-one polytopes ⋮ A branch and bound algorithm for the acyclic subgraph problem ⋮ A heuristic procedure for solving the quadratic assignment problem ⋮ Near-optimal heuristics for an assignment problem in mass storage ⋮ Heuristische Verfahren zur Lösung quadratischer Zuordnungsprobleme ⋮ Quadratic Combinatorial Optimization Using Separable Underestimators ⋮ On the quadratic assignment problem ⋮ Single and multiple period layout models for automated manufacturing systems ⋮ Exact algorithms for the solution of the grey pattern quadratic assignment problem ⋮ Convergence of a modified algorithm of fast probabilistic modeling ⋮ Constrained 0-1 quadratic programming: basic approaches and extensions ⋮ Website structure improvement: quadratic assignment problem approach and ant colony meta-heuristic technique ⋮ A generalized Gilmore-Lawler procedure for the quadratic assignment problem ⋮ Experimental analysis of crossover and mutation operators on the quadratic assignment problem ⋮ A location problem on unicyclic networks: Balanced case ⋮ Simulated annealing for machine layout problems in the presence of zoning constraints ⋮ Layout design for flexible manufacturing systems ⋮ A distance assignment approach to the facility layout problem ⋮ Computational performance and efficiency of lower-bound procedures for the dynamic facility layout problem ⋮ Mapping the convergence of genetic algorithms ⋮ The quadratic shortest path problem: complexity, approximability, and solution methods ⋮ Generating quadratic assignment test problems with known optimal permutations ⋮ Algorithms for robust single and multiple period layout planning for manufacturing systems ⋮ FALSA-facilities allocation by statistical analysis Part I. Further investigations on the cost distribution associated with the problem of facilities design ⋮ FALSA-Facilities allocation by statistical analysis Part II. An heuristic algorithm to the problem of facilities design ⋮ RLT insights into lift-and-project closures ⋮ A ‘fuzzy’ heuristic for the quadratic assignment formulation to the facility layout problem ⋮ Reconfigurable layout problem ⋮ Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing ⋮ The QAP-polytope and the star transformation ⋮ Effective formulation reductions for the quadratic assignment problem ⋮ The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm ⋮ A new relaxation framework for quadratic assignment problems based on matrix splitting ⋮ Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem ⋮ A hybrid heuristic for the facilities layout problem ⋮ A parallel heuristic for quadratic assignment problems ⋮ Single- and multi-objective facility layout with workflow interference considerations ⋮ Cotas inferiores para el QAP-Arbol ⋮ A contribution to quadratic assignment problems ⋮ An algorithm for the quadratic assignment problem using Benders' decomposition ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting ⋮ A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices ⋮ A convex form of the quadratic assignment problem ⋮ Lower bounds based on linear programming for the quadratic assignment problem ⋮ A neural network approach to facility layout problems ⋮ Optimizing simulated annealing schedules with genetic programming ⋮ The linearization problem of a binary quadratic problem and its applications ⋮ A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases ⋮ Network-based formulations of the quadratic assignment problem ⋮ Lower bounds for nonlinear assignment problems using many body interactions ⋮ An optimal tree search method for the manufacturing systems cell formation problem ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems ⋮ Move based heuristics for the unidirectional loop network layout problem ⋮ A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method ⋮ Semantic relatedness ⋮ A new linearization method for quadratic assignment problems ⋮ Exact Solution of Two Location Problems via Branch-and-Bound ⋮ A variant of time minimizing assignment problem ⋮ An exact algorithm for the general quadratic assignment problem ⋮ A heuristic for cyclic stochastic sequencing of tasks on a drum-like storage system ⋮ Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation ⋮ Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods

This page was built for publication: Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem