BGIP_SolverBranchAndBound is a class that performs Branch-and-Bound search for identical payoff Bayesian Games. More...

#include <BGIP_SolverBranchAndBound.h>

Inheritance diagram for BGIP_SolverBranchAndBound< JP >:

Public Member Functions
	BGIP_SolverBranchAndBound (const boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > &bg, int verbose=0, size_t nrDesiredSolutions=1, bool expandAll=false, BGIP_BnB::BnB_JointTypeOrdering jtOrdering=BGIP_BnB::IdentityMapping, bool reComputeHeur=false)
	Constructor. More...

bool	GetNextJointPolicyAndValueSpecific (boost::shared_ptr< JointPolicyDiscretePure > &jpol, double &value)
	The specific implementation that should be implemented by the derived class: More...

size_t	GetNrNodesExpanded () const

bool	IsExactSolver () const
	Methods should indicated whether they compute exact (optimal) solutions or not. More...

void	SetCBGlowerBound (double lowerbound)

void	SetCBGupperBound (double upperbound)

double	Solve ()
	The methods that performs the planning. More...

	~BGIP_SolverBranchAndBound ()

Public Member Functions inherited from BGIP_IncrementalSolverInterface_T< JP >
	BGIP_IncrementalSolverInterface_T (const boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > &bg, size_t nrDesiredSolutions=INT_MAX)

virtual boost::shared_ptr < JointPolicyDiscretePure >	GetNewJpol () const
	this gives a implementation of GetNewJpol (specified in BayesianGameIdenticalPayoffSolver) More...

Public Member Functions inherited from BGIP_IncrementalSolverInterface
bool	AllSolutionsHaveBeenReturned () const

	BGIP_IncrementalSolverInterface (const boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > &bg, size_t nrDesiredSolutions=INT_MAX)

bool	GetNextJointPolicyAndValue (boost::shared_ptr< JointPolicyDiscretePure > &jpol, double &value)
	Gets the next solution from the Incremental CBG solver. More...

virtual	~BGIP_IncrementalSolverInterface ()

Public Member Functions inherited from BayesianGameIdenticalPayoffSolver
void	AddSolution (const JointPolicyPureVector &jp, double value)

void	AddSolution (const JointPolicyPureVectorForClusteredBG &jp, double value)

void	AddSolution (LIndex jpolIndex, double value)

	BayesianGameIdenticalPayoffSolver (const boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > &bg, size_t nrDesiredSolutions=1)
	(default) Constructor More...

double	Evaluate (const JointPolicyPureVector &jpolBG) const

double	Evaluate (const JointPolicyPureVectorForClusteredBG &jpolBG) const

boost::shared_ptr< const BayesianGameIdenticalPayoffInterface >	GetBGIPI () const

double	GetExpectedReward () const

const boost::shared_ptr < JointPolicy >	GetJointPolicy () const

const JointPolicyPureVector &	GetJointPolicyPureVector () const

boost::shared_ptr< JPPVValuePair >	GetNextSolutionJPPV () const

boost::shared_ptr < PartialJPDPValuePair >	GetNextSolutionPJPDP () const

size_t	GetNrDesiredSolutions () const

size_t	GetNrFoundSolutions () const
	Gets the found number of solutions. More...

double	GetPayoff () const

std::ofstream *	GetResultsOFStream () const

std::ofstream *	GetTimingsOFStream () const

bool	GetWriteAnyTimeResults () const

bool	IsEmptyJPPV () const

bool	IsEmptyPJPDP () const

void	PopNextSolutionJPPV ()

void	PopNextSolutionPJPDP ()

void	SaveSolution (const std::string &filename) const

void	SetAnyTimeResults (bool turn_on, std::ofstream results, std::ofstream timings)
	Turns Anytime results on and of. More...

virtual void	SetDeadline (double deadlineInSeconds)
	To limit the amount of time the solver uses. More...

void	SetNrDesiredSolutions (size_t n)
	Gets the desired number of solutions to be returned. More...

std::string	SoftPrintSolution () const

virtual	~BayesianGameIdenticalPayoffSolver ()
	Destructor. More...

Private Member Functions
void	ComputeCompleteInformationValues ()
	Computes the "complete information" heuristic values for all joint types. More...

std::vector< double >	ComputeMinContributionValues () const

void	ComputeValidJointActionExtensions (BGIP_BnB_NodePtr node, std::vector< Index > &valid_JAs)
	returns std::vector with all joint action indices that are valid. More...

