Optimization Online


Solving Challenging Large Scale QAPs

Koichi Fujii (fujii***at***msi.co.jp)
Naoki Ito (naoki.b.ito***at***fastretailing.com)
Sunyoung Kim (skim1510***at***yahoo.com)
Masakazu Kojima (kojimamasakazu***at***me.com)
Yuji Shinano (shinano***at***zib.de)
Kim-Chuan Toh (mattohkc***at***nus.edu.sg)

Abstract: We report our progress on the project for solving larger scale quadratic assignment problems (QAPs). Our main approach to solve large scale NP-hard combinatorial optimization problems such as QAPs is a parallel branch-and-bound method eciently implemented on a powerful computer system using the Ubiquity Generator (UG) framework that can utilize more than 100,000 cores. Lower bounding procedures incorporated in the branch-and-bound method play a crucial role in solving the problems. For a strong lower bounding procedure, we employ the Lagrangian doubly nonnegative (DNN) relaxation and the Newton-bracketing method developed by the authors' group. In this report, we describe some basic tools used in the project including the lower bounding procedure and branching rules, and present some preliminary numerical results. Our next target problem is QAPs with dimension at least 50, as we have succeeded to solve tai30a and sko42 from QAPLIB for the rst time.

Keywords: QAP, Parallel Branch-and-bound

Category 1: Applications -- OR and Management Sciences

Citation: ZIB Report 21-02, Zuse Institute Berlin, Takustraße 7 14195 Berlin Deutschland

Download: [PDF]

Entry Submitted: 01/23/2021
Entry Accepted: 01/24/2021
Entry Last Modified: 01/24/2021

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