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

#include <ParBranchAndBound.h>

Public Member Functions
	ParBranchAndBound ()
	Default constructor.

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

virtual	~ParBranchAndBound ()
	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...

std::vector< std::vector< double > >	mapSerialOutput (std::vector< std::vector< double > >serVec, std::vector< std::vector< double > >parVec)
	Map nodes generated in serial and parallel branch-and-bound 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.

int	strToInt (std::string str)
	Convert a string to integer data type.

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

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

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

void	print2dvec (std::vector< std::vector< int > > output)
	Print a two-dimensional vector (customized).

void	print2dvec (std::vector< std::vector< double > > output)
	Print a two-dimensional vector (customized).

std::vector< std::vector< double > >	readSerialOutput (const char *inputFile)
	Read output of branch-and-bound tree generated by a single thread. 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 ParBranchAndBound::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 ParBranchAndBound::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 ParBranchAndBound::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 ParBranchAndBound::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.

◆ mapSerialOutput()

std::vector< std::vector< double > > ParBranchAndBound::mapSerialOutput	(	std::vector< std::vector< double > >	serVec,
		std::vector< std::vector< double > >	parVec
	)

Map nodes generated in serial and parallel branch-and-bound tree.

The logic assumes that a parent node gives rise to only two children and the one created using the left branch is assigned an id first.

Parameters

[in]	serVec	The vector of node descriptions in serial tree.
[in]	parVec	The vector of node descriptions in parallel tree.

◆ parsolve()

void ParBranchAndBound::parsolve	(	ParNodeIncRelaxerPtr	parNodeRelaxer[],
		ParPCBProcessorPtr	parPCBProcessor[],
		UInt	nThreads
	)

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.

◆ parsolveOppor()

void ParBranchAndBound::parsolveOppor	(	ParNodeIncRelaxerPtr	parNodeRelaxer[],
		ParPCBProcessorPtr	parPCBProcessor[],
		UInt	nThreads
	)

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 ParBranchAndBound::parsolveSync	(	ParNodeIncRelaxerPtr	parNodeRelaxer[],
		ParPCBProcessorPtr	parPCBProcessor[],
		UInt	nThreads
	)

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.

◆ readSerialOutput()

std::vector< std::vector< double > > ParBranchAndBound::readSerialOutput ( const char * inputFile )

Read output of branch-and-bound tree generated by a single thread.

Each line of the input file must contain the following node information. NodeId ParentId BrVar Lb ThreadId StartTime EndTime TbScore PruneStatus TreeUb Only the first three columns are used for mapping, rest are for completeness of tree information. Root node information is not needed.

◆ setLogLevel()

void ParBranchAndBound::setLogLevel ( LogLevel level )

Set log level.

Parameters

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

◆ setNodeProcessor()

void ParBranchAndBound::setNodeProcessor ( NodeProcessorPtr p )

Set the NodeProcessor that processes each node.

Parameters

[in] p The desired node-processor.

◆ setNodeRelaxer()

void ParBranchAndBound::setNodeRelaxer ( NodeRelaxerPtr nr )

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

Parameters

[in] nr The desired node-relaxer.

◆ shouldCreateRoot()

void ParBranchAndBound::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/ParBranchAndBound.h
/home/amahajan/tmp/minotaur-test/src/base/ParBranchAndBound.cpp

Public Member Functions

Detailed Description

Member Function Documentation

◆ addPreRootHeur()

◆ getLb()

◆ getPerGap()

◆ getUb()

◆ mapSerialOutput()

◆ parsolve()

◆ parsolveOppor()

◆ parsolveSync()

◆ readSerialOutput()

◆ setLogLevel()

◆ setNodeProcessor()

◆ setNodeRelaxer()

◆ shouldCreateRoot()