  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. The
symmetry induces equivalent subproblems in branch and bound (BB) methods. To
effectively improve the LB, we propose an efficient BB method that incorporates
a doubly nonnegative relaxation, the standard orbit branching and a technique
to prune equivalent subproblems. 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.
