Subproblem Selection in Branch-and-Bound Algorithms
Mirjam Dür, Technische Universität Darmstadt
We investigate the Branch-and-Bound method which is frequently used both
for discrete and for continuous 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 randomized selection rule converges with probability one.
This new method is a generalization of the well known best-bound selection
rule. Numerical experiments on the Maximum Clique Problem show that
probabilistic selection can speed up an algorithm in many cases.
This is joint work with Volker Stix, Wirtschaftsuniversität Wien.
Chemnitz Workshop
Last modified: Thu Oct 7 16:01:51 CEST 2004