Optimization Online


A Tight Lower Bound for the Adjacent Quadratic Assignment Problem

Borzou Rostami (bo.rostami***at***gmail.com)
Federico Malucelli (federico.malucelli***at***polimi.it)
Pietro Belotti (pietrobelotti***at***fico.com)

Abstract: In this paper we address the Adjacent Quadratic Assignment Problem (AQAP) which is a variant of the QAP where the cost coefficient matrix has a particular structure. Motivated by strong lower bounds obtained by applying Reformulation Linearization Technique (RLT) to the classical QAP, we propose two special RLT representations for the problem. The first is based on a ``flow'' formulation whose linear relaxation can be solved very efficiently for large instances while the second one has significantly more variables and constraints, but possesses some desirable properties relative to the constraint set. Our computational results indicate that the second model outperforms the classical level-2 RLT, as it obtains lower bounds close to the optimal solutions for all instances with less computational effort.

Keywords: Adjacent quadratic assignment problem, Reformulation-linearization technique, Lower bound, Dual-ascent algorithm

Category 1: Combinatorial Optimization

Category 2: Integer Programming (0-1 Programming )



Entry Submitted: 09/23/2014
Entry Accepted: 09/25/2014
Entry Last Modified: 11/28/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society