An exceptionally difficult binary quadratic optimization problem with symmetry: a challenge for the largest unsolved QAP instance Tai256c

Koichi Fujii, Sunyoung Kim, Masakazu Kojima, Hans D. Mittelmann, Yuji Shinano

Research output: Contribution to journalArticlepeer-review

Abstract

Tai256c is the largest unsolved quadratic assignment problem (QAP) instance in QAPLIB. It is known that QAP tai256c can be converted into a 256 dimensional binary quadratic optimization problem (BQOP) with a single cardinality constraint which requires the sum of the binary variables to be 92. As the BQOP is much simpler than the original QAP, the conversion increases the possibility to solve the QAP. Solving exactly the BQOP, however, is still very difficult. Indeed, a 1.48% gap remains between the best known upper bound (UB) and lower bound (LB) of the unknown optimal value. This paper shows that the BQOP admits a nontrivial symmetry, a property that makes the BQOP very hard to solve. Despite this difficulty, it is imperative to decrease the gap in order to ultimately solve the BQOP exactly. To effectively improve the LB, we propose an efficient BB method that incorporates a doubly nonnegative relaxation, the orbit branching and the isomorphism pruning. With this BB method, a new LB with 1.25% gap is successfully obtained, and computing an LB with 1.0% gap is shown to be still quite difficult.

Original languageEnglish
JournalOptimization Letters
DOIs
StateAccepted/In press - 2024

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2024.

Fingerprint

Dive into the research topics of 'An exceptionally difficult binary quadratic optimization problem with symmetry: a challenge for the largest unsolved QAP instance Tai256c'. Together they form a unique fingerprint.

Cite this