quadratic assignment problem (qap)

A New Relaxation Framework for Quadratic Assignment Problems based on Matrix Splitting

  • Xiaoxue Li
  • Hans D Mittelmann
  • Jiming Peng
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Linear, Cone and Semidefinite Programming Tags , , , ,

    Quadratic assignment problems (QAPs) are among the hardest discrete optimization problems. Recent study shows that even obtaining a strong lower bound for QAPs is a computational challenge. In this paper, we first discuss how to construct new simple convex relaxations of QAPs based on various matrix splitting schemes. Then we introduce the so-called symmetric mappings … Read more

    Estimating Bounds for Quadratic Assignment Problems Associated with Hamming and Manhattan Distance Matrices based on Semidefinite Programming

  • Hans D Mittelmann
  • Jiming Peng
    • Categories Applications - OR and Management Sciences, Semi-definite Programming Tags , , ,

    Quadratic assignment problems (QAPs) with a Hamming distance matrix of a hypercube or a Manhattan distance matrix of rectangular grids arise frequently from communications and facility locations and are known to be among the hardest discrete optimization problems. In this paper we consider the issue of how to obtain lower bounds for those two classes … Read more