A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method

DOI10.1016/S0377-2217(97)00063-5zbMath0947.90129MaRDI QIDQ1296800

Thomas Grant, Nat Hall, Peter M. Hahn

Publication date: 3 August 1999

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

integer programmingquadratic programmingbranch-and-boundquadratic assignment problem

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20)

Related Items

The quadratic three-dimensional assignment problem: exact and approximate solution methods ⋮ A survey for the quadratic assignment problem ⋮ A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives ⋮ Bounds for the quadratic assignment problem using the bundle method ⋮ A level-2 reformulation-linearization technique bound for the quadratic assignment problem ⋮ A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique ⋮ A new adaptive Hungarian mating scheme in genetic algorithms ⋮ Fuzzy weighted equilibrium multi-job assignment problem and genetic algorithm ⋮ New linearizations of quadratic assignment problems ⋮ RLT insights into lift-and-project closures ⋮ The fuzzy quadratic assignment problem with penalty: new models and genetic algorithm ⋮ Effective formulation reductions for the quadratic assignment problem ⋮ Probabilistic subproblem selection in branch-and-bound algorithms ⋮ An algorithm for the generalized quadratic assignment problem ⋮ The linearization problem of a binary quadratic problem and its applications ⋮ Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods

Uses Software

• QAPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quadratic assignment problems
• QAPLIB-A quadratic assignment problem library
• On lower bounds for a class of quadratic 0,1 programs
• A parallel branch and bound algorithm for the quadratic assignment problem
• On the quadratic assignment problem
• A heuristic for quadratic Boolean programs with applications to quadratic assignment problems
• Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation
• The Quadratic Assignment Problem
• Implementation of a Variance Reduction-Based Lower Bound in a Branch-and-Bound Algorithm for the Quadratic Assignment Problem
• Algorithms for the Assignment and Transportation Problems
• Assignment Problems and the Location of Economic Activities
• A branch-and-bound-based heuristic for solving the quadratic assignment problem
• A New Lower Bound for the Quadratic Assignment Problem
• P-Complete Approximation Problems
• Hospital Layout as a Quadratic Assignment Problem
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem