二次指派问题新的线性化方法.pdfVIP

Optimization Methods and Software Vol. 21, No. 5, October 2006, 805–818 A new linearization method for quadratic assignment problems YONG XIA* and YA-XIANG YUAN State Key Laboratory of Scientific/Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, The Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences, P.O. Box 2719, Beijing 100080, P.R. China (Received 2 November 2004; revised 14 July 2005; in final form 18 July 2005) The quadratic assignment problem (QAP) is one of the great challenges in combinatorial optimization. Linearization for QAP is to transform the quadratic objective function into a linear one. Numerous QAP linearizations have been proposed, most of which yield mixed integer linear programs. Kauffmann and Broeckx’s linearization (KBL) is the current smallest one in terms of the number of variables and constraints. In this article, we give a new linearization, which has the same size as KBL. Our linearization is more efficient in terms of the tightness of the continuous relaxation. Furthermore, the continuous relaxation of our linearization leads to an improvement to the Gilmore–Lawler bound. We also give a corresponding cutting plane heuristic method for QAP and demonstrate its superiority by numerical results. Keywords: Quadratic assignment problem; Linearization; Mixed integer linear program; Lower bound; Cutting plane 1. Introduction The quadratic assignment problem (QAP) is one of the great challenges in combinatorial optimization. For comprehensive surveys of QAPs, we refer to refs. [7,11,19]. A detailed review on recent advances is given in ref. [3]. The following formulation of QAP was used initially by Koopm