An Exact Algorithm for the Quadratic Assignment Problem on a Tree

DOI10.1287/opre.37.5.760zbMath0682.90064OpenAlexW2010971800MaRDI QIDQ4732306

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

branch-and-boundNP-completeQuadratic Assignment Problempolynomial boundTraveling SalesmanLangrangian relaxation

Mathematics Subject Classification ID

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

Related Items

An efficient algorithm for unequal area facilities layout planning with input and output points ⋮ A survey for the quadratic assignment problem ⋮ Quadratic assignment problems on series-parallel digraphs ⋮ A Lagrangian relaxation algorithm for sparse quadratic assignment problems ⋮ A nonmonotone GRASP ⋮ A branch-and-bound algorithm for the single-row equidistant facility layout problem ⋮ Global optimality conditions and optimization methods for quadratic assignment problems ⋮ Continuation methods for approximate large scale object sequencing ⋮ An experimental study of variable depth search algorithms for the quadratic assignment problem ⋮ Semidefinite programming approach for the quadratic assignment problem with a sparse graph ⋮ Convergence of the surrogate Lagrangian relaxation method ⋮ The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm ⋮ 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 ⋮ A greedy genetic algorithm for the quadratic assignment problem