Classes | Public Types | Public Member Functions | Protected Types | Protected Member Functions | Static Protected Member Functions | Protected Attributes | Related Functions

Parma_Polyhedra_Library::PIP_Tree_Node Class Reference

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

#include <ppl.hh>

Inherited by Parma_Polyhedra_Library::PIP_Decision_Node, and Parma_Polyhedra_Library::PIP_Solution_Node.

List of all members.

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_Nodeclone () const =0
 Returns a pointer to a dynamically-allocated copy of *this.
virtual ~PIP_Tree_Node ()
 Destructor.
virtual bool OK () const
 Returns true if and only if *this is well formed.
virtual const PIP_Solution_Nodeas_solution () const
 Returns this if *this is a solution node, 0 otherwise.
virtual const PIP_Decision_Nodeas_decision () const
 Returns this if *this is a decision node, 0 otherwise.
const Constraint_Systemconstraints () const
 Returns the system of parameter constraints controlling *this.
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, unsigned indent=0) const
 Prints on s the tree rooted in *this.
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< ConstraintConstraint_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_Problemget_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 is owned by *pip.
const PIP_Decision_Nodeparent () 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.
virtual PIP_Tree_Nodesolve (const PIP_Problem &pip, bool check_feasible_context, const Matrix &context, const Variables_Set &params, dimension_type space_dim)=0
 Executes a parametric simplex on the tableau, under specified context.
void add_constraint (const Row &x, 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, unsigned indent, const std::vector< bool > &pip_dim_is_param, dimension_type first_art_dim) const
 Prints on s the tree rooted in *this.

Static Protected Member Functions

static void indent_and_print (std::ostream &s, unsigned indent, const char *str)
 A helper function used when printing PIP trees.
static bool compatibility_check (Matrix &s)
 Checks whether a context matrix is satisfiable.
static bool compatibility_check (const Matrix &context, const Row &row)
 Helper method: checks for satisfiability of the restricted context obtained by adding row to context.

Protected Attributes

const PIP_Problemowner_
 A pointer to the PIP_Problem object owning this node.
const PIP_Decision_Nodeparent_
 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.

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:


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,
unsigned  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 
) [protected, pure 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_Solution_Node, and Parma_Polyhedra_Library::PIP_Decision_Node.

virtual PIP_Tree_Node* Parma_Polyhedra_Library::PIP_Tree_Node::solve ( const PIP_Problem pip,
bool  check_feasible_context,
const Matrix &  context,
const Variables_Set params,
dimension_type  space_dim 
) [protected, pure 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.

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

virtual void Parma_Polyhedra_Library::PIP_Tree_Node::print_tree ( std::ostream &  s,
unsigned  indent,
const std::vector< bool > &  pip_dim_is_param,
dimension_type  first_art_dim 
) const [protected, 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).

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

static bool Parma_Polyhedra_Library::PIP_Tree_Node::compatibility_check ( Matrix &  s  )  [static, protected]

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 
) [related]

Output operator: prints the solution tree rooted in x.


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