A node of the PIP solution tree. More...

#include <ppl.hh>

Inheritance diagram for Parma_Polyhedra_Library::PIP_Tree_Node:

Classes
class	Artificial_Parameter
	Artificial parameters in PIP solution trees. More...

Public Types
typedef std::vector< Artificial_Parameter >	Artificial_Parameter_Sequence
	A type alias for a sequence of Artificial_Parameter's.

Public Member Functions
virtual PIP_Tree_Node *	clone () const =0
	Returns a pointer to a dynamically-allocated copy of `*this`.

virtual	~PIP_Tree_Node ()
	Destructor.

virtual bool	OK () const =0
	Returns `true` if and only if `*this` is well formed.

virtual const PIP_Solution_Node *	as_solution () const =0
	Returns `this` if `*this` is a solution node, 0 otherwise.

virtual const PIP_Decision_Node *	as_decision () const =0
	Returns `this` if `*this` is a decision node, 0 otherwise.

const Constraint_System &	constraints () const
	Returns the system of parameter constraints controlling `*this`. More...

Artificial_Parameter_Sequence::const_iterator	art_parameter_begin () const
	Returns a const_iterator to the beginning of local artificial parameters.

Artificial_Parameter_Sequence::const_iterator	art_parameter_end () const
	Returns a const_iterator to the end of local artificial parameters.

dimension_type	art_parameter_count () const
	Returns the number of local artificial parameters.

void	print (std::ostream &s, int indent=0) const
	Prints on `s` the tree rooted in `*this`. More...

void	ascii_dump (std::ostream &s) const
	Dumps to `s` an ASCII representation of `*this`.

bool	ascii_load (std::istream &s)
	Loads from `s` an ASCII representation (as produced by ascii_dump(std::ostream&) const) and sets `*this` accordingly. Returns `true` if successful, `false` otherwise.

virtual memory_size_type	total_memory_in_bytes () const =0
	Returns the total size in bytes of the memory occupied by `*this`.

virtual memory_size_type	external_memory_in_bytes () const =0
	Returns the size in bytes of the memory managed by `*this`.

Protected Types
typedef std::vector< Constraint >	Constraint_Sequence
	A type alias for a sequence of constraints.

Protected Member Functions
	PIP_Tree_Node (const PIP_Problem *owner)
	Constructor: builds a node owned by `*owner`.

	PIP_Tree_Node (const PIP_Tree_Node &y)
	Copy constructor.

const PIP_Problem *	get_owner () const
	Returns a pointer to the PIP_Problem owning object.

virtual void	set_owner (const PIP_Problem *owner)=0
	Sets the pointer to the PIP_Problem owning object.

virtual bool	check_ownership (const PIP_Problem *owner) const =0
	Returns `true` if and only if all the nodes in the subtree rooted in `this` are owned by `owner`.

const PIP_Decision_Node *	parent () const
	Returns a pointer to this node's parent.

void	set_parent (const PIP_Decision_Node *p)
	Set this node's parent to `*p`.

virtual void	update_tableau (const PIP_Problem &pip, dimension_type external_space_dim, dimension_type first_pending_constraint, const Constraint_Sequence &input_cs, const Variables_Set &parameters)=0
	Populates the parametric simplex tableau using external data. More...

virtual PIP_Tree_Node *	solve (const PIP_Problem &pip, bool check_feasible_context, const Matrix< Row > &context, const Variables_Set &params, dimension_type space_dim, int indent_level)=0
	Executes a parametric simplex on the tableau, under specified context. More...

void	add_constraint (const Row &row, const Variables_Set &parameters)
	Inserts a new parametric constraint in internal row format.

void	parent_merge ()
	Merges parent's artificial parameters into `*this`.

virtual void	print_tree (std::ostream &s, int indent, const std::vector< bool > &pip_dim_is_param, dimension_type first_art_dim) const =0
	Prints on `s` the tree rooted in `*this`. More...

Static Protected Member Functions
static void	indent_and_print (std::ostream &s, int indent, const char *str)
	A helper function used when printing PIP trees.

static bool	compatibility_check (Matrix< Row > &s)
	Checks whether a context matrix is satisfiable. More...

static bool	compatibility_check (const Matrix< Row > &context, const Row &row)
	Helper method: checks for satisfiability of the restricted context obtained by adding `row` to `context`.

Protected Attributes
const PIP_Problem *	owner_
	A pointer to the PIP_Problem object owning this node.

