We investigate the branch-and-bound method for solving nonconvex optimization problems. Traditionally, much effort has been invested in improving the quality of the bounds and in the development of branching strategie...
详细信息
We investigate the branch-and-bound method for solving nonconvex optimization problems. Traditionally, much effort has been invested in improving the quality of the bounds and in the development of branching strategies, whereas little is known about good selection rules. After summarizing several known selection methods, we propose to introduce a probabilistic element into the selection process. We describe conditions which guarantee that a branch-and-bound algorithm using our probabilistic selection rule converges with probability 1. This new method is a generalization of the well-known best-boundselection rule. Furthermore, we relate the corresponding probability measure to the distribution of the optimal solution in the bounding interval. We also show how information on the quality of the upper and lower bounds influences the choice of the subsetselection rule and conclude with numerical experiments on the Maximum Clique Problem which show that probabilistic selection can speed up an algorithm in many cases. (c) 2004 Elsevier B.V. All rights reserved.
暂无评论