Target-oriented branch and bound method for global optimization (Q1422887)

The author introduces the concept of a ``target'' for branch and bound algorithms for (here) maximization problems. The target is a value between the lower and upper bound of the problem at a node of the branch and bound tree. If some feasible solution \(x\) can be found such that \(f(x) \geq target\) then \(f(x)\) serves as a lower bound, otherwise \(target\) defines a new upper bound. The modified algorithm does only explore nodes where the upper bound is greater than or equal to the target. Those where the upper bound is less than the target, but bigger than the lower bound are remembered. The process is then repeated with the list of remembered nodes. In numerical tests it is shown that the target-oriented branch and bound algorithm is superior to the classical one for the maximum clique problem.