The QAP-polytope and the star transformation (Q5939231)

The authors propose an isomorphic transformation, called star-transformation, of the quadratic assignment polytope. Starting with this, a new technique is developed that allows performing deeper polyhedral investigations of the quadratic asignment problem. This simplifies the polyhedral investigations enormously and so it is possible to use this technique for improving practical solutions of hard combinatorial problems, like the traveling salesman problem.