bnb/SelfSplitBranchAndBound.h

Header of the layer bnb, in the group Searches; the same header on the site of Doxygen, its source on GitHub.

Classes

Class	Description
SelfSplitBranchAndBound	The parallel B&B by a split of the tree after a sampling

Description of the header

Header file for SelfSplitBranchAndBound, the parallel Branch-and-Bound (B&B) whose workers share nothing but the nodes of a first sampling of the tree, as in the SelfSplit of Fischetti, Monaci and Salvagnin (2014).

The problem, the options and the Solution are those of BranchAndBound.h and ParallelBranchAndBound.h, and the design is discussed in docs/branch-and-bound.md.

The search is the following, with the notation of the page “Parallel

branch-and-bound” of the documentation and the procedures of the sequential search [see

BranchAndBound.h]; \( \sigma \) is the number of open nodes per worker at which the sampling stops (split, 4 if 0):

 1  procedure SELFSPLIT(R)
 2     Q ← R;  z ← the given incumbent, or ∞     ▷ the sampling, by worker 0
 3     while p > 1 and Q ≠ ∅ and |Q| < σ p do
 4        if a limit is reached then break
 5        if PRUNABLE(the least bound of Q) then
 6           the nodes of Q are leaves (pruned);  Q ← ∅;  break
 7        n ← the first node of Q, removed;  Q ← Q ∪ PROCESS(n)
 8     if p > 1, split_dive and Q ≠ ∅ then         ▷ the dive, by worker 0
 9        n ← a copy of the first node of Q
10        while n ≠ nil and no limit is reached do
11           n ← the child of PROCESS(n) of least estimate, or nil
12     for k = 0, 1, ..., while Q ≠ ∅ do           ▷ the split
13        add the first node of Q, removed, to R_(k mod p)
14     in parallel, on each worker i = 0, ..., p − 1 do
15        S_i ← B&B(R_i) on the evaluator of i, from the incumbent z, with
             its share of the node limit and the time left, pruning also
             by the incumbent of all the workers if split_shared
16     z ← min(z, the values of the S_i), the node of the least i on ties
17     return z, its node, the leaves of the sampling and of the S_i, and
          the least of their bounds

Without split_shared the workers neither share the incumbent nor exchange nodes between lines 14 and 15, and the nodes of line 13 are those of the sampling in the order of the selection; hence, the outcome depends only on \( \sigma \) and on \( p \), provided that the evaluation of a node by a worker depends only on the node and on the nodes evaluated by that worker before. The sampling uses the selection of the options, with best-first in place of plunging, and the search is correct since the subsets of the nodes of the split cover what the sampling left open. The dive of lines 8 to 11 (the estimate of a child being that of the problem, if it gives one, and its bound otherwise) gives the workers an incumbent to start from: a best-first sampling seldom reaches a leaf, and a worker whose subtrees do not hold the optimum evaluates, without an incumbent, each of their nodes whose bound is better than the best value in them, which on the knapsack were up to 850 times the nodes of the sequential search (at most 2.8 times with the dive). The nodes of the dive are evaluated again by the worker whose subtree holds them, and both evaluations are counted. One worker has nothing to split, and it gets R with neither the sampling nor the dive, so that it evaluates the nodes of the sequential search.

Author

Donato Meoli

Dipartimento di Informatica

Università di Pisa

Copyright

© by Donato Meoli