An Exact Algorithm for the Quadratic Assignment Problem on a Tree
From MaRDI portal
Publication:4732306
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
branch-and-boundNP-completeQuadratic Assignment Problempolynomial boundTraveling SalesmanLangrangian relaxation
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