I am currently trying to implement a branch-and-bound approach to solve the quadratic assignment problem by following the paper 'A parallel branch and bound algorithm for the quadratic assignment problem' which can be found here: Link to paper. I got quite far already, but I am missing some information. Maybe someone can help me understand the last steps.
My problem mainly focuses on understanding page 7 (page 217 in the corner). So, on the first node, I calculate the lower and upper bound. Then I create new nodes (in this case $T_1,\dots,T_3$ and save them in a list. With the permutation $p^{B^0}$ I can calculate the cost of the branch $T_3$. Now the algorithm jumps to the next node $T_2$ saved in the list. The permutation for this node is not finished yet. As I understand it, I have to find a partial permutation $\beta$, that completes this branch. Can I choose an arbitrary $\beta$ here? If so, what happens if there are a lot of prohibited assignments already. Is there an elegant way to find a suitable $\beta$, that is programmable?
After finding $\beta$, is the instruction for finding $B^{(k)}(\beta)$ an update instruction to the previously found $B$, returning a new $B$ of size $n\times n$ or does this return a smaller matrix?
I hope my questions are clear enough. If not, feel free to ask more. I really need to get this algorithm implemented as soon as possible.
Thanks for helping :)