An exact algorithm for the general quadratic assignment problem
From MaRDI portal
We develop an algorithm that is based on the linearization and decomposition of a general quadratic assignment problem of size n into \(n^ 2\) linear assignment problems of size (n-1). The solutions to these subproblems are used to calculate a lower bound for the original problem, and this bound is then used in an exact branch and bound procedure. These subproblems are similar to the 'minors' defined by Lawler, but permit us to calculate tighter bounds. Computational experience is given for solution to optimality of general quadratic assignment problems of sizes up to \(n=10\).
Recommendations
- A new exact algorithm for the solution of quadratic assignment problems
- scientific article; zbMATH DE number 4143776
- Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique
- scientific article; zbMATH DE number 1302195
- An algorithm for the generalized quadratic assignment problem
Cites work
- An Algorithm for the Quadratic Assignment Problem
- An algorithm for the quadratic assignment problem using Benders' decomposition
- Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
- Assignment Problems and the Location of Economic Activities
- Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem
- scientific article; zbMATH DE number 3633982 (Why is no real title available?)
- scientific article; zbMATH DE number 3440185 (Why is no real title available?)
- Numerical investigations on quadratic assignment problems
- Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
- The Backboard Wiring Problem: A Placement Algorithm
- The Efficiency of Computer Algorithms for Plant Layout
- The quadratic assignment problem
- The Quadratic Assignment Problem: An Experimental Evaluation of Solution Strategies
- Time-slot assignment for TDMA-systems
- Tree-search algorithms for quadratic assignment problems
Cited in
(32)- An algorithm for the generalized quadratic assignment problem
- The facility layout problem
- Single and multiple period layout models for automated manufacturing systems
- Computational performance and efficiency of lower-bound procedures for the dynamic facility layout problem
- Network-based formulations of the quadratic assignment problem
- Strengthening Gilmore's bound for the quadratic assignment problem
- A new exact algorithm for the solution of quadratic assignment problems
- The quadratic assignment problem. Theory and algorithms
- A heuristic procedure for the single-row facility layout problem
- FaSa: A fast and stable quadratic placement algorithm
- An exact algorithm for the minimum squared load assignment problem
- An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations
- Room allocation: a polynomial subcase of the quadratic assignment problem
- A performance guarantee heuristic for electronic components placement problems including thermal effects
- The quadratic assignment problem. II: Refined Gilmore-Lawler algorithm
- A hybrid heuristic for the facilities layout problem
- The quadratic three-dimensional assignment problem: exact and approximate solution methods
- General forms of the quadratic assignment problem
- A genetic algorithm and queuing theory based methodology for facilities layout problem
- scientific article; zbMATH DE number 7234393 (Why is no real title available?)
- scientific article; zbMATH DE number 4143776 (Why is no real title available?)
- A solution method for the quadratic assignment problem based on the Hungarian algorithm
- A Relaxed Assignment Algorithm For The Quadratic Assignement Problem
- Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem
- An Exact Penalty Approach to the Quadratic Assignment Problem
- Locating cells with bottleneck machines in cellular manufacturing systems
- An Exact Algorithm for the Quadratic Assignment Problem on a Tree
- Exact algorithms for the solution of the grey pattern quadratic assignment problem
- scientific article; zbMATH DE number 2200751 (Why is no real title available?)
- Efficient models for the facility layout problem
- A survey for the quadratic assignment problem
- Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique
This page was built for publication: An exact algorithm for the general quadratic assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1067975)
