Implement a generic parallel branch-and-bound algorithm on a multicore cpu. More...

#include <ParQGBranchAndBound.h>

Public Member Functions
	ParQGBranchAndBound ()
	Default constructor.

	ParQGBranchAndBound (EnvPtr env, ProblemPtr p)
	Constructor for a given Problem and Environment.

virtual	~ParQGBranchAndBound ()
	Destroy.

void	printsomething ()

void	addPreRootHeur (HeurPtr h)
	Add a heuristic that will be called before root node. More...

double	getPerGap ()
	Return the percentage gap between the lower and upper bounds. More...

double	getLb ()
	Return the lower bound from the search tree. More...

NodeProcessorPtr	getNodeProcessor ()
	Return a pointer to NodeProcessor used in branch-and-bound.

NodeRelaxerPtr	getNodeRelaxer ()
	Return a pointer to NodeRelaxer used in branch-and-bound.

SolutionPtr	getSolution ()

SolveStatus	getStatus ()
	Return the final status.

ParTreeManagerPtr	getTreeManager ()
	Return a pointer to the tree manager. The client can then directly query the ParTreeManager for its size and other attributes.

double	getUb ()
	Return the upper bound for the solution value from the search tree. More...

UInt	numProcNodes ()
	Return number of nodes processed while solving.

void	setLogLevel (LogLevel level)
	Set log level. More...

void	setNodeProcessor (NodeProcessorPtr p)
	Set the NodeProcessor that processes each node. More...

void	setNodeRelaxer (NodeRelaxerPtr nr)
	Set the NodeRelaxer for setting-up relaxations at each node. More...

void	shouldCreateRoot (bool b)
	Switch to turn on/off root-node creation. More...

void	solve ()
	Start solving the Problem using branch-and-bound.

void	parsolve (ParNodeIncRelaxerPtr parNodeRelaxer[], ParPCBProcessorPtr parPCBProcessor[], UInt nThreads, bool prune)
	Start solving the Problem using branch-and-bound. More...

void	parsolveOppor (ParNodeIncRelaxerPtr parNodeRelaxer[], ParPCBProcessorPtr parPCBProcessor[], UInt nThreads, bool prune)
	Start solving the Problem using parallel branch-and-bound in an opportunistic mode. More...

void	parsolveSync (ParNodeIncRelaxerPtr parNodeRelaxer[], ParPCBProcessorPtr parPCBProcessor[], UInt nThreads, bool prune)
	Branch-and-bound solver with reproducibility of results. More...

void	removeAddedCons (RelaxationPtr rel, UInt nc)
	Function to remove the constraints added to this relaxation. More...

double	totalTime ()
	Return total time taken.

void	writeStats (std::ostream &out)
	Write statistics to the ostream out.

void	writeParStats (std::ostream &out, ParPCBProcessorPtr parPCBProcessor[])
	Write statistics of parallel algorithm to the ostream out.

void	writeStats ()
	Write statistics to the logger.

double	getWallTime ()
	Get wall clock time.

Detailed Description

Implement a generic parallel branch-and-bound algorithm on a multicore cpu.

Member Function Documentation

◆ addPreRootHeur()

void ParQGBranchAndBound::addPreRootHeur ( HeurPtr h )

Add a heuristic that will be called before root node.

Parameters

[in] h The heuristic that should be called. This heuristic will be called after all previously added heuristic.

◆ getLb()

double ParQGBranchAndBound::getLb ( )

Return the lower bound from the search tree.

This bound is defined as the minimum of the bounds from all active nodes. It may not be a bound on the optimal solution value.

◆ getPerGap()

double ParQGBranchAndBound::getPerGap ( )

Return the percentage gap between the lower and upper bounds.

Gap percentage is calculated as $\frac{u - l}{\left|u\right|+\epsilon} \times 100$ , where $u$ is the upper bound, $l$ is the lower bound and $\epsilon$ is a small constant to avoid division by zero.

◆ getUb()

double ParQGBranchAndBound::getUb ( )

Return the upper bound for the solution value from the search tree.

This bound may or may not correspond to a feasible solution of the problem. It may be obtained from a feasible solution of a relaxation of the problem.

◆ parsolve()

void ParQGBranchAndBound::parsolve	(	ParNodeIncRelaxerPtr	parNodeRelaxer[],
		ParPCBProcessorPtr	parPCBProcessor[],
		UInt	nThreads,
		bool	prune
	)

Start solving the Problem using branch-and-bound.

Parameters

[in]	parNodeRelaxer	is the array of node relaxers.
[in]	parPCBProcessor	is the array of node processors.
[in]	nThreads	is the number of threads being used.
[in]	prune	if true indicates infeasiblity

◆ parsolveOppor()

void ParQGBranchAndBound::parsolveOppor	(	ParNodeIncRelaxerPtr	parNodeRelaxer[],
		ParPCBProcessorPtr	parPCBProcessor[],
		UInt	nThreads,
		bool	prune
	)

Start solving the Problem using parallel branch-and-bound in an opportunistic mode.

Parameters

[in]	parNodeRelaxer	is the array of node relaxers.
[in]	parPCBProcessor	is the array of node processors.
[in]	nThreads	is the number of threads being used.

◆ parsolveSync()

void ParQGBranchAndBound::parsolveSync	(	ParNodeIncRelaxerPtr	parNodeRelaxer[],
		ParPCBProcessorPtr	parPCBProcessor[],
		UInt	nThreads,
		bool	prune
	)

Branch-and-bound solver with reproducibility of results.

Parameters

[in]	parNodeRelaxer	is the array of node relaxers.
[in]	parPCBProcessor	is the array of node processors.
[in]	nThreads	is the number of threads being used.

◆ removeAddedCons()

void ParQGBranchAndBound::removeAddedCons	(	RelaxationPtr	rel,
		UInt	nc
	)

Function to remove the constraints added to this relaxation.

Parameters

[in]	rel	is the relaxation of a node.
[in]	nc	is the number of constraints at the root node.

◆ setLogLevel()

void ParQGBranchAndBound::setLogLevel ( LogLevel level )

Set log level.

Parameters

[in] level The desired log level for this class.

◆ setNodeProcessor()

void ParQGBranchAndBound::setNodeProcessor ( NodeProcessorPtr p )

Set the NodeProcessor that processes each node.

Parameters

[in] p The desired node-processor.

◆ setNodeRelaxer()

void ParQGBranchAndBound::setNodeRelaxer ( NodeRelaxerPtr nr )

Set the NodeRelaxer for setting-up relaxations at each node.

Parameters

[in] nr The desired node-relaxer.

◆ shouldCreateRoot()

void ParQGBranchAndBound::shouldCreateRoot ( bool b )

Switch to turn on/off root-node creation.

Sometimes a client may set up a root node on its own and may not want the default root node.

Parameters

[in] b True if root node should be created, false otherwise.

The documentation for this class was generated from the following files:

/home/amahajan/tmp/minotaur-test/src/base/ParQGBranchAndBound.h
/home/amahajan/tmp/minotaur-test/src/base/ParQGBranchAndBound.cpp

Public Member Functions

Detailed Description

Member Function Documentation

◆ addPreRootHeur()

◆ getLb()

◆ getPerGap()

◆ getUb()

◆ parsolve()

◆ parsolveOppor()

◆ parsolveSync()

◆ removeAddedCons()

◆ setLogLevel()

◆ setNodeProcessor()

◆ setNodeRelaxer()

◆ shouldCreateRoot()