Optimization Online


MatQapNB User Guide: A branch-and-bound program for QAPs in Matlab with the Newton-Bracketing method

Koichi Fujii (fujii***at***msi.co.jp)
Naoki Ito (naoki.b.ito***at***fastretailing.com)
Sunyoung Kim (skim***at***ewha.ac.kr)
Masakazu Kojima (kojima***at***is.titech.ac.jp)
Hans D. Mittelmann (mittelma***at***asu.edu)
Yuji Shinano (shinano***at***zib.de)
Kim-Chuan Toh (mattohkc***at***nus.edu.sg)

Abstract: MatQapNB is a MATLAB toolbox that implements a parallel branch-and-bound method using NewtBracket (the Newton bracketing method [4]) for its lower bounding procedure. It can solve small to medium scale Quadratic Assignment Problem (QAP) instances with dimension up to 30. MatQapNB was used in the numerical experiments on QAPs in the recent article "Solving challenging scale QAPs" [3] by Fujii, Ito, Kim, Kojima, Shinano and Toh, an intermediate progress report on the authors' joint project for solve large-scale QAP instances in QAPLIB whose exact optimal values are unknown [2]. For large scale QAPs, the authors have been developing a C++ version of the method, QapNB, which works on the Ubiquity Generator (UG) framework utilizing more than 100,000 cores, based on MatQapNB. We refer to the article [3] for theoretical and technical details on the parallel branch-and-method implemented in MatQapNB. This user guide describes the usage of MatQapNB. MatQapNB is included in the software package NewtBracket-v2.0 as an application, which can be obtained from https://sites.google.com/site/masakazukojima1/softwares-developed/newtbracket

Keywords: Matlab toolbox, Quadratic assignment problems, Branch-and-bound methods, Newton-Bracketing methods

Category 1: Global Optimization (Applications )

Category 2: Optimization Software and Modeling Systems (Optimization Software Design Principles )

Category 3: Nonlinear Optimization (Quadratic Programming )


Download: [PDF]

Entry Submitted: 06/09/2021
Entry Accepted: 06/27/2021
Entry Last Modified: 08/31/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