pipsipmpp::DistributedTree Class Reference

Represents the hierarchical structure of a distributed optimization problem. More...

#include <DistributedTree.h>

Public Member Functions
long long	getN () const
	Get the number of primal variables in this node and its children.
long long	getMY () const
	Get the number of equality constraints in this node and its children.
long long	getMYL () const
	Get the number of linking equality constraints in this node and its children.
long long	getMZ () const
	Get the number of inequality constraints in this node and its children.
long long	getMZL () const
	Get the number of linking inequality constraints in this node and its children.
virtual std::unique_ptr< DistributedTree >	clone () const =0
	Create a deep copy of this tree node.
virtual void	computeGlobalSizes ()=0
	Computes the total problem dimensions for the subtree rooted at this node.
void	getGlobalSizes (long long &n, long long &my, long long &mz) const
	Get the total problem dimensions for the subtree rooted at this node.
void	getGlobalSizes (long long &n, long long &my, long long &myl, long long &mz, long long &mzl) const
	Get the total problem dimensions including linking constraints for the subtree rooted at this node.
void	assignProcesses (MPI_Comm comm=MPI_COMM_WORLD)
	Assigns MPI processes to the nodes of the tree.
virtual	~DistributedTree ()=default
	Virtual destructor.
bool	distributedPreconditionerActive () const
	Check if a distributed preconditioner is active.
void	startMonitors ()
	Start performance monitors for IPM iterations.
void	startNodeMonitors ()
	Start performance monitors for this node.
void	stopMonitors ()
	Stop performance monitors for IPM iterations.
void	stopNodeMonitors ()
	Stop performance monitors for this node.
void	getSyncInfo (int myRank, int &syncNeeded, int &sendOrRecv, int &toFromCPU)
	Get synchronization information for load balancing.
virtual std::unique_ptr< DistributedSymmetricMatrix >	createQ () const =0
	Create the Hessian matrix (Q) for this node. Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createc () const =0
	Create the objective vector (c) for this node. Pure virtual.
virtual double	createobjconst () const =0
	Create the objective constant for this node. Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createxlow () const =0
	Create the lower bound vector for primal variables (x). Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createixlow () const =0
	Create the indicator vector for lower bounds on x. Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createxupp () const =0
	Create the upper bound vector for primal variables (x). Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createixupp () const =0
	Create the indicator vector for upper bounds on x. Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	create_variable_integrality_type () const =0
	Create the vector indicating the integrality type of variables. Pure virtual.
virtual std::unique_ptr< DistributedMatrix >	createA () const =0
	Create the equality constraint matrix (A) for this node. Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createb () const =0
	Create the right-hand side vector for equality constraints (b). Pure virtual.
virtual std::unique_ptr< DistributedMatrix >	createC () const =0
	Create the inequality constraint matrix (C) for this node. Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createclow () const =0
	Create the lower bound vector for inequality constraints. Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createiclow () const =0
	Create the indicator vector for lower bounds on inequality constraints. Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createcupp () const =0
	Create the upper bound vector for inequality constraints. Pure virtual.
virtual std::unique_ptr< DistributedVector< double > >	createicupp () const =0
	Create the indicator vector for upper bounds on inequality constraints. Pure virtual.
template<typename T>
std::unique_ptr< DistributedVector< T > >	new_primal_vector (bool empty=false) const
	Create a new distributed vector for primal variables.
template<typename T>
std::unique_ptr< DistributedVector< T > >	new_equalities_dual_vector (bool empty=false) const
	Create a new distributed vector for equality constraint duals.
template<typename T>
std::unique_ptr< DistributedVector< T > >	new_inequalities_dual_vector (bool empty=false) const
	Create a new distributed vector for inequality constraint duals.
std::unique_ptr< DistributedVector< double > >	new_right_hand_side () const
	Create a new distributed vector for the right-hand side of the augmented system.
const DistributedTree *	getSubRoot () const
	Get the sub-root of this node for hierarchical structures.
