TY - JOUR
T1 - An exceptionally difficult binary quadratic optimization problem with symmetry
T2 - a challenge for the largest unsolved QAP instance Tai256c
AU - Fujii, Koichi
AU - Kim, Sunyoung
AU - Kojima, Masakazu
AU - Mittelmann, Hans D.
AU - Shinano, Yuji
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2024.
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85208811826&partnerID=8YFLogxK
U2 - 10.1007/s11590-024-02157-2
DO - 10.1007/s11590-024-02157-2
M3 - Article
AN - SCOPUS:85208811826
SN - 1862-4472
JO - Optimization Letters
JF - Optimization Letters
ER -