orbital.algorithm.template
Class ParallelBranchAndBound

java.lang.Object
  orbital.algorithm.template.GeneralSearch
      orbital.algorithm.template.GeneralBoundingSearch
          orbital.algorithm.template.BranchAndBound
              orbital.algorithm.template.ParallelBranchAndBound

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate, EvaluativeAlgorithm, HeuristicAlgorithm

public class ParallelBranchAndBound
extends BranchAndBound

Parallel branch-and-bound algorithm.

Visits the next nodes in parallel and bound by the best solution known. Even though the implementation uses a stack of nodes, due to the parallel nature this algorithm behaves much like BreadthFirstSearch. However, the scheduling policy of the thread scheduler may introduce a probabilistic behaviour in execution speed.

Multi-Processors versus Multi-Threading on a Single-Processor

Parallel algorithms profit much from multi-processors, but their benefits are nevertheless not limited to those machines. Even single-processor systems can experience a speed-up when using a parallel variant of a simple algorithm.

The speed-up S(n) := T(1)/T(n) in execution time T(n) on an n processor system is in general in 1≤S(n)≤I(n)≤n, with I(n) := P(n)/T(n) being the parallel index of mean parallelization on an n processor system (P(n) := number of operations on n processors).

However, in rare cases super-linear speed-ups of S(n)>n can be observed due to synergy effects, even though they impossible from a theoretical perspective. In fact, they result from comparing slightly different(!) algorithms, or from more memory or larger caches. Yet, when they occur these advantages should be exploited.

ParallelBranchAndBound very often is such a case where super-linear speed-ups occur, because a parallel depth-first search no longer is depth-first in the large. In combination with the bounding, the synergetic effects result from the fact that the one thread's success may simplify another thread's job. By its sheer parallelity, the parallel depth-first branch-and-bound more resembles breadth-first search inspite of its implementation similarity with depth-first search. And this explains why using ParallelBranchAndBound can result in a better performance even on single-processor systems.

Author:

André Platzer

See Also:

BreadthFirstSearch, Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class orbital.algorithm.template.GeneralSearch

GeneralSearch.OptionIterator

Nested classes/interfaces inherited from interface orbital.algorithm.template.HeuristicAlgorithm

HeuristicAlgorithm.Configuration, HeuristicAlgorithm.PatternDatabaseHeuristic

Nested classes/interfaces inherited from interface orbital.algorithm.template.EvaluativeAlgorithm

EvaluativeAlgorithm.EvaluationComparator

Constructor Summary

ParallelBranchAndBound(Function heuristic, double bound)

Method Summary

Function	complexity() O(d) on parallel machines where d the solution depth.
protected java.util.Iterator	createTraversal(GeneralSearchProblem problem) Define a traversal order by creating an iterator for the problem's state space.
protected java.lang.Object	search(java.util.Iterator nodes) Run the general search algorithm scheme.
protected java.lang.Object	solveImpl(GeneralSearchProblem problem) Implements the solution policy.
Function	spaceComplexity() O(bd) where b is the branching factor and d the solution depth.

Methods inherited from class orbital.algorithm.template.BranchAndBound

getEvaluation, getHeuristic, getMaxBound, isOptimal, processSolution, setHeuristic, setMaxBound, setMaxBound

Methods inherited from class orbital.algorithm.template.GeneralBoundingSearch

getBound, isContinuedWhenFound, isOutOfBounds, setBound, setBound, setContinuedWhenFound

Methods inherited from class orbital.algorithm.template.GeneralSearch

getProblem, solve

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate

solve

Constructor Detail

ParallelBranchAndBound

public ParallelBranchAndBound(Function heuristic,
                              double bound)

Method Detail

complexity

public Function complexity()

O(d) on parallel machines where d the solution depth.

Specified by:

complexity in interface AlgorithmicTemplate

Overrides:

complexity in class BranchAndBound

Returns:

the function f for which the solve() method of this algorithm runs in O(f(n)) assuming the algorithmic problem hook to run in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)

spaceComplexity

public Function spaceComplexity()

O(b^d) where b is the branching factor and d the solution depth.

Specified by:

spaceComplexity in interface AlgorithmicTemplate

Returns:

the function f for which the solve() method of this algorithm consumes memory with an amount in O(f(n)) assuming the algorithmic problem hook uses space in O(1).

See Also:

AlgorithmicTemplate.solve(AlgorithmicProblem)

solveImpl

protected java.lang.Object solveImpl(GeneralSearchProblem problem)

Description copied from class: GeneralSearch

Implements the solution policy.

Like the default solution policies, this implementation will

1. Fetch a traversal order policy by calling GeneralSearch.createTraversal(GeneralSearchProblem).
2. Then call GeneralSearch.search(Iterator) to search through the state space in the traversal order.

However, sophisticated search algorithms may want to change that policy and iterate the above process, resulting in a sequence of calls to those methods. They may do so by by overwriting this method.

Overrides:

solveImpl in class BranchAndBound

Returns:

the solution found by GeneralSearch.search(Iterator).

See Also:

GeneralSearch.search(Iterator)

createTraversal

protected final java.util.Iterator createTraversal(GeneralSearchProblem problem)

Description copied from class: GeneralSearch

Define a traversal order by creating an iterator for the problem's state space.

Lays a linear order through the state space which the search can simply follow sequentially. Thus a traversal policy effectively reduces a search problem through a graph to a search problem through a linear sequence of states. Of course, the mere notion of a traversal policy does not yet solve the task of finding a good order of states, but only encapsulate it. Complete search algorithms result from traversal policies that have a linear sequence through the whole state space.

Parameters:

problem - the problem whose state space to create a traversal iterator for.

Returns:

an iterator over the options of the problem's state space thereby encapsulating and hiding the traversal order.

See Also:

Factory Method, GeneralSearch.OptionIterator

search

protected java.lang.Object search(java.util.Iterator nodes)

Description copied from class: GeneralBoundingSearch

Run the general search algorithm scheme.

This method only needs to be overwritten to provide a completely different search scheme. Usually, the default search algorithm scheme is sufficient.

Overrides:

search in class GeneralBoundingSearch

Parameters:

nodes - is the iterator over the nodes to visit (sometimes called open set) which determines the traversal order.

Returns:

the solution found searching the state space via nodes.

See Also:

Template Method