A survey for the quadratic assignment problem

DOI10.1016/J.EJOR.2005.09.032zbMath1103.90058OpenAlexW2013603106MaRDI QIDQ852928

Peter M. Hahn, Paulo Oswaldo Boaventura-Netto, Nair Maria Maia De Abreu, Eliane Maria Loiola, 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

zbMATH Keywords

integer programmingcombinatorial optimizationmetaheuristicsbranch and boundassignmentfacilities planning and design

Mathematics Subject Classification ID

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

Related Items (only showing first 100 items - show all)

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 ⋮ A relative position-coded differential evolution for loop-based station sequencing problem ⋮ The generalised machine layout problem ⋮ SIMD tabu search for the quadratic assignment problem with graphics hardware acceleration ⋮ An improved heuristic approach for multi-objective facility layout problem ⋮ Copositive and semidefinite relaxations of the quadratic assignment problem ⋮ A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ Mathematical modeling and efficient optimization methods for the distance-dependent rearrangement clustering problem ⋮ A cooperative parallel tabu search algorithm for the quadratic assignment problem ⋮ On the geometry of graph spaces ⋮ Evolutionary decision-makings for the dynamic weapon-target assignment problem ⋮ Single row layout models ⋮ Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO ⋮ Exact Recovery with Symmetries for the Doubly Stochastic Relaxation ⋮ Tabu search vs. simulated annealing as a function of the size of quadratic assignment problem instances ⋮ An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes ⋮ Survey of quantitative methods in construction ⋮ Improved exact approaches for row layout problems with departments of equal length ⋮ A nonmonotone GRASP ⋮ On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study ⋮ An efficient continuation method for quadratic assignment problems ⋮ A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems ⋮ Fast simulated annealing for single-row equidistant facility layout ⋮ Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers ⋮ Structured linear reformulation of binary quadratically constrained quadratic programs ⋮ Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach ⋮ A survey of hidden convex optimization ⋮ Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic \(0-1\) optimization problems with linear constraints ⋮ New variable-length data compression scheme for solution representation of meta-heuristics ⋮ Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2 ⋮ A new exact discrete linear reformulation of the quadratic assignment problem ⋮ The multi-story space assignment problem ⋮ Comparative performance of tabu search and simulated annealing heuristics for the quadratic assignment problem ⋮ Minimum energy configurations on a toric lattice as a quadratic assignment problem ⋮ Locating names on vertices of a transaction network ⋮ Generating QAP instances with known optimum solution and additively decomposable cost function ⋮ Decorous combinatorial lower bounds for row layout problems ⋮ A New Neighborhood for the QAP ⋮ Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town? ⋮ An efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems ⋮ A semidefinite optimization approach to the target visitation problem ⋮ An exact qubit allocation approach for NISQ architectures ⋮ Garden optimization problems for benchmarking quantum annealers ⋮ Dual track and segmented single track bidirectional loop guidepath layout for AGV systems ⋮ A branch-and-bound algorithm for the single-row equidistant facility layout problem ⋮ Global optimality conditions and optimization methods for quadratic assignment problems ⋮ MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems ⋮ An implementation of the iterated tabu search algorithm for the quadratic assignment problem ⋮ Global optimization of a class of nonconvex quadratically constrained quadratic programming problems ⋮ Linear and quadratic programming approaches for the general graph partitioning problem ⋮ Optimal rates of statistical seriation ⋮ A splitting method for orthogonality constrained problems ⋮ Complete description for the spanning tree problem with one linearised quadratic term ⋮ The random quadratic assignment problem ⋮ Generating constrained length personalized bicycle tours ⋮ An improved linearization strategy for zero-one quadratic programming problems ⋮ An exact algorithm for the minimum squared load assignment problem ⋮ Exact solution of emerging quadratic assignment problems ⋮ Continuation methods for approximate large scale object sequencing ⋮ On improving convex quadratic programming relaxation for the quadratic assignment problem ⋮ An experimental study of variable depth search algorithms for the quadratic assignment problem ⋮ Website structure improvement: quadratic assignment problem approach and ant colony meta-heuristic technique ⋮ Semidefinite programming approach for the quadratic assignment problem with a sparse graph ⋮ An efficient variable neighborhood search for the space-free multi-row facility layout problem ⋮ Random assignment problems ⋮ Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions ⋮ New special cases of the quadratic assignment problem with diagonally structured coefficient matrices ⋮ ANTIGONE: algorithms for coNTinuous/Integer global optimization of nonlinear equations ⋮ Embedding signed graphs in the line ⋮ New linearizations of quadratic assignment problems ⋮ Discrete and geometric branch and bound algorithms for~medical image registration ⋮ The dynamic space allocation problem: applying hybrid GRASP and tabu search metaheuristics ⋮ A TISSUE P SYSTEM BASED SOLUTION TO QUADRATIC ASSIGNMENT PROBLEM ⋮ Effective formulation reductions for the quadratic assignment problem ⋮ Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique ⋮ A new relaxation framework for quadratic assignment problems based on matrix splitting ⋮ Relaxations for Minimizing Metric Distortion and Elastic Energies for 3D Shape Matching ⋮ QPLIB: a library of quadratic programming instances ⋮ Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search ⋮ Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems ⋮ A fast algorithm to generate feasible solution of production facilities layout based on plane segmentation ⋮ An algorithm for the generalized quadratic assignment problem ⋮ Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting ⋮ Using constraint programming for the design of network-on-chip architectures ⋮ Combining and solving sequence dependent traveling salesman and quadratic assignment problems in PCB assembly ⋮ New exact approaches to row layout problems ⋮ A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem ⋮ Image matching from handcrafted to deep features: a survey ⋮ Matroid optimization problems with monotone monomials in the objective ⋮ $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices ⋮ A Novel SDP Relaxation for the Quadratic Assignment Problem Using Cut Pseudo Bases ⋮ CONVEX HULL PRESENTATION OF A QUADRATICALLY CONSTRAINED SET AND ITS APPLICATION IN SOLVING QUADRATIC PROGRAMMING PROBLEMS ⋮ Robust optimization of internal transports at a parcel sorting center operated by Deutsche Post world net ⋮ Scalable Semidefinite Programming ⋮ Linear programming insights into solvable cases of the quadratic assignment problem ⋮ A revised reformulation-linearization technique for the quadratic assignment problem ⋮ Who should get vaccinated? Individualized allocation of vaccines over SIR network ⋮ Finding optimal solutions to several gray pattern instances

Uses Software

• GRASP_QAP
• SDP_S
• Unnamed Item
• Unnamed Item

Cites Work

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

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