const std::vector< std::unique_ptr< DistributedTree > > &	getChildren () const
	Get the children of this node.
unsigned int	nChildren () const
	Get the number of children of this node.
MPI_Comm	getCommWorkers () const
	Get the MPI communicator for the workers of this node.
virtual int	nx () const =0
	Get the local number of primal variables. Pure virtual.
virtual int	my () const =0
	Get the local number of equality constraints. Pure virtual.
virtual int	myl () const =0
	Get the local number of linking equality constraints. Pure virtual.
virtual int	mzl () const =0
	Get the local number of linking inequality constraints. Pure virtual.
virtual int	mz () const =0
	Get the local number of inequality constraints. Pure virtual.
virtual int	id () const =0
	Get the ID of this node. Pure virtual.
double	processLoad () const
	Get the processing load of this node and its subtree.
bool	isHierarchicalRoot () const
	Check if this node is a hierarchical root.
void	setHierarchicalInnerRoot ()
	Set this node as a hierarchical inner root.
bool	isHierarchicalInnerRoot () const
	Check if this node is an hierarchical inner root.
void	setHierarchicalInnerLeaf ()
	Set this node as a hierarchical inner leaf.
bool	isHierarchicalInnerLeaf () const
	Check if this node is an hierarchical inner leaf.
virtual std::unique_ptr< DistributedTree >	shaveDenseBorder (int nx_to_shave, int myl_to_shave, int mzl_to_shave, std::unique_ptr< DistributedTree > pointer_to_this)=0
	Shave off a dense border from the problem structure. Pure virtual. Adds an additional top layer.
virtual std::pair< int, int >	splitTree (int n_layers, DistributedProblem *data)=0
	Split the tree to introduce more layers for hierarchical parallelism. Pure virtual. Adds an additional layer below this one by adding sqrt(nChildren) children each with sqrt(nChildren) of our current children.
virtual std::unique_ptr< DistributedTree >	switchToHierarchicalTree (DistributedProblem *&data, std::unique_ptr< DistributedTree > pointer_to_this)=0
	Switch to a hierarchical tree structure. Pure virtual.
void	printProcessTree () const
	Print the process tree to standard output.
bool	was_A0_moved_to_border () const
	Check if the A0 matrix was moved to the border.

Static Public Member Functions
static bool	balanceLoad ()
	Perform load balancing. Currently disabled.

Public Attributes
StochNodeResourcesMonitor	resMon
	Monitors resources for stochastic nodes.

Static Public Attributes
static Timer	iterMon
	Timer for IPM iterations.

Protected Member Functions
	DistributedTree (const DistributedTree &other)
	Copy constructor.
void	appendPrintTreeLayer (std::vector< std::string > &layer_outputs, unsigned int level) const
	Appends a string representation of a tree layer to a vector of strings.
	DistributedTree ()=default
	Default constructor.
void	toMonitorsList (std::list< NodeTimer > &)
	Serialize monitor data to a list.
void	fromMonitorsList (std::list< NodeTimer > &)
	Deserialize monitor data from a list.
void	computeNodeTotal ()
	Compute total execution time for this node.
void	saveCurrentCPUState ()
	Save the current CPU assignment for this node and its children.

Static Protected Member Functions
static void	mapChildrenToNSubTrees (std::vector< unsigned int > &map_child_to_sub_tree, unsigned int n_children, unsigned int n_subtrees)
	Maps a number of children to a number of subtrees.

Protected Attributes
MPI_Comm	commWrkrs {MPI_COMM_NULL}
	MPI communicator for the workers assigned to this subtree.
std::vector< int >	myProcs
	Ranks of processes assigned to this node.
std::vector< int >	myOldProcs
	Ranks of processes previously assigned to this node (used for load balancing).
MPI_Comm	commP2ZeroW {MPI_COMM_NULL}
	Communicator between preconditioner (rank P+1) and the root worker (rank 0).