void	ComputeValidJointActions (Index jt_bgI, std::vector< Index > &valid_JAs, BGIP_BnB_NodePtr node)
	the following computes the valid joint actions for jt_bgI. More...

void	ComputeValidJointActionsOld (BGIP_BnB_NodePtr node, Index jt_bgI, std::vector< Index > &valid_JAs)
	computes the valid joint actions in a slow manner but always works correctly. More...

double	ComputeValueOfFullySpecifiedPolicy (BGIP_BnB_NodePtr node)

void	ConvertNodeToPolicyAndAddToSolution (BGIP_BnB_NodePtr node, double value)

void	Expand (BGIP_BnB_NodePtr node, Index JA)

void	ExpandAllExtensions (BGIP_BnB_NodePtr node)

void	GenerateJointActions (const std::vector< Index > &valid_action_set, std::vector< Index > &curr_JA, std::vector< Index > &valid_JAs, Index agentI)

void	GenerateJointActions_ProcessAction (const std::vector< Index > &valid_action_set, std::vector< Index > &curr_JA, std::vector< Index > &valid_JAs, Index agentI, Index actionI)

double	GetContribution (Index jtI, Index jaI) const
	Get the contribution of a (joint type,joint action) pair. More...

Index	GetDepthFirstSpecified (Index agentI, Index typeI, BGIP_BnB_NodePtr node) const

Index	GetJTIndexMapping (Index i, BGIP_BnB_NodePtr node) const
	Returns the i-th joint type for which a joint action will be selected. More...

double	GetPerJPRatio (size_t s) const

void	Pop (BGIP_BnB_NodePtr node)

void	PopAndDeleteNode (BGIP_BnB_NodePtr node)

void	PrintStatistics (Index i) const

void	ProcessFullySpecifiedNode (BGIP_BnB_NodePtr node)

void	Prune (double value)

void	ReComputeH (BGIP_BnB_NodePtr node)

void	ReOrderJointTypes (std::vector< Index > &jtIndexMapping)

void	ReOrderJointTypes (const std::vector< Index > &origJTIndexMapping, const std::vector< double > &origValues, const std::vector< double > &orderedValues, std::vector< Index > &jtIndexMapping) const
	Orders the joint type mapping origJTIndexMapping (with values origValues) according to orderValues. More...

double	ReSolve ()

void	SortAscending (std::vector< double > &values) const
	Sorts a std::vector in ascending order. More...

void	SortDescending (std::vector< double > &values) const
	Sorts a std::vector in descending order. More...

Private Attributes
BGIP_BnB_NodePtr	_m_bestNode
	the best node found so far... More...

boost::shared_ptr< const BayesianGameIdenticalPayoffInterface >	_m_bgip
	Pointer to the BG we're solving. More...

double	_m_CBGlowerBound

double	_m_CBGupperBound

std::vector< double >	_m_completeInformationValues

std::vector< std::vector< Index > >	_m_depthFirstSpecified
	_m_depthFirstSpecified[agentI][typeI] specifies at what depth typeI of agentI is first specified. More...

bool	_m_expandAll

std::vector< std::vector< Index > >	_m_jaToIndCache

std::vector< Index >	_m_jtIndexMapping
	_m_jtIndexMapping[i] the i-th joint type for which a joint action will be selected, _m_jtIndexMapping[i] = j means that the j-th joint-type of the BG will be the i-th for which a . More...

BGIP_BnB::BnB_JointTypeOrdering	_m_jtOrdering
	The ordering of joint types used in the search. More...

