What exactly is it we are branching ? In order to apply B&B search, we need to perform some sort of incremental solution of our optimization problem.
The approach I chose, is to fix some row and some column at the left-most upper-most position. Since many rows and columns may yield a valid sub-solution (eg. place a non-zero in the diagonal), we are often able to generate multiple branches.
For every branch we are again able to fix some other row and some other column in the second-left-most and second-upper-most positions. Again we probably have more than one choice, and therefore a number of sub-branches. At all times, the active branches are kept in the list of ``live nodes''.
The process of fixing a column and a row can be visualized as below:
When we reach the point where we have fixed all columns and all rows, we have reached a final solution. The cost of this solution (found simply by factorizing it and recording the number of FLOPS required), will determine whether it will be the new best-solution, or simply discarded.
