Implementation of a Variance Reduction-Based Lower Bound in a Branch-and-Bound Algorithm for the Quadratic Assignment Problem

DOI10.1137/S1052623494273393zbMath0873.90072MaRDI QIDQ3124047

Yong Li, K. G. Ramakrishnan, Mauricio G. C. Resende, Panos M. Pardalos

Publication date: 11 March 1997

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

zbMATH Keywords

branch-and-boundquadratic assignmentlower boundtest problemsdata structurehashing functionlarge data variance problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Integer programming (90C10) Quadratic programming (90C20) Combinatorial optimization (90C27) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Discrete location and assignment (90B80)

Related Items

A survey for the quadratic assignment problem ⋮ A branch-and-cut algorithm for quadratic assignment problems based on linearizations ⋮ Solution methods for the balancing of jet turbines ⋮ Gilmore-Lawler bound of quadratic assignment problem ⋮ Hybridizing exact methods and metaheuristics: a taxonomy ⋮ A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method ⋮ Classes of quadratic assignment problem instances: Isomorphism and difficulty measure using a statistical approach

Uses Software

• QAPLIB
• GRASP_QAP