An Exact Algorithm for the Quadratic Assignment Problem on a Tree

DOI10.1287/OPRE.37.5.760MaRDI QIDQ4732306zbMATH OpenOpenAlexFDO

Authors Enrique Benavent, Nicos Christofides

Publication date 1989

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1287/opre.37.5.760

zbMATH Keywords

NP-completebranch-and-boundQuadratic Assignment Problempolynomial boundTraveling SalesmanLangrangian relaxation

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Programming involving graphs or networks (90C35) Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39) Integer programming (90C10)

Recommendations

• Dynamic programming for the quadratic assignment problem on trees
• An exact algorithm for the general quadratic assignment problem
• scientific article; zbMATH DE number 2049005
• A new exact algorithm for the solution of quadratic assignment problems
• A Lagrangian relaxation algorithm for sparse quadratic assignment problems

Cited in

(22)

• scientific article; zbMATH DE number 708857 (Why is no real title available?)
• A greedy genetic algorithm for the quadratic assignment problem
• Semidefinite programming approach for the quadratic assignment problem with a sparse graph
• Global optimality conditions and optimization methods for quadratic assignment problems
• scientific article; zbMATH DE number 2049010 (Why is no real title available?)
• A survey for the quadratic assignment problem
• An efficient algorithm for unequal area facilities layout planning with input and output points
• Quadratic assignment problems on series-parallel digraphs
• Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem
• A branch-and-bound algorithm for the single-row equidistant facility layout problem
• On a quadratic programming problem involving distances in trees
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• A nonmonotone GRASP
• Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles
• A mathematical model and a heuristic procedure for the turbine balancing problem
• An experimental study of variable depth search algorithms for the quadratic assignment problem
• scientific article; zbMATH DE number 2049005 (Why is no real title available?)
• A Lagrangian relaxation algorithm for sparse quadratic assignment problems
• A mixed-integer programming formulation for optimizing the double row layout problem
• Convergence of the surrogate Lagrangian relaxation method
• Continuation methods for approximate large scale object sequencing
• Dynamic programming for the quadratic assignment problem on trees

This page was built for publication: An Exact Algorithm for the Quadratic Assignment Problem on a Tree

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