Why Heuristics ?

Searching thru the search-tree involves computation of lower bounds, where some are required, but most usually belong in branches which are discarded. The better the bounding function, the fewer unnecessary lower bounds will have to be computed.

It is not simple to calculate a good lower bound. Usually, improvements in the lower bound function yields much higher computational costs of the function. However, no matter how fast the lower bound is to calculate, it will never make it up for a bad bound. The choice between a slow but good, and a faster but worse bounding function remains a compromise.

In order to find a reasonable minimal cost for evaluating the equation system using some ordering (every branch represents a possible ordering), we must go thru the QR factorization process. The ways the different rows of the system affects each other, is simply too complex to easily approximate using some other function. At least, I completely failed to find an easier way, not that I didn't try.

Thus, in order to guarantee that the lower bound is really a lower bound, we should optimize the system before calculating the target function. This is a little too recursive to do us any good. Instead, a simple ordering of the system is made, and that system is factorized. This means, that our lower bound is not necessarily a lower bound anymore. It is a heuristic.

Using heuristics means, that a solution to our problem may no longer be the optimal solution. This is bad if we end up far from the optimum. However, a well-behaved heuristic may well yield results that are ``good'' if not optimal. It truly worried me not being able to guarantee the quality of the solution. However, the heuristic used seems to behave well, and the solutions returned absolutely seems to make sense. Furthermore, it did not seem to be a viable solution to recursively order the system every time a bound calculation is made. Note, that bound calculations for the $56\times 56$ system some times take place more than a billion times (for some ugly systems). If every calculation would involve a B&B search with an average depth of perhaps 30, the result - however good - would be of use to no one by the time it would finish.