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

DOI10.1016/S0377-2217(97)00063-5zbMATH Open0947.90129MaRDI QIDQ1296800FDOQ1296800

Authors: Thomas Grant, Nat Hall, Peter M. Hahn 

Publication date: 3 August 1999

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

Recommendations

• A solution method for the quadratic assignment problem based on the Hungarian algorithm
• Lower bounds for the quadratic assignment problem based upon a dual formulation
• A branch-and-bound-based heuristic for solving the quadratic assignment problem
• scientific article; zbMATH DE number 970341

zbMATH Keywords

quadratic programmingquadratic assignment probleminteger programmingbranch-and-bound

Mathematics Subject Classification ID

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

Cites Work

• QAPLIB-A quadratic assignment problem library
• Assignment Problems and the Location of Economic Activities
• Algorithms for the Assignment and Transportation Problems
• P-Complete Approximation Problems
• On the quadratic assignment problem
• Lower bounds for the quadratic assignment problem based upon a dual formulation
• The quadratic assignment problem
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• A parallel branch and bound algorithm for the quadratic assignment problem
• Hospital Layout as a Quadratic Assignment Problem
• Title not available (Why is that?)
• A New Lower Bound for the Quadratic Assignment Problem
• Quadratic assignment problems
• A heuristic for quadratic Boolean programs with applications to quadratic assignment problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• On lower bounds for a class of quadratic 0,1 programs
• A branch-and-bound-based heuristic for solving the quadratic assignment problem
• Implementation of a Variance Reduction-Based Lower Bound in a Branch-and-Bound Algorithm for the Quadratic Assignment Problem
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (20)

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

Uses Software

• QAPLIB

This page was built for publication: A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method

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