The quadratic assignment problem. Theory and algorithms
From MaRDI portal
Publication:1377989
zbMath0909.90226MaRDI QIDQ1377989
Publication date: 4 February 1998
Published in: Combinatorial Optimization (Search for Journal in Brave)
heuristicsasymptotic behaviourquadratic assignment problemlower boundscutting planesQAPMonge matricesBiQAPbiquadratic assignment problemsolvable cases
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items (92)
Linearizable special cases of the QAP ⋮ BRANCHING TECHNIQUE FOR A BI-OBJECTIVE TWO-STAGE ASSIGNMENT PROBLEM ⋮ Copositive and semidefinite relaxations of the quadratic assignment problem ⋮ The extended concentric tabu for the quadratic assignment problem ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Effect of transformations of numerical parameters in automatic algorithm configuration ⋮ A cooperative parallel tabu search algorithm for the quadratic assignment problem ⋮ Solution methods for the bi-objective (cost-coverage) unconstrained facility location problem with an illustrative example ⋮ The bipartite quadratic assignment problem and extensions ⋮ A quadra-directional decomposition heuristic for a two-dimensional, non-equidistant machine-cell location problem ⋮ A game-theoretic algorithm for non-linear single-path routing problems ⋮ A survey for the quadratic assignment problem ⋮ Assignment problems: a golden anniversary survey ⋮ Detailed layout planning for irregularly-shaped machines with transportation path design ⋮ Tabu search vs. simulated annealing as a function of the size of quadratic assignment problem instances ⋮ A note on a polynomial time solvable case of the quadratic assignment problem ⋮ An efficient continuation method for quadratic assignment problems ⋮ A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems ⋮ The quadratic minimum spanning tree problem and its variations ⋮ Bounds for the quadratic assignment problem using the bundle method ⋮ Resource assignment with preference conditions ⋮ The Rank-One Quadratic Assignment Problem ⋮ The quadratic knapsack problem -- a survey ⋮ Optimal role and position assignment in multi-robot freely reachable formations ⋮ Biologically inspired parent selection in genetic algorithms ⋮ A hybrid method integrating an elite genetic algorithm with tabu search for the quadratic assignment problem ⋮ Aligning random graphs with a sub-tree similarity message-passing algorithm ⋮ Comparative performance of tabu search and simulated annealing heuristics for the quadratic assignment problem ⋮ Locating names on vertices of a transaction network ⋮ Generating QAP instances with known optimum solution and additively decomposable cost function ⋮ The bilinear assignment problem: complexity and polynomially solvable special cases ⋮ Better Process Mapping and Sparse Quadratic Assignment ⋮ Selection hyper-heuristics for the multi and many-objective quadratic assignment problem ⋮ Gilmore-Lawler bound of quadratic assignment problem ⋮ An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems ⋮ A parallel water flow algorithm with local search for solving the quadratic assignment problem ⋮ Characterizing linearizable QAPs by the level-1 reformulation-linearization technique ⋮ Distribution functions, extremal limits and optimal transport ⋮ A new greedy algorithm for the quadratic assignment problem ⋮ An LP-based characterization of solvable QAP instances with chess-board and graded structures ⋮ The multi-stripe travelling salesman problem ⋮ Global optimization of a class of nonconvex quadratically constrained quadratic programming problems ⋮ A novel approach to fault tolerant multichannel networks designing problems ⋮ Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study ⋮ Extending time‐to‐target plots to multiple instances ⋮ Revisiting simulated annealing: a component-based analysis ⋮ The random quadratic assignment problem ⋮ Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis ⋮ Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters ⋮ Weighted Optimization with Thresholding for Complete-Case Analysis ⋮ Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem ⋮ The Wiener maximum quadratic assignment problem ⋮ Two classes of quadratic assignment problems that are solvable as linear assignment problems ⋮ Continuation methods for approximate large scale object sequencing ⋮ Exact algorithms for the solution of the grey pattern quadratic assignment problem ⋮ Graph Similarity and Approximate Isomorphism ⋮ On improving convex quadratic programming relaxation for the quadratic assignment problem ⋮ A branch-and-bound algorithm for the minimum cost bipartite perfect matching problem with conflict pair constraints ⋮ Constrained 0-1 quadratic programming: basic approaches and extensions ⋮ Random assignment problems ⋮ Conformal Wasserstein distance: II. computational aspects and extensions ⋮ Mapping the convergence of genetic algorithms ⋮ New special cases of the quadratic assignment problem with diagonally structured coefficient matrices ⋮ Another well-solvable case of the QAP: maximizing the job completion time variance ⋮ Embedding signed graphs in the line ⋮ New linearizations of quadratic assignment problems ⋮ Approximate solutions to the turbine balancing problem. ⋮ Selected topics on assignment problems ⋮ Discrete location problems with push-pull objectives ⋮ Conformal Wasserstein distances: comparing surfaces in polynomial time ⋮ Dynamic programming for the quadratic assignment problem on trees ⋮ Compounded genetic algorithms for the quadratic assignment problem ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ A New Tractable Case of the QAP with a Robinson Matrix ⋮ Effective formulation reductions for the quadratic assignment problem ⋮ Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique ⋮ A divide-and-conquer local search heuristic for data visualization ⋮ Random walk's correlation function for multi-objective NK landscapes and quadratic assignment problem ⋮ COSEARCH: A parallel cooperative metaheuristic ⋮ Hybrid population-based algorithms for the bi-objective quadratic assignment problem ⋮ On the use of fitness landscape features in meta-learning based algorithm selection for the quadratic assignment problem ⋮ SDP Relaxations for Some Combinatorial Optimization Problems ⋮ Global Approaches for Facility Layout and VLSI Floorplanning ⋮ Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems ⋮ A new linearization method for quadratic assignment problems ⋮ A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices ⋮ Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach ⋮ Linear programming insights into solvable cases of the quadratic assignment problem ⋮ Four-point conditions for the TSP: the complete complexity classification ⋮ Minimum Congestion Mapping in a Cloud ⋮ Well-solvable cases of the QAP with block-structured matrices ⋮ Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
Uses Software
This page was built for publication: The quadratic assignment problem. Theory and algorithms
