An Exact Algorithm for the Quadratic Assignment Problem on a Tree

DOI10.1287/OPRE.37.5.760zbMATH Open0682.90064OpenAlexW2010971800MaRDI QIDQ4732306FDOQ4732306

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

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

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)

Cited In (22)

• A greedy genetic algorithm for the quadratic assignment problem
• Title not available (Why is that?)
• Semidefinite programming approach for the quadratic assignment problem with a sparse graph
• Global optimality conditions and optimization methods for quadratic assignment problems
• 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
• Title not available (Why is that?)
• A mixed-integer programming formulation for optimizing the double row layout problem
• A Lagrangian relaxation algorithm for sparse quadratic assignment problems
• Convergence of the surrogate Lagrangian relaxation method
• Continuation methods for approximate large scale object sequencing
• Dynamic programming for the quadratic assignment problem on trees
• Title not available (Why is that?)

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)