Integrating pivot based search with branch and bound for binary MIPs

This paper examines integration of a sophisticated, pivot-based tabu search into branch and bound for 0-1 MIPS and global diversification tests using chunking. Issues related to behavior of a tabu search within a branch and b ound algorithm are analyzed using computational experiments. Results are pr esented showing that the inclusion of the local search sometimes results in fewer nodes and lower CPU times even when used in a callback mode. The mai n benefit in incorporating a pivot based heuristic is that an integer feasi ble solution can be found earlier in the branching process. Computational e xperiments are presented showing that for some instances the overall search time is improved, while for some others the tabu search can find good solu tions quickly.