Probabilistic subproblem selection in branch-and-bound algorithms (Q557739)

The authors propose to include a probabilistic element into the selection process of the subproblem in branch-and-bound algorithms. The proposed method is a generalization of the best-bound selection rule. Also, they give conditions which guarantee that the branch-and-bound algorithm converges with probability \(1\), using the probabilistic selection rule proposed by the authors. Numerical experiments on the maximum clique problem are given.