A survey for the quadratic assignment problem

DOI10.1016/J.EJOR.2005.09.032zbMATH Open1103.90058OpenAlexW2013603106MaRDI QIDQ852928FDOQ852928

Authors: Eliane Maria Loiola, Nair Abreu, Paulo Oswaldo Boaventura-Netto, Peter M. Hahn, Tania M. Querido 

Publication date: 15 November 2006

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2005.09.032

Recommendations

• scientific article; zbMATH DE number 714526
• A contribution to quadratic assignment problems
• The quadratic assignment problem. Theory and algorithms
• Recent approaches to the quadratic assignment problem
• An algorithm for quadratic assignment problems
• A new form of the quadratic assignment problem and approximate solutions
• Recent advances in the solution of quadratic assignment problems
• An Algorithm for the Quadratic Assignment Problem

zbMATH Keywords

combinatorial optimizationmetaheuristicsinteger programmingassignmentbranch and boundfacilities planning and design

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Integer programming (90C10) Discrete location and assignment (90B80)

Cites Work

• QAPLIB - a quadratic assignment problem library
• Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP
• QAPLIB-A quadratic assignment problem library
• Ant colonies for the quadratic assignment problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimization by simulated annealing
• Approximation algorithms for multi-dimensional assignment problems with decomposable costs
• Approximation algorithms for three-dimensional assignment problems with triangle inequalities
• Facets of the three-index assignment polytope
• An Algorithm for Solving 3-Dimensional Assignment Problems with Application to Scheduling a Teaching Practice
• A bilinear programming formulation of the 3-dimensional assignment problem
• Letter to the Editor—The Multidimensional Assignment Problem
• The Distribution of Values in the Quadratic Assignment Problem
• A classification of formulations for the (time-dependent) traveling salesman problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Tabu Search—Part I
• Computational results of an interior point algorithm for large scale linear programming
• A solvable case of the quadratic assignment problem
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• The quadratic assignment problem. Theory and algorithms
• Three-dimensional axial assignment problems with decomposable cost coefficients
• Assignment Problems and the Location of Economic Activities
• Title not available (Why is that?)
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Selected topics on assignment problems
• Copositive and semidefinite relaxations of the quadratic assignment problem
• Variable neighborhood search
• An ant colony system for permutation flow-shop sequencing
• Title not available (Why is that?)
• Comparison of iterative searches for the quadratic assignment problem
• Title not available (Why is that?)
• An extreme point algorithm for a local minimum solution to the quadratic assignment problem
• Title not available (Why is that?)
• P-Complete Approximation Problems
• Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
• The quadratic assignment problem in the context of the printed circuit board assembly process
• Title not available (Why is that?)
• On the quadratic assignment problem
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Semidefinite programming relaxations for the quadratic assignment problem
• Greedy randomized adaptive search procedures
• Complexity of a 3-dimensional assignment problem
• Iterated local search for the quadratic assignment problem
• Tabu Search—Part II
• Title not available (Why is that?)
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• Backtracking of jobs in one-dimensional machine location problems
• Directional decomposition heuristic for a linear machine-cell location problem.
• A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices
• Tabu Search Applied to the Quadratic Assignment Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Locating cells with bottleneck machines in cellular manufacturing systems
• Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing
• A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem
• Recent advances in the solution of quadratic assignment problems
• A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
• Metaheuristics: A bibliography
• Lower bounds for the quadratic assignment problem based upon a dual formulation
• The quadratic assignment problem
• On Solving A One-Dimensional Space Allocation Problem With Integer Programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Evolutionary Computation in Combinatorial Optimization
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• A parallel branch and bound algorithm for the quadratic assignment problem
• Algodesk: An experimental comparison of eight evolutionary heuristics applied to the quadratic assignment problem
• Application of the simulated annealing algorithm to the combinatorial optimization problem with permutation property: An investigation of generation mechanism
• Simulated annealing and tabu search in the long run: A comparison on QAP tasks
• A study of diversification strategies for the quadratic assignment problem
• A genetic approach to the quadratic assignment problem
• Simulated annealing and genetic algorithms for the facility layout problem: A survey
• Hope: A genetic algorithm for the unequal area facility layout problem.
• Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices.
• Intelligent local search strategies for solving facility layout problems with the quadratic assignment problem formulation
• From linear to semidefinite programming: an algorithm to obtain semidefinite relaxations for bivalent quadratic problems
• Solving large quadratic assignment problems on computational grids
• A new genetic algorithm for the quadratic assignment problem
• The Backboard Wiring Problem: A Placement Algorithm
• Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/LP Approach
• Hospital Layout as a Quadratic Assignment Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Improved Constructive Multistart Strategies for the Quadratic Assignment Problem Using Adaptive Memory
• An Exact Algorithm for the Quadratic Assignment Problem on a Tree
• An improved annealing scheme for the QAP
• A thermodynamically motivated simulation procedure for combinatorial optimization problems
• Generating quadratic assignment test problems with known optimal permutations
• A GRASP for the biquadratic assignment problem
• Title not available (Why is that?)
• A parallel depth first search branch and bound algorithm for the quadratic assignment problem
• A New Lower Bound for the Quadratic Assignment Problem
• Title not available (Why is that?)
• Evolutionary Computation in Combinatorial Optimization
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Title not available (Why is that?)
• Approximate solutions to the turbine balancing problem.
• Ranking scalar products to improve bounds for the quadratic assignment problem
• Tabu search and design optimization
• Title not available (Why is that?)
• Title not available (Why is that?)
• An asymptotically exact polynomial algorithm for equipartition problems
• Solutions for the constrained dynamic facility layout problem
• Simple approaches to parallel branch and bound
• Mechanisms for local search
• A neural network approach to facility layout problems
• Solving large-scale QAP problems in parallel with the serach library ZRAM
• A parallel adaptive tabu search approach
• Network-based formulations of the quadratic assignment problem
• Lower bounds for nonlinear assignment problems using many body interactions
• Strengthening Gilmore's bound for the quadratic assignment problem
• Large-scale layout of facilities using a heuristic hybrid algorithm
• Solution methods for the balancing of jet turbines
• Solution procedures for the dynamic facility layout problem
• Fast equi-partitioning of rectangular domains using stripe decomposition
• A novel chaotic search for quadratic assignment problems
• Approximating the maximum quadratic assignment problem
• Room allocation: a polynomial subcase of the quadratic assignment problem
• Lower bounds based on linear programming for the quadratic assignment problem
• Extensive testing of a hybrid genetic algorithm for solving quadratic assignment problems
• Generating hard test instances with known optimal solution for the rectilinear quadratic assignment problem
• Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach
• A modification of threshold accepting and its application to the quadratic assignment problem
• Parallel genetic algorithms with local search
• A parallel heuristic for quadratic assignment problems
• Improved lower bounds for the quadratic assignment problem
• A divide-and-conquer local search heuristic for data visualization
• Implementation of a Variance Reduction-Based Lower Bound in a Branch-and-Bound Algorithm for the Quadratic Assignment Problem
• Title not available (Why is that?)
• A new formulation of the quadratic assignment problem on r-dimensional grid
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Use of Specially Structured Models for Obtaining Bounds in the Quadratic Assignment Problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An n‐step, 2‐variable search algorithm for the component placement problem
• Title not available (Why is that?)
• Quadratic assignment problem QAP with adaptable material handling devices
• A hybrid approach for concurrent layout design of cells and their flow paths in a tree configuration
• Redinv-SA: la simulated annealing for the quadratic assignment problem
• Title not available (Why is that?)
• Parallel Ant Colonies for the quadratic assignment problem
• The quadratic assignment problem with a monotone anti-monge and a symmetric toeplitz matrix: Easy and hard cases
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Lagrangean Relaxation Approach for a Turbine Design Quadratic Assignment Problem
• Heuristics from Nature for Hard Combinatorial Optimization Problems
• Evolutionary Computation in Combinatorial Optimization
• A deterministic annnealing algorithm for a combinatorial optimization problem using replicator equations
• Best reduction of the quadratic semi-assignment problem
• Quadratic assignment problems and \(M/G/C/C/\) state dependent network flows
• Box-inequalities for quadratic assignment polytopes
• Doubly constrained network for combinatorial optimization
• A branch and bound method for solving the bidirectional circular layout problem
• Un Algorithme De Génération De Coupes Pour Le Problème De L’Affectation Quadratique
• An algorithm for the quadratic assignment problem using Benders' decomposition
• A greedy genetic algorithm for the quadratic assignment problem
• An Algorithm for the Three-Index Assignment Problem
• Quadratic assignment problems
• Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
• On Latin squares and the facial structure of related polytopes
• On the classification of NP-complete problems in terms of their correlation coefficient
• Multi colony ant algorithms
• One-dimensional machine location problems in a multi-product flowline with equidistant locations
• A quadratic assignment formulation of the molecular conformation problem
• Lower bounds for the quadratic assignment problem via triangle decompositions
• QUADRATIC ASSIGNMENT AS A GENERAL DATA ANALYSIS STRATEGY
• On the landscape ruggedness of the quadratic assignment problem
• A heuristic for quadratic Boolean programs with applications to quadratic assignment problems
• Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem
• On the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem
• Numerical investigations on quadratic assignment problems
• Bounds on the Performance of Vector-Quantizers Under Channel Errors
• Heuristics for biquadratic assignment problems and their computational comparison
• Optimizing simulated annealing schedules with genetic programming
• A tabu search algorithm for the quadratic assignment problem
• The extended concentric tabu for the quadratic assignment problem
• Strong duality for a trust-region type relaxation of the quadratic assignment problem
• Title not available (Why is that?)
• A Review of the Placement and Quadratic Assignment Problems
• Applying an extended guided local search to the quadratic assignment problem
• On the quality of local search for the quadratic assignment problem
• Polynomial approximation algorithms for the TSP and the QAP with a factorial domination number
• Title not available (Why is that?)
• Solving quadratic assignment problems with rectangular distances and integer programming
• Tree-search algorithms for quadratic assignment problems
• Adaptive memory programming: a unified view of metaheuristics
• Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
• Lower bounds for the quadratic assignment problem
• Solving quadratic assignment problems using convex quadratic programming relaxations
• A New Lower Bound Via Projection for the Quadratic Assignment Problem
• A new bound for the quadratic assignment problem based on convex quadratic programming
• Efficient genetic algorithms using simple genes exchange local search policy for the quadratic assignment problem
• A performance guarantee heuristic for electronic components placement problems including thermal effects
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• Lagrangean decomposition for integer nonlinear programming with linear constraints
• An algorithm for the planar three-index assignment problem
• Tabu search for the planar three-index assignment problem
• Title not available (Why is that?)
• An algorithm for the multiprocessor assignment problem
• A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method
• On the quality of heuristic solutions to a 19\(\times 19\) quadratic assignment problem
• The quadratic three-dimensional assignment problem: exact and approximate solution methods
• Title not available (Why is that?)
• On random quadratic bottleneck assignment problems
• A Graph Theoretic Analysis of Bounds for the Quadratic Assignment Problem
• An exact branch-and-bound procedure for the quadratic-assignment problem
• An Algorithm for the Quadratic Assignment Problem
• Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem
• An algorithm for quadratic assignment problems
• Extensions of a tabu search adaptation to the quadratic assignment problem
• Modeling and Analysis of Congestion in the Design of Facility Layouts
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Lagrangian relaxation algorithm for sparse quadratic assignment problems
• Compounded genetic algorithms for the quadratic assignment problem
• A new Lagrangian relaxation based algorithm for a class of multidimensional assignment problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Asymptotic Properties of the Quadratic Assignment Problem
• Special cases of the quadratic assignment problem
• Solving large quadratic assignment problems in parallel
• Symmetrization of nonsymmetric quadratic assignment problems and the Hoffman-Wielandt inequality
• On lower bounds for a class of quadratic 0,1 programs
• Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems
• An optimal tree search method for the manufacturing systems cell formation problem
• Location, scheduling, design and integer programming
• On the applicability of lower bounds for solving rectilinear quadratic assignment problems in parallel
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• Linear-time separation algorithms for the three-index assignment polytope
• A dual framework for lower bounds of the quadratic assignment problem based on linearization
• Massively parallel tabu search for the quadratic assignment problem
• Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem
• On the SQAP-polytope
• Title not available (Why is that?)
• Title not available (Why is that?)
• A branch and bound algorithm for the Koopmans-Beckmann quadratic assignment problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The QAP-polytope and the star transformation
• Move based heuristics for the unidirectional loop network layout problem
• Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
• Title not available (Why is that?)
• Contributions to the quadratic assignment problem
• An exact algorithm for the general quadratic assignment problem
• A new exact algorithm for the solution of quadratic assignment problems
• A branch-and-bound-based heuristic for solving the quadratic assignment problem
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• A memetic heuristic for the generalized quadratic assignment problem
• A cooperative parallel tabu search algorithm for the quadratic assignment problem
• A new exact discrete linear reformulation of the quadratic assignment problem
• On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study
• QPLIB: a library of quadratic programming instances
• An improved linearization strategy for zero-one quadratic programming problems
• A survey of meta-heuristic solution methods for the quadratic assignment problem
• New linearizations of quadratic assignment problems
• Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
• Evolutionary decision-makings for the dynamic weapon-target assignment problem
• Copositive and semidefinite relaxations of the quadratic assignment problem
• A deterministic annealing algorithm for approximating a solution of the min-bisection problem
• A hybrid biased random key genetic algorithm for the quadratic assignment problem
• An efficient continuation method for quadratic assignment problems
• Global optimality conditions and optimization methods for quadratic assignment problems
• Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach
• Linear programming insights into solvable cases of the quadratic assignment problem
• The quadratic assignment problem. Theory and algorithms
• A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• A splitting method for orthogonality constrained problems
• A note on asymptotic properties of the quadratic assignment problem
• A survey of hidden convex optimization
• An implementation of the iterated tabu search algorithm for the quadratic assignment problem
• A flexible, polynomial-time, construction and improvement heuristic for the quadratic assignment problem
• The multi-story space assignment problem
• Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting
• A semidefinite optimization approach to the target visitation problem
• Discrete and geometric branch and bound algorithms for~medical image registration
• On the geometry of graph spaces
• Single row layout models
• Tabu search vs. simulated annealing as a function of the size of quadratic assignment problem instances
• Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach
• Website structure improvement: quadratic assignment problem approach and ant colony meta-heuristic technique
• A branch-and-bound algorithm for the single-row equidistant facility layout problem
• Random assignment problems
• An algorithm for the generalized quadratic assignment problem
• Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique
• Title not available (Why is that?)
• Generating QAP instances with known optimum solution and additively decomposable cost function
• SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration
• Asymptotic Properties of the Quadratic Assignment Problem
• Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO
• Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions
• \(L_p\)-norm regularization algorithms for optimization over permutation matrices
• A hybrid ant colony optimization algorithm for solving facility layout problems formulated as quadratic assignment problems
• Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town?
• Combining and solving sequence dependent traveling salesman and quadratic assignment problems in PCB assembly
• An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes
• Complete description for the spanning tree problem with one linearised quadratic term
• A Branch-and-Bound Algorithm for Team Formation on Social Networks
• To lay out or not to lay out?
• Comparative performance of tabu search and simulated annealing heuristics for the quadratic assignment problem
• A nonmonotone GRASP
• ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations
• Title not available (Why is that?)
• Fast simulated annealing for single-row equidistant facility layout
• Exact solution of emerging quadratic assignment problems
• Recent advances in the solution of quadratic assignment problems
• Global optimization of a class of nonconvex quadratically constrained quadratic programming problems
• Mathematical modeling and efficient optimization methods for the distance-dependent rearrangement clustering problem
• On improving convex quadratic programming relaxation for the quadratic assignment problem
• Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers
• The random quadratic assignment problem
• Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study
• A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem
• An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems
• Continuation methods for approximate large scale object sequencing
• Linear and quadratic programming approaches for the general graph partitioning problem
• A new relaxation framework for quadratic assignment problems based on matrix splitting
• Effective formulation reductions for the quadratic assignment problem
• A revised reformulation-linearization technique for the quadratic assignment problem
• Sharing in construction projects -- on determining optimal container assignments for the on-site accommodation of trades
• Generating constrained length personalized bicycle tours
• Who should get vaccinated? Individualized allocation of vaccines over SIR network
• Embedding signed graphs in the line
• A new class of hard problem instances for the 0-1 knapsack problem
• An exact algorithm for the minimum squared load assignment problem
• Structured linear reformulation of binary quadratically constrained quadratic programs
• Fairer comparisons for travelling salesman problem solutions using hash functions
• Finding optimal solutions to several gray pattern instances
• Decorous combinatorial lower bounds for row layout problems
• Robust optimization of internal transports at a parcel sorting center operated by Deutsche Post world net
• Image Keypoint Matching Using Graph Neural Networks
• New exact approaches to row layout problems
• A tissue P system based solution to quadratic assignment problem
• Semidefinite programming approach for the quadratic assignment problem with a sparse graph
• The ‘Idiot’ crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems
• An exact qubit allocation approach for NISQ architectures
• An efficient variable neighborhood search for the space-free multi-row facility layout problem
• Using constraint programming for the design of network-on-chip architectures
• New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
• An LP-based characterization of solvable QAP instances with chess-board and graded structures
• The dynamic space allocation problem: applying hybrid GRASP and tabu search metaheuristics
• A note on the exact solution of the minimum squared load assignment problem
• A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique
• Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs
• Garden optimization problems for benchmarking quantum annealers
• An efficient algorithm for unequal area facilities layout planning with input and output points
• A New Neighborhood for the QAP

Uses Software

• QAPLIB
• ZRAM
• GRASP_QAP
• SDP_S

This page was built for publication: A survey for the quadratic assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q852928)