Index	_m_maxDepth
	the maximum depth of a search node (i.e., the depth at which it is fully More...

double	_m_maxLowerBound

const std::vector< size_t > &	_m_nrActions

size_t	_m_nrAgents

size_t	_m_nrJTs

size_t	_m_nrNodesExpanded

size_t	_m_nrNodesFullySpecified

size_t	_m_nrNodesPruned

size_t	_m_nrSolutionsComputed
	The number of solutions we already computed for the incremental solver. More...

std::priority_queue < BGIP_BnB_NodePtr > *	_m_openQueue
	The priority queue keeping track of all the open nodes in the search. More...

bool	_m_reComputeH

bool	_m_reComputeJTIndexMapping

bool	_m_solved
	Whether we already called Solve(). More...

int	_m_verbosity
	Level of verboseness of the solver. More...

Additional Inherited Members
Protected Member Functions inherited from BayesianGameIdenticalPayoffSolver
virtual void	CheckDeadline (const std::string &errorMessage) const
	Checks whether the deadline has expired. Throws EDeadline. More...

virtual void	InitDeadline ()
	Should be called at the beginning of Solve(). More...

Protected Attributes inherited from BGIP_IncrementalSolverInterface
size_t	_m_nrSolutionsReturned
	The number of solutions we already returned (not computed) More...

Detailed Description

template<class JP>
class BGIP_SolverBranchAndBound< JP >

BGIP_SolverBranchAndBound is a class that performs Branch-and-Bound search for identical payoff Bayesian Games.

The template argument JP represents the joint policy class the solver should return.

Constructor & Destructor Documentation

template<class JP>

BGIP_SolverBranchAndBound< JP >::BGIP_SolverBranchAndBound	(	const boost::shared_ptr< const BayesianGameIdenticalPayoffInterface > &	bg,
		int	verbose = `0`,
		size_t	nrDesiredSolutions = `1`,
		bool	expandAll = `false`,
		BGIP_BnB::BnB_JointTypeOrdering	jtOrdering = `BGIP_BnB::IdentityMapping`,
		bool	reComputeHeur = `false`
	)

inline

Constructor.

Directly Associates a problem with the planner Information regarding the problem is used to construct a joint policy of the proper shape.

References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_BnB::ConsistentMaxContribution, BGIP_BnB::ConsistentMaxContributionDifference, BGIP_BnB::ConsistentMinContribution, and BGIP_BnB::UNSPECIFIED_ACTION.

template<class JP>

BGIP_SolverBranchAndBound< JP >::~BGIP_SolverBranchAndBound ( )

inline

References BGIP_SolverBranchAndBound< JP >::_m_openQueue.

Member Function Documentation

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ComputeCompleteInformationValues ( )

inlineprivate

Computes the "complete information" heuristic values for all joint types.

References BayesianGameIdenticalPayoffSolver::CheckDeadline(), BGIP_SolverBranchAndBound< JP >::GetContribution(), and PrintTools::SoftPrintVector().

Referenced by BGIP_SolverBranchAndBound< JP >::Solve().

template<class JP>

std::vector<double> BGIP_SolverBranchAndBound< JP >::ComputeMinContributionValues ( ) const

inlineprivate

References BGIP_SolverBranchAndBound< JP >::GetContribution(), and PrintTools::SoftPrintVector().

Referenced by BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionExtensions	(	BGIP_BnB_NodePtr	node,
		std::vector< Index > &	valid_JAs
	)

inlineprivate

returns std::vector with all joint action indices that are valid.

References BGIP_SolverBranchAndBound< JP >::ComputeValidJointActions(), BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionsOld(), VectorTools::Equal(), BGIP_SolverBranchAndBound< JP >::GetJTIndexMapping(), and PrintTools::SoftPrintVector().

Referenced by BGIP_SolverBranchAndBound< JP >::ExpandAllExtensions().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ComputeValidJointActions	(	Index	jt_bgI,
		std::vector< Index > &	valid_JAs,
		BGIP_BnB_NodePtr	node
	)

inlineprivate

the following computes the valid joint actions for jt_bgI.

when CACHE_IMPLIED_JPOL is true, it simply uses the cached implied policy: valid_action_set[agI] = _m_impliedJPol[agI][tI]; to determine the valid actions for each agent.

References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_SolverBranchAndBound< JP >::GenerateJointActions(), BGIP_SolverBranchAndBound< JP >::GetDepthFirstSpecified(), PrintTools::SoftPrintVector(), and BGIP_BnB::UNSPECIFIED_ACTION.

Referenced by BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionExtensions(), and BGIP_SolverBranchAndBound< JP >::ReComputeH().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionsOld	(	BGIP_BnB_NodePtr	node,
		Index	jt_bgI,
		std::vector< Index > &	valid_JAs
	)

inlineprivate

computes the valid joint actions in a slow manner but always works correctly.

References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_SolverBranchAndBound< JP >::GetDepthFirstSpecified(), and BGIP_BnB::UNSPECIFIED_ACTION.

Referenced by BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionExtensions().

template<class JP>

double BGIP_SolverBranchAndBound< JP >::ComputeValueOfFullySpecifiedPolicy ( BGIP_BnB_NodePtr node )

inlineprivate

References BGIP_SolverBranchAndBound< JP >::GetContribution(), BGIP_SolverBranchAndBound< JP >::GetDepthFirstSpecified(), and BGIP_SolverBranchAndBound< JP >::GetJTIndexMapping().

Referenced by BGIP_SolverBranchAndBound< JP >::ProcessFullySpecifiedNode().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ConvertNodeToPolicyAndAddToSolution	(	BGIP_BnB_NodePtr	node,
		double	value
	)

inlineprivate

References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BayesianGameIdenticalPayoffSolver::AddSolution(), BGIP_SolverBranchAndBound< JP >::GetDepthFirstSpecified(), and BGIP_IncrementalSolverInterface_T< JP >::GetNewJpol().

Referenced by BGIP_SolverBranchAndBound< JP >::ProcessFullySpecifiedNode().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::Expand	(	BGIP_BnB_NodePtr	node,
		Index	JA
	)

inlineprivate

References BGIP_SolverBranchAndBound< JP >::_m_CBGlowerBound, BGIP_SolverBranchAndBound< JP >::GetContribution(), and BGIP_SolverBranchAndBound< JP >::ReComputeH().

Referenced by BGIP_SolverBranchAndBound< JP >::ExpandAllExtensions().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ExpandAllExtensions ( BGIP_BnB_NodePtr node )

inlineprivate

References BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionExtensions(), BGIP_SolverBranchAndBound< JP >::Expand(), and BGIP_SolverBranchAndBound< JP >::Pop().

Referenced by BGIP_SolverBranchAndBound< JP >::ReSolve().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::GenerateJointActions	(	const std::vector< Index > &	valid_action_set,
		std::vector< Index > &	curr_JA,
		std::vector< Index > &	valid_JAs,
		Index	agentI
	)

inlineprivate

References BGIP_SolverBranchAndBound< JP >::GenerateJointActions_ProcessAction(), PrintTools::SoftPrintVector(), and BGIP_BnB::UNSPECIFIED_ACTION.

Referenced by BGIP_SolverBranchAndBound< JP >::ComputeValidJointActions(), and BGIP_SolverBranchAndBound< JP >::GenerateJointActions_ProcessAction().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::GenerateJointActions_ProcessAction	(	const std::vector< Index > &	valid_action_set,
		std::vector< Index > &	curr_JA,
		std::vector< Index > &	valid_JAs,
		Index	agentI,
		Index	actionI
	)

inlineprivate

References BGIP_SolverBranchAndBound< JP >::GenerateJointActions(), and PrintTools::SoftPrintVector().

Referenced by BGIP_SolverBranchAndBound< JP >::GenerateJointActions().

template<class JP>

double BGIP_SolverBranchAndBound< JP >::GetContribution	(	Index	jtI,
		Index	jaI
	)		const

inlineprivate

Get the contribution of a (joint type,joint action) pair.

Referenced by BGIP_SolverBranchAndBound< JP >::ComputeCompleteInformationValues(), BGIP_SolverBranchAndBound< JP >::ComputeMinContributionValues(), BGIP_SolverBranchAndBound< JP >::ComputeValueOfFullySpecifiedPolicy(), BGIP_SolverBranchAndBound< JP >::Expand(), and BGIP_SolverBranchAndBound< JP >::ReComputeH().

template<class JP>

Index BGIP_SolverBranchAndBound< JP >::GetDepthFirstSpecified	(	Index	agentI,
		Index	typeI,
		BGIP_BnB_NodePtr	node
	)		const

inlineprivate

Referenced by BGIP_SolverBranchAndBound< JP >::ComputeValidJointActions(), BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionsOld(), BGIP_SolverBranchAndBound< JP >::ComputeValueOfFullySpecifiedPolicy(), and BGIP_SolverBranchAndBound< JP >::ConvertNodeToPolicyAndAddToSolution().

template<class JP>

Index BGIP_SolverBranchAndBound< JP >::GetJTIndexMapping	(	Index	i,
		BGIP_BnB_NodePtr	node
	)		const

inlineprivate

Returns the i-th joint type for which a joint action will be selected.

Referenced by BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionExtensions(), BGIP_SolverBranchAndBound< JP >::ComputeValueOfFullySpecifiedPolicy(), and BGIP_SolverBranchAndBound< JP >::ReComputeH().

template<class JP>

bool BGIP_SolverBranchAndBound< JP >::GetNextJointPolicyAndValueSpecific	(	boost::shared_ptr< JointPolicyDiscretePure > &	jpol,
		double &	value
	)

inlinevirtual

The specific implementation that should be implemented by the derived class:

Implements BGIP_IncrementalSolverInterface.

References BayesianGameIdenticalPayoffSolver::GetNextSolutionJPPV(), BayesianGameIdenticalPayoffSolver::GetNextSolutionPJPDP(), BayesianGameIdenticalPayoffSolver::GetNrFoundSolutions(), BayesianGameIdenticalPayoffSolver::IsEmptyJPPV(), BayesianGameIdenticalPayoffSolver::IsEmptyPJPDP(), BayesianGameIdenticalPayoffSolver::PopNextSolutionJPPV(), BayesianGameIdenticalPayoffSolver::PopNextSolutionPJPDP(), BGIP_SolverBranchAndBound< JP >::ReSolve(), and BGIP_SolverBranchAndBound< JP >::Solve().

template<class JP>

size_t BGIP_SolverBranchAndBound< JP >::GetNrNodesExpanded ( ) const

inline

template<class JP>

double BGIP_SolverBranchAndBound< JP >::GetPerJPRatio ( size_t s ) const

inlineprivate

References Globals::CastLIndexToDouble().

Referenced by BGIP_SolverBranchAndBound< JP >::PrintStatistics(), and BGIP_SolverBranchAndBound< JP >::ReSolve().

template<class JP>

bool BGIP_SolverBranchAndBound< JP >::IsExactSolver ( ) const

inlinevirtual

Methods should indicated whether they compute exact (optimal) solutions or not.

Implements BayesianGameIdenticalPayoffSolver.

template<class JP>

void BGIP_SolverBranchAndBound< JP >::Pop ( BGIP_BnB_NodePtr node )

inlineprivate

Referenced by BGIP_SolverBranchAndBound< JP >::ExpandAllExtensions(), BGIP_SolverBranchAndBound< JP >::PopAndDeleteNode(), BGIP_SolverBranchAndBound< JP >::ProcessFullySpecifiedNode(), and BGIP_SolverBranchAndBound< JP >::Prune().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::PopAndDeleteNode ( BGIP_BnB_NodePtr node )

inlineprivate

References BGIP_SolverBranchAndBound< JP >::Pop().

Referenced by BGIP_SolverBranchAndBound< JP >::ProcessFullySpecifiedNode(), and BGIP_SolverBranchAndBound< JP >::Prune().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::PrintStatistics ( Index i ) const

inlineprivate

References BGIP_SolverBranchAndBound< JP >::GetPerJPRatio(), and PRINTNUM.

Referenced by BGIP_SolverBranchAndBound< JP >::ReSolve().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ProcessFullySpecifiedNode ( BGIP_BnB_NodePtr node )

inlineprivate

References BGIP_SolverBranchAndBound< JP >::ComputeValueOfFullySpecifiedPolicy(), BGIP_SolverBranchAndBound< JP >::ConvertNodeToPolicyAndAddToSolution(), BayesianGameIdenticalPayoffSolver::GetNrDesiredSolutions(), BGIP_SolverBranchAndBound< JP >::Pop(), BGIP_SolverBranchAndBound< JP >::PopAndDeleteNode(), and BGIP_SolverBranchAndBound< JP >::Prune().

Referenced by BGIP_SolverBranchAndBound< JP >::ReSolve().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::Prune ( double value )

inlineprivate

References BGIP_SolverBranchAndBound< JP >::_m_openQueue, BGIP_SolverBranchAndBound< JP >::Pop(), and BGIP_SolverBranchAndBound< JP >::PopAndDeleteNode().

Referenced by BGIP_SolverBranchAndBound< JP >::ProcessFullySpecifiedNode().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ReComputeH ( BGIP_BnB_NodePtr node )

inlineprivate

References BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_SolverBranchAndBound< JP >::ComputeValidJointActions(), BGIP_BnB::ConsistentMaxContribution, BGIP_BnB::ConsistentMaxContributionDifference, BGIP_BnB::ConsistentMinContribution, BGIP_SolverBranchAndBound< JP >::GetContribution(), BGIP_SolverBranchAndBound< JP >::GetJTIndexMapping(), BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes(), PrintTools::SoftPrintVector(), BGIP_SolverBranchAndBound< JP >::SortDescending(), and BGIP_BnB::UNSPECIFIED_ACTION.

Referenced by BGIP_SolverBranchAndBound< JP >::Expand().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes ( std::vector< Index > & jtIndexMapping )

inlineprivate

References BGIP_SolverBranchAndBound< JP >::_m_completeInformationValues, BGIP_SolverBranchAndBound< JP >::_m_nrAgents, BGIP_BnB::BasisTypes, BGIP_SolverBranchAndBound< JP >::ComputeMinContributionValues(), BGIP_BnB::ConsistentMaxContribution, BGIP_BnB::ConsistentMaxContributionDifference, BGIP_BnB::ConsistentMinContribution, BGIP_BnB::DescendingProbability, BGIP_BnB::IdentityMapping, BGIP_BnB::MaxContribution, BGIP_BnB::MaxContributionDifference, BGIP_BnB::MinContribution, PrintTools::SoftPrintVector(), BGIP_SolverBranchAndBound< JP >::SortAscending(), BGIP_SolverBranchAndBound< JP >::SortDescending(), and BGIP_BnB::UNSPECIFIED_ACTION.

Referenced by BGIP_SolverBranchAndBound< JP >::ReComputeH(), and BGIP_SolverBranchAndBound< JP >::Solve().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes	(	const std::vector< Index > &	origJTIndexMapping,
		const std::vector< double > &	origValues,
		const std::vector< double > &	orderedValues,
		std::vector< Index > &	jtIndexMapping
	)		const

inlineprivate

Orders the joint type mapping origJTIndexMapping (with values origValues) according to orderValues.

References BGIP_BnB::UNSPECIFIED_ACTION.

template<class JP>

double BGIP_SolverBranchAndBound< JP >::ReSolve ( )

inlineprivate

References BGIP_SolverBranchAndBound< JP >::_m_CBGlowerBound, BayesianGameIdenticalPayoffSolver::CheckDeadline(), BGIP_SolverBranchAndBound< JP >::ExpandAllExtensions(), BayesianGameIdenticalPayoffSolver::GetBGIPI(), BayesianGameIdenticalPayoffSolver::GetNrDesiredSolutions(), BayesianGameIdenticalPayoffSolver::GetNrFoundSolutions(), BayesianGameIdenticalPayoffSolver::GetPayoff(), BGIP_SolverBranchAndBound< JP >::GetPerJPRatio(), BGIP_SolverBranchAndBound< JP >::PrintStatistics(), Globals::PROB_PRECISION, BGIP_SolverBranchAndBound< JP >::ProcessFullySpecifiedNode(), and PrintTools::SoftPrintVector().

Referenced by BGIP_SolverBranchAndBound< JP >::GetNextJointPolicyAndValueSpecific(), and BGIP_SolverBranchAndBound< JP >::Solve().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::SetCBGlowerBound ( double lowerbound )

inlinevirtual

Implements BayesianGameIdenticalPayoffSolver.

template<class JP>

void BGIP_SolverBranchAndBound< JP >::SetCBGupperBound ( double upperbound )

inlinevirtual

Implements BayesianGameIdenticalPayoffSolver.

template<class JP>

double BGIP_SolverBranchAndBound< JP >::Solve ( )

inlinevirtual

The methods that performs the planning.

Returns the expected reward.

Implements BayesianGameIdenticalPayoffSolver.

References BGIP_SolverBranchAndBound< JP >::ComputeCompleteInformationValues(), BayesianGameIdenticalPayoffSolver::InitDeadline(), BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes(), BGIP_SolverBranchAndBound< JP >::ReSolve(), and PrintTools::SoftPrintVector().

Referenced by BGIP_SolverBranchAndBound< JP >::GetNextJointPolicyAndValueSpecific().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::SortAscending ( std::vector< double > & values ) const

inlineprivate

Sorts a std::vector in ascending order.

Referenced by BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes(), and BGIP_SolverBranchAndBound< JP >::SortDescending().

template<class JP>

void BGIP_SolverBranchAndBound< JP >::SortDescending ( std::vector< double > & values ) const

inlineprivate

Sorts a std::vector in descending order.

References BGIP_SolverBranchAndBound< JP >::SortAscending().

Referenced by BGIP_SolverBranchAndBound< JP >::ReComputeH(), and BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes().

Member Data Documentation

template<class JP>

BGIP_BnB_NodePtr BGIP_SolverBranchAndBound< JP >::_m_bestNode

private

the best node found so far...

template<class JP>

boost::shared_ptr<const BayesianGameIdenticalPayoffInterface> BGIP_SolverBranchAndBound< JP >::_m_bgip

private

Pointer to the BG we're solving.

template<class JP>

double BGIP_SolverBranchAndBound< JP >::_m_CBGlowerBound

private

Referenced by BGIP_SolverBranchAndBound< JP >::Expand(), and BGIP_SolverBranchAndBound< JP >::ReSolve().

template<class JP>

double BGIP_SolverBranchAndBound< JP >::_m_CBGupperBound

private

template<class JP>

std::vector<double> BGIP_SolverBranchAndBound< JP >::_m_completeInformationValues

private

Referenced by BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes().

template<class JP>

std::vector< std::vector< Index > > BGIP_SolverBranchAndBound< JP >::_m_depthFirstSpecified

private

_m_depthFirstSpecified[agentI][typeI] specifies at what depth typeI of agentI is first specified.

This is computed when the ordering is determined.

template<class JP>

bool BGIP_SolverBranchAndBound< JP >::_m_expandAll

private

template<class JP>

std::vector<std::vector<Index> > BGIP_SolverBranchAndBound< JP >::_m_jaToIndCache

private

template<class JP>

std::vector<Index> BGIP_SolverBranchAndBound< JP >::_m_jtIndexMapping

private

_m_jtIndexMapping[i] the i-th joint type for which a joint action will be selected, _m_jtIndexMapping[i] = j means that the j-th joint-type of the BG will be the i-th for which a .

so

i is the order index: i_oI
j is the BG-index: j_bgI

template<class JP>

BGIP_BnB::BnB_JointTypeOrdering BGIP_SolverBranchAndBound< JP >::_m_jtOrdering

private

The ordering of joint types used in the search.

template<class JP>

Index BGIP_SolverBranchAndBound< JP >::_m_maxDepth

private

the maximum depth of a search node (i.e., the depth at which it is fully

template<class JP>

double BGIP_SolverBranchAndBound< JP >::_m_maxLowerBound

private

template<class JP>

const std::vector<size_t>& BGIP_SolverBranchAndBound< JP >::_m_nrActions

private

template<class JP>

size_t BGIP_SolverBranchAndBound< JP >::_m_nrAgents

private

Referenced by BGIP_SolverBranchAndBound< JP >::BGIP_SolverBranchAndBound(), BGIP_SolverBranchAndBound< JP >::ComputeValidJointActions(), BGIP_SolverBranchAndBound< JP >::ComputeValidJointActionsOld(), BGIP_SolverBranchAndBound< JP >::ConvertNodeToPolicyAndAddToSolution(), BGIP_SolverBranchAndBound< JP >::ReComputeH(), and BGIP_SolverBranchAndBound< JP >::ReOrderJointTypes().

template<class JP>

size_t BGIP_SolverBranchAndBound< JP >::_m_nrJTs

private

template<class JP>

size_t BGIP_SolverBranchAndBound< JP >::_m_nrNodesExpanded

private

template<class JP>

size_t BGIP_SolverBranchAndBound< JP >::_m_nrNodesFullySpecified

private

template<class JP>

size_t BGIP_SolverBranchAndBound< JP >::_m_nrNodesPruned

private

template<class JP>

size_t BGIP_SolverBranchAndBound< JP >::_m_nrSolutionsComputed

private

The number of solutions we already computed for the incremental solver.

template<class JP>

std::priority_queue<BGIP_BnB_NodePtr>* BGIP_SolverBranchAndBound< JP >::_m_openQueue

private

The priority queue keeping track of all the open nodes in the search.

Referenced by BGIP_SolverBranchAndBound< JP >::Prune(), and BGIP_SolverBranchAndBound< JP >::~BGIP_SolverBranchAndBound().

template<class JP>

bool BGIP_SolverBranchAndBound< JP >::_m_reComputeH

private

template<class JP>

bool BGIP_SolverBranchAndBound< JP >::_m_reComputeJTIndexMapping

private

template<class JP>

bool BGIP_SolverBranchAndBound< JP >::_m_solved

private

Whether we already called Solve().

template<class JP>

int BGIP_SolverBranchAndBound< JP >::_m_verbosity

private

Level of verboseness of the solver.

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

template<class JP> class BGIP_SolverBranchAndBound< JP >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class JP>
class BGIP_SolverBranchAndBound< JP >