Wednesday 26
Non-linear optimisation, bi-level optimisation and yield management
Serigne Gueye
› 12:00 - 12:30 (30min)
› Bât. A - TD 34
A linear formulation with O(n^2 ) variables for the quadratic assignment problem
Serigne Gueye  1@  , Philippe Michelon  1@  
1 : Laboratoire d'Informatique d'Avignon  (LIA)  -  Website
Université d'Avignon et des Pays de Vaucluse
339, chemin des Meinajaries Agroparc BP 91228 84911 AVIGNON Cedex 9, FRANCE -  France

We present an integer linear formulation that uses the so-called “distance variables” to solve the quadratic assignment problem (QAP). The model involves O(n^2 ) variables. Valid equalities and inequalities are additionally proposed. We further improved the model by using metric properties as well as an algebraic characterization of the Manhattan distance matrices that Mittelman and Peng recently proved for the special case of problems on grid graphs. We numerically tested the lower bound provided by the linear relaxation using instances of the quadratic assignment problem library (QAPLIB). Our results are compared with the best known lower bounds. For all instances, the formulation gives a very competitive lower bound in a short computational time, improving seven best lower bounds of QAPLIB instances for which no optimality proofs exist.

Online user: 2