A new exact discrete linear reformulation of the quadratic assignment problem

A new exact discrete linear reformulation of the quadratic assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20123249
Volume: 220
Issue: 2
Start Page Number: 314
End Page Number: 319
Publication Date: Jul 2012
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: integer, programming: nonlinear
Abstract:

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP‐hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non‐linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n =32 and 64), from the quadratic assignment problem library, QAPLIB.

Reviews

Required fields are marked *. Your email address will not be published.