const PIP_Decision_Node *	parent_
	A pointer to the parent of `this`, null if `this` is the root.

Constraint_System	constraints_
	The local system of parameter constraints.

Artificial_Parameter_Sequence	artificial_parameters
	The local sequence of expressions for local artificial parameters.

Related Functions
(Note that these are not member functions.)
std::ostream &	operator<< (std::ostream &os, const PIP_Tree_Node &x)
	Output operator: prints the solution tree rooted in `x`. More...

Detailed Description

A node of the PIP solution tree.

This is the base class for the nodes of the binary trees representing the solutions of PIP problems. From this one, two classes are derived:

PIP_Decision_Node, for the internal nodes of the tree;
PIP_Solution_Node, for the leaves of the tree.

Member Function Documentation

const Constraint_System & Parma_Polyhedra_Library::PIP_Tree_Node::constraints ( ) const

inline

Returns the system of parameter constraints controlling *this.

The indices in the constraints are the same as the original variables and parameters. Coefficients in indices corresponding to variables always are zero.

void Parma_Polyhedra_Library::PIP_Tree_Node::print	(	std::ostream &	s,
		int	indent = `0`
	)		const

Prints on s the tree rooted in *this.

Parameters

s	The output stream.
indent	The amount of indentation.

virtual void Parma_Polyhedra_Library::PIP_Tree_Node::update_tableau	(	const PIP_Problem &	pip,
		dimension_type	external_space_dim,
		dimension_type	first_pending_constraint,
		const Constraint_Sequence &	input_cs,
		const Variables_Set &	parameters
	)

protectedpure virtual

Populates the parametric simplex tableau using external data.

Parameters

pip	The PIP_Problem object containing this node.
external_space_dim	The number of all problem variables and problem parameters (excluding artificial parameters).
first_pending_constraint	The first element in `input_cs` to be added to the tableau, which already contains the previous elements.
input_cs	All the constraints of the PIP problem.
parameters	The set of indices of the problem parameters.

Implemented in Parma_Polyhedra_Library::PIP_Decision_Node, and Parma_Polyhedra_Library::PIP_Solution_Node.

virtual PIP_Tree_Node* Parma_Polyhedra_Library::PIP_Tree_Node::solve	(	const PIP_Problem &	pip,
		bool	check_feasible_context,
		const Matrix< Row > &	context,
		const Variables_Set &	params,
		dimension_type	space_dim,
		int	indent_level
	)

protectedpure virtual

Executes a parametric simplex on the tableau, under specified context.

Returns: The root of the PIP tree solution, or 0 if unfeasible.

Parameters

pip	The PIP_Problem object containing this node.
check_feasible_context	Whether the resolution process should (re-)check feasibility of context (since the initial context may have been modified).
context	The context, being a set of constraints on the parameters.
params	The local parameter set, including parent's artificial parameters.
space_dim	The space dimension of parent, including artificial parameters.
indent_level	The indentation level (for debugging output only).

Implemented in Parma_Polyhedra_Library::PIP_Decision_Node, and Parma_Polyhedra_Library::PIP_Solution_Node.

virtual void Parma_Polyhedra_Library::PIP_Tree_Node::print_tree	(	std::ostream &	s,
		int	indent,
		const std::vector< bool > &	pip_dim_is_param,
		dimension_type	first_art_dim
	)		const

protectedpure virtual

Prints on s the tree rooted in *this.

Parameters

s	The output stream.
indent	The amount of indentation.
pip_dim_is_param	A vector of Boolean flags telling which PIP problem dimensions are problem parameters. The size of the vector is equal to the PIP problem internal space dimension (i.e., no artificial parameters).
first_art_dim	The first space dimension corresponding to an artificial parameter that was created in this node (if any).

Implemented in Parma_Polyhedra_Library::PIP_Decision_Node, and Parma_Polyhedra_Library::PIP_Solution_Node.

static bool Parma_Polyhedra_Library::PIP_Tree_Node::compatibility_check ( Matrix< Row > & s )

staticprotected

Checks whether a context matrix is satisfiable.

The satisfiability check is implemented by the revised dual simplex algorithm on the context matrix. The algorithm ensures the feasible solution is integer by applying a cut generation method when intermediate non-integer solutions are found.

Friends And Related Function Documentation

std::ostream & operator<<	(	std::ostream &	os,
		const PIP_Tree_Node &	x
	)

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

ppl.hh

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Related Functions

Detailed Description

Member Function Documentation

Friends And Related Function Documentation