long long	N {0}
	Total number of primal variables in the subtree rooted at this node.
long long	MY {0}
	Total number of equality constraints in the subtree rooted at this node.
long long	MZ {0}
	Total number of inequality constraints in the subtree rooted at this node.
long long	MYL {0}
	Total number of linking equality constraints in the subtree rooted at this node.
long long	MZL {0}
	Total number of linking inequality constraints in the subtree rooted at this node.
int	np {-1}
	Number of variables in the parent node.
double	IPMIterExecTIME {-1.0}
	Execution time for an IPM iteration, used for load balancing. Not used since loads of nodes and processes are currently not computed.
std::vector< std::unique_ptr< DistributedTree > >	children
	Children of this node in the tree.
std::unique_ptr< DistributedTree >	sub_root {}
	Sub-tree for hierarchical approach. Implies sub structure inside the current Bmat.
bool	is_hierarchical_root {false}
	Flag indicating if this is the root of a hierarchical problem structure.
bool	is_hierarchical_inner_root {false}
	Flag indicating if this is an inner root in a hierarchical structure.
bool	is_hierarchical_inner_leaf {false}
	Flag indicating if this is an inner leaf in a hierarchical structure.
bool	was_a0_moved_to_border {false}
	Flag indicating if the A0 matrix was moved to the border.

Static Protected Attributes
static int	rankPrcnd
	Rank of the preconditioner process.
static int	rankZeroW
	Rank of the root worker process (usually 0).
static int	rankMe
	Rank of the current process.
static int	numProcs
	Total number of available MPI processes.

Detailed Description

Represents the hierarchical structure of a distributed optimization problem.

This is an abstract base class that defines the tree structure of a stochastic or distributed optimization problem. Each node in the tree can represent a subproblem, a scenario, a stage, or a block. The tree structure is used to manage the distribution of data and computations across multiple processes in an MPI environment.

Derived classes are responsible for implementing the pure virtual functions to provide the actual problem data (matrices, vectors, etc.) for each node.

Constructor & Destructor Documentation

DistributedTree()

pipsipmpp::DistributedTree::DistributedTree ( const DistributedTree & other )

protected

Copy constructor.

Parameters

other

The DistributedTree to copy.

Member Function Documentation

appendPrintTreeLayer()

void pipsipmpp::DistributedTree::appendPrintTreeLayer ( std::vector< std::string > & layer_outputs, unsigned int level ) const

protected

Appends a string representation of a tree layer to a vector of strings.

Parameters

[in,out]	layer_outputs	Vector of strings, each representing a layer.
	level	The current level in the tree to print.

assignProcesses()

void pipsipmpp::DistributedTree::assignProcesses

(

MPI_Comm

comm = MPI_COMM_WORLD

)

Assigns MPI processes to the nodes of the tree.

Parameters

comm	The MPI communicator for all available processes.

balanceLoad()

bool pipsipmpp::DistributedTree::balanceLoad ( )

static

Perform load balancing. Currently disabled.

Returns

always false

clone()

virtual std::unique_ptr< DistributedTree > pipsipmpp::DistributedTree::clone ( ) const

nodiscardpure virtual

Create a deep copy of this tree node.

Returns

copy of tree

computeGlobalSizes()

virtual void pipsipmpp::DistributedTree::computeGlobalSizes ( )

pure virtual

Computes the total problem dimensions for the subtree rooted at this node.

This is a pure virtual function that must be implemented by derived classes. It should recursively calculate the total number of variables and constraints for this node and all its descendants.

create_variable_integrality_type()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::create_variable_integrality_type ( ) const

nodiscardpure virtual

Create the vector indicating the integrality type of variables. Pure virtual.

Returns

indicators for variable types

createA()

virtual std::unique_ptr< DistributedMatrix > pipsipmpp::DistributedTree::createA ( ) const

nodiscardpure virtual

Create the equality constraint matrix (A) for this node. Pure virtual.

Returns

non-linking equality constraint matrix

createb()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createb ( ) const

nodiscardpure virtual

Create the right-hand side vector for equality constraints (b). Pure virtual.

Returns

non-linking equality right-hand-side

createC()

virtual std::unique_ptr< DistributedMatrix > pipsipmpp::DistributedTree::createC ( ) const

nodiscardpure virtual

Create the inequality constraint matrix (C) for this node. Pure virtual.

Returns

non-linking inequality constraint matrix

createc()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createc ( ) const

nodiscardpure virtual

Create the objective vector (c) for this node. Pure virtual.

Returns

objective linear coefficients vector

createclow()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createclow ( ) const

nodiscardpure virtual

Create the lower bound vector for inequality constraints. Pure virtual.

Returns

non-linking inequality constraints left-hand-side

createcupp()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createcupp ( ) const

nodiscardpure virtual

Create the upper bound vector for inequality constraints. Pure virtual.

Returns

non-linking inequality constraints right-hand-side

createiclow()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createiclow ( ) const

nodiscardpure virtual

Create the indicator vector for lower bounds on inequality constraints. Pure virtual.

Returns

indicator for active non-linking inequality constraints left-hand-side

createicupp()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createicupp ( ) const

nodiscardpure virtual

Create the indicator vector for upper bounds on inequality constraints. Pure virtual.

Returns

indicator for active non-linking inequality constraint right-hand-side

createixlow()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createixlow ( ) const

nodiscardpure virtual

Create the indicator vector for lower bounds on x. Pure virtual.

Returns

indicators for active variable lower bounds

createixupp()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createixupp ( ) const

nodiscardpure virtual

Create the indicator vector for upper bounds on x. Pure virtual.

Returns

indicator for active variable upper bounds

createobjconst()

virtual double pipsipmpp::DistributedTree::createobjconst ( ) const

nodiscardpure virtual

Create the objective constant for this node. Pure virtual.

Returns

objective constant term

createQ()

virtual std::unique_ptr< DistributedSymmetricMatrix > pipsipmpp::DistributedTree::createQ ( ) const

nodiscardpure virtual

Create the Hessian matrix (Q) for this node. Pure virtual.

Returns

objective quadratic coefficients matrix

createxlow()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createxlow ( ) const

nodiscardpure virtual

Create the lower bound vector for primal variables (x). Pure virtual.

Returns

variable lower bounds

createxupp()

virtual std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::createxupp ( ) const

nodiscardpure virtual

Create the upper bound vector for primal variables (x). Pure virtual.

Returns

variable upper bounds

distributedPreconditionerActive()

bool pipsipmpp::DistributedTree::distributedPreconditionerActive ( ) const

nodiscard

Check if a distributed preconditioner is active.

Returns

whether preconditioner is active

getChildren()

const std::vector< std::unique_ptr< DistributedTree > > & pipsipmpp::DistributedTree::getChildren ( ) const

inlinenodiscard

Get the children of this node.

Returns

the children

getCommWorkers()

MPI_Comm pipsipmpp::DistributedTree::getCommWorkers ( ) const

inlinenodiscard

Get the MPI communicator for the workers of this node.

Returns

MPI communicator for the workers

getGlobalSizes() [1/2]

void pipsipmpp::DistributedTree::getGlobalSizes	(	long long &	n,
		long long &	my,
		long long &	myl,
		long long &	mz,
		long long &	mzl ) const

Get the total problem dimensions including linking constraints for the subtree rooted at this node.

Parameters

[out]	n	Total number of primal variables.
[out]	my	Total number of equality constraints.
[out]	myl	Total number of linking equality constraints.
[out]	mz	Total number of inequality constraints.
[out]	mzl	Total number of linking inequality constraints.

getGlobalSizes() [2/2]

void pipsipmpp::DistributedTree::getGlobalSizes	(	long long &	n,
		long long &	my,
		long long &	mz ) const

Get the total problem dimensions for the subtree rooted at this node.

Parameters

[out]	n	Total number of primal variables.
[out]	my	Total number of equality constraints.
[out]	mz	Total number of inequality constraints.

getMY()

long long pipsipmpp::DistributedTree::getMY ( ) const

inlinenodiscard

Get the number of equality constraints in this node and its children.

Returns

number of non-linking equality constraints

getMYL()

long long pipsipmpp::DistributedTree::getMYL ( ) const

inlinenodiscard

Get the number of linking equality constraints in this node and its children.

Returns

number of linking equality constraints

getMZ()

long long pipsipmpp::DistributedTree::getMZ ( ) const

inlinenodiscard

Get the number of inequality constraints in this node and its children.

Returns

number of non-linking inequality constraints

getMZL()

long long pipsipmpp::DistributedTree::getMZL ( ) const

inlinenodiscard

Get the number of linking inequality constraints in this node and its children.

Returns

number of linking inequality constraints

getN()

long long pipsipmpp::DistributedTree::getN ( ) const

inlinenodiscard

Get the number of primal variables in this node and its children.

Returns

number of variables

getSubRoot()

const DistributedTree * pipsipmpp::DistributedTree::getSubRoot ( ) const

inlinenodiscard

Get the sub-root of this node for hierarchical structures.

Returns

the sub-root

getSyncInfo()

void pipsipmpp::DistributedTree::getSyncInfo	(	int	myRank,
		int &	syncNeeded,
		int &	sendOrRecv,
		int &	toFromCPU )

Get synchronization information for load balancing.

Parameters

	myRank	Rank of the process requesting info.
[out]	syncNeeded	1 if synchronization is needed, 0 otherwise.
[out]	sendOrRecv	1 for send, 0 for receive.
[out]	toFromCPU	The rank of the process to communicate with.

id()

virtual int pipsipmpp::DistributedTree::id ( ) const

nodiscardpure virtual

Get the ID of this node. Pure virtual.

Returns

ID of node

isHierarchicalInnerLeaf()

bool pipsipmpp::DistributedTree::isHierarchicalInnerLeaf ( ) const

inlinenodiscard

Check if this node is an hierarchical inner leaf.

Returns

whether node is an hierarchical inner leaf

isHierarchicalInnerRoot()

bool pipsipmpp::DistributedTree::isHierarchicalInnerRoot ( ) const

inlinenodiscard

Check if this node is an hierarchical inner root.

Returns

whether this node is an hierarchical inner root

isHierarchicalRoot()

bool pipsipmpp::DistributedTree::isHierarchicalRoot ( ) const

inlinenodiscard

Check if this node is a hierarchical root.

Returns

whether this node is a hierarchical root

mapChildrenToNSubTrees()

void pipsipmpp::DistributedTree::mapChildrenToNSubTrees ( std::vector< unsigned int > & map_child_to_sub_tree, unsigned int n_children, unsigned int n_subtrees )

staticprotected

Maps a number of children to a number of subtrees.

Parameters

[out]	map_child_to_sub_tree	Output vector mapping each child to a subtree index.
	n_children	The number of children to map.
	n_subtrees	The number of subtrees to map to.

my()

virtual int pipsipmpp::DistributedTree::my ( ) const

nodiscardpure virtual

Get the local number of equality constraints. Pure virtual.

Returns

local number of equality constraints

myl()

virtual int pipsipmpp::DistributedTree::myl ( ) const

nodiscardpure virtual

Get the local number of linking equality constraints. Pure virtual.

Returns

local number of linking equality constraints

mz()

virtual int pipsipmpp::DistributedTree::mz ( ) const

nodiscardpure virtual

Get the local number of inequality constraints. Pure virtual.

Returns

local number of linking inequality constraints

mzl()

virtual int pipsipmpp::DistributedTree::mzl ( ) const

nodiscardpure virtual

Get the local number of linking inequality constraints. Pure virtual.

Returns

local number of linking inequality constraints

nChildren()

unsigned int pipsipmpp::DistributedTree::nChildren ( ) const

inlinenodiscard

Get the number of children of this node.

Returns

the number of children

new_equalities_dual_vector()

template<typename T>

std::unique_ptr< DistributedVector< T > > pipsipmpp::DistributedTree::new_equalities_dual_vector ( bool empty = false ) const

nodiscard

Create a new distributed vector for equality constraint duals.

Template Parameters

T	The data type of the vector elements (e.g., double, int).

Parameters

empty

If true, create an empty vector.

Returns

A unique pointer to the new equality dual vector.

new_inequalities_dual_vector()

template<typename T>

std::unique_ptr< DistributedVector< T > > pipsipmpp::DistributedTree::new_inequalities_dual_vector ( bool empty = false ) const

nodiscard

Create a new distributed vector for inequality constraint duals.

Template Parameters

T	The data type of the vector elements (e.g., double, int).

Parameters

empty

If true, create an empty vector.

Returns

A unique pointer to the new inequality dual vector.

new_primal_vector()

template<typename T>

std::unique_ptr< DistributedVector< T > > pipsipmpp::DistributedTree::new_primal_vector ( bool empty = false ) const

nodiscard

Create a new distributed vector for primal variables.

Template Parameters

T	The data type of the vector elements (e.g., double, int).

Parameters

empty

If true, create an empty vector.

Returns

A unique pointer to the new primal vector.

new_right_hand_side()

std::unique_ptr< DistributedVector< double > > pipsipmpp::DistributedTree::new_right_hand_side ( ) const

nodiscard

Create a new distributed vector for the right-hand side of the augmented system.

Returns

new right-hand side

nx()

virtual int pipsipmpp::DistributedTree::nx ( ) const

nodiscardpure virtual

Get the local number of primal variables. Pure virtual.

Returns

local number of variables

processLoad()

double pipsipmpp::DistributedTree::processLoad ( ) const

nodiscard

Get the processing load of this node and its subtree.

Returns

the processing load

shaveDenseBorder()

virtual std::unique_ptr< DistributedTree > pipsipmpp::DistributedTree::shaveDenseBorder ( int nx_to_shave, int myl_to_shave, int mzl_to_shave, std::unique_ptr< DistributedTree > pointer_to_this )

nodiscardpure virtual

Shave off a dense border from the problem structure. Pure virtual. Adds an additional top layer.

Parameters

nx_to_shave	number of variables to shave off
myl_to_shave	number of linking equality rows to shave off
mzl_to_shave	number of linking inequality rows to shave off
pointer_to_this	unique pointer object to update

Returns

the tree with dense border shaved off

splitTree()

virtual std::pair< int, int > pipsipmpp::DistributedTree::splitTree ( int n_layers, DistributedProblem * data )

nodiscardpure virtual

Split the tree to introduce more layers for hierarchical parallelism. Pure virtual. Adds an additional layer below this one by adding sqrt(nChildren) children each with sqrt(nChildren) of our current children.

Parameters

n_layers	number of layers to split
data	problem to work on

Returns

number of deleted linking equality (first) and inequality (second) constraints

switchToHierarchicalTree()

virtual std::unique_ptr< DistributedTree > pipsipmpp::DistributedTree::switchToHierarchicalTree ( DistributedProblem *& data, std::unique_ptr< DistributedTree > pointer_to_this )

nodiscardpure virtual

Switch to a hierarchical tree structure. Pure virtual.

Parameters

data	problem to work on
pointer_to_this	a unique pointer object to update

Returns

the hierarchical tree

was_A0_moved_to_border()

bool pipsipmpp::DistributedTree::was_A0_moved_to_border ( ) const

inlinenodiscard

Check if the A0 matrix was moved to the border.

Returns

whether A0 was moved to border