A branch-and-cut algorithm for quadratic assignment problems based on linearizations

DOI10.1016/j.cor.2005.05.027zbMath1102.90034OpenAlexW2120803586MaRDI QIDQ856686

Güneş Erdoğan, Barbaros C. Tansel

Publication date: 7 December 2006

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11693/11440

zbMATH Keywords

linearizationquadratic assignment problembranch-and-cut

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Discrete location and assignment (90B80)

Related Items (10)

Linearizable special cases of the QAP ⋮ A hybrid biased random key genetic algorithm for the quadratic assignment problem ⋮ A note on a polynomial time solvable case of the quadratic assignment problem ⋮ Linearizable special cases of the quadratic shortest path problem ⋮ A linear time algorithm for linearizing quadratic and higher-order shortest path problems ⋮ A flow based formulation and a reinforcement learning based strategic oscillation for cross-dock door assignment ⋮ A new formulation and an effective matheuristic for the airport gate assignment problem ⋮ An experimental study of variable depth search algorithms for the quadratic assignment problem ⋮ Experimental analysis of crossover and mutation operators on the quadratic assignment problem ⋮ Effective formulation reductions for the quadratic assignment problem

Uses Software

• QAPLIB
• ZRAM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating quadratic assignment test problems with known optimal permutations
• An algorithm for the quadratic assignment problem using Benders' decomposition
• A new exact algorithm for the solution of quadratic assignment problems
• QAPLIB - a quadratic assignment problem library
• Solving large quadratic assignment problems in parallel
• A heuristic for quadratic Boolean programs with applications to quadratic assignment problems
• Solving large quadratic assignment problems on computational grids
• Solving quadratic assignment problems using convex quadratic programming relaxations
• The Quadratic Assignment Problem
• Implementation of a Variance Reduction-Based Lower Bound in a Branch-and-Bound Algorithm for the Quadratic Assignment Problem
• The Backboard Wiring Problem: A Placement Algorithm
• Assignment Problems and the Location of Economic Activities
• P-Complete Approximation Problems
• Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme
• Numerical investigations on quadratic assignment problems

This page was built for publication: A branch-and-cut algorithm for quadratic assignment problems based on linearizations