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

#include <PIP_Tree.defs.hh>

Inheritance diagram for Parma_Polyhedra_Library::PIP_Tree_Node:

Collaboration 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`.
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`.
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` is owned by `pip`.
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.
virtual PIP_Tree_Node *	solve (const PIP_Problem &pip, bool check_feasible_context, const Matrix &context, const Variables_Set &params, dimension_type space_dim, int indent_level)=0
	Executes a parametric simplex on the tableau, under specified context.
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`.
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 &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_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.
Friends
class	PIP_Problem
class	PIP_Decision_Node
class	PIP_Solution_Node
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:

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

Definition at line 49 of file PIP_Tree.defs.hh.

Member Typedef Documentation

typedef std::vector<Artificial_Parameter> Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter_Sequence

A type alias for a sequence of Artificial_Parameter's.

Definition at line 94 of file PIP_Tree.defs.hh.

typedef std::vector<Constraint> Parma_Polyhedra_Library::PIP_Tree_Node::Constraint_Sequence

protected

A type alias for a sequence of constraints.

Definition at line 135 of file PIP_Tree.defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::PIP_Tree_Node::PIP_Tree_Node ( const PIP_Problem * owner )

explicitprotected

Constructor: builds a node owned by *owner.

Definition at line 859 of file PIP_Tree.cc.

  : owner_(owner),
    parent_(0),
    constraints_(),
    artificial_parameters() {
}

Parma_Polyhedra_Library::PIP_Tree_Node::PIP_Tree_Node ( const PIP_Tree_Node & y )

protected

Copy constructor.

Definition at line 866 of file PIP_Tree.cc.

  : owner_(y.owner_),
    parent_(0), // NOTE: parent is not copied.
    constraints_(y.constraints_),
    artificial_parameters(y.artificial_parameters) {
}

Parma_Polyhedra_Library::PIP_Tree_Node::~PIP_Tree_Node ( )

inlinevirtual

Destructor.

Definition at line 56 of file PIP_Tree.inlines.hh.

{
}

Member Function Documentation

void Parma_Polyhedra_Library::PIP_Tree_Node::add_constraint	(	const Row &	row,
		const Variables_Set &	parameters
	)

protected

Inserts a new parametric constraint in internal row format.

Definition at line 1166 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::add_mul_assign(), Parma_Polyhedra_Library::Sparse_Row::begin(), constraints_, Parma_Polyhedra_Library::Sparse_Row::end(), Parma_Polyhedra_Library::Sparse_Row::get(), Parma_Polyhedra_Library::CO_Tree::const_iterator::index(), Parma_Polyhedra_Library::Constraint_System::insert(), PPL_ASSERT, WEIGHT_ADD, and WEIGHT_BEGIN.

Referenced by Parma_Polyhedra_Library::PIP_Solution_Node::solve().

                                                                {
  // Compute the expression for the parameter constraint.
  Linear_Expression expr = Linear_Expression(row.get(0));
  Variables_Set::const_iterator j = parameters.begin();
  if (!parameters.empty()) {
    // Needed to avoid reallocations in expr when iterating upward.
    add_mul_assign(expr, 0, Variable(*(parameters.rbegin())));
    // The number of increments of j plus one.
    dimension_type j_index = 1;
    Row::const_iterator i = row.begin();
    Row::const_iterator i_end = row.end();
    if (i != i_end && i.index() == 0)
      ++i;
    // NOTE: iterating in [1..num_params].
    WEIGHT_BEGIN();
    for ( ; i != i_end; ++i) {
      PPL_ASSERT(i.index() <= parameters.size());
      std::advance(j, i.index() - j_index);
      j_index = i.index();
      WEIGHT_ADD(74);
      add_mul_assign(expr, *i, Variable(*j));
    }
  }
  // Add the parameter constraint.
  constraints_.insert(expr >= 0);
}

PIP_Tree_Node::Artificial_Parameter_Sequence::const_iterator Parma_Polyhedra_Library::PIP_Tree_Node::art_parameter_begin ( ) const

inline

Returns a const_iterator to the beginning of local artificial parameters.

Definition at line 80 of file PIP_Tree.inlines.hh.

References artificial_parameters.

Referenced by external_memory_in_bytes(), parent_merge(), and print_tree().

                                         {
  return artificial_parameters.begin();
}

dimension_type Parma_Polyhedra_Library::PIP_Tree_Node::art_parameter_count ( ) const

inline

Returns the number of local artificial parameters.

Definition at line 90 of file PIP_Tree.inlines.hh.

References artificial_parameters.

Referenced by Parma_Polyhedra_Library::PIP_Decision_Node::print_tree().

                                         {
  return artificial_parameters.size();
}

PIP_Tree_Node::Artificial_Parameter_Sequence::const_iterator Parma_Polyhedra_Library::PIP_Tree_Node::art_parameter_end ( ) const

inline

Returns a const_iterator to the end of local artificial parameters.

Definition at line 85 of file PIP_Tree.inlines.hh.

References artificial_parameters.

Referenced by external_memory_in_bytes(), parent_merge(), and print_tree().

                                       {
  return artificial_parameters.end();
}

virtual const PIP_Decision_Node* Parma_Polyhedra_Library::PIP_Tree_Node::as_decision ( ) const

pure virtual

Returns this if *this is a decision node, 0 otherwise.

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

virtual const PIP_Solution_Node* Parma_Polyhedra_Library::PIP_Tree_Node::as_solution ( ) const

pure virtual

Returns this if *this is a solution node, 0 otherwise.

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

void Parma_Polyhedra_Library::PIP_Tree_Node::ascii_dump ( std::ostream & s ) const

Dumps to s an ASCII representation of *this.

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

Definition at line 1737 of file PIP_Tree.cc.

References artificial_parameters, Parma_Polyhedra_Library::Constraint_System::ascii_dump(), Parma_Polyhedra_Library::PIP_Solution_Node::ascii_dump(), and constraints_.

Referenced by Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter::ascii_dump().

                                             {
  s << "constraints_\n";
  constraints_.ascii_dump(s);
  dimension_type artificial_parameters_size = artificial_parameters.size();
  s << "\nartificial_parameters( " << artificial_parameters_size << " )\n";
  for (dimension_type i = 0; i < artificial_parameters_size; ++i)
    artificial_parameters[i].ascii_dump(s);
}

bool Parma_Polyhedra_Library::PIP_Tree_Node::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.

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

Definition at line 1747 of file PIP_Tree.cc.

References artificial_parameters, Parma_Polyhedra_Library::Constraint_System::ascii_load(), Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter::ascii_load(), and constraints_.

Referenced by Parma_Polyhedra_Library::PIP_Solution_Node::ascii_load(), and Parma_Polyhedra_Library::PIP_Decision_Node::ascii_load().

                                       {
  std::string str;
  if (!(s >> str) || str != "constraints_")
    return false;
  constraints_.ascii_load(s);

  if (!(s >> str) || str != "artificial_parameters(")
    return false;
  dimension_type artificial_parameters_size;
  if (!(s >> artificial_parameters_size))
    return false;
  if (!(s >> str) || str != ")")
    return false;
  Artificial_Parameter ap;
  for (dimension_type i = 0; i < artificial_parameters_size; ++i) {
    if (!ap.ascii_load(s))
      return false;
    artificial_parameters.push_back(ap);
  }

  // Note: do not assert OK() here.
  // The node invariants should be checked on derived nodes.
  return true;
}

virtual bool Parma_Polyhedra_Library::PIP_Tree_Node::check_ownership ( const PIP_Problem * owner ) const

protectedpure virtual

Returns true if and only if all the nodes in the subtree rooted in *this is owned by *pip.

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

Referenced by Parma_Polyhedra_Library::PIP_Decision_Node::check_ownership().

virtual PIP_Tree_Node* Parma_Polyhedra_Library::PIP_Tree_Node::clone ( ) const

pure virtual

Returns a pointer to a dynamically-allocated copy of *this.

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

Referenced by Parma_Polyhedra_Library::PIP_Decision_Node::PIP_Decision_Node(), and Parma_Polyhedra_Library::PIP_Problem::PIP_Problem().

bool Parma_Polyhedra_Library::PIP_Tree_Node::compatibility_check ( Matrix & 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.

Definition at line 2051 of file PIP_Tree.cc.

Referenced by compatibility_check(), Parma_Polyhedra_Library::PIP_Problem::solve(), Parma_Polyhedra_Library::PIP_Solution_Node::solve(), and Parma_Polyhedra_Library::PIP_Decision_Node::solve().

                                            {
  PPL_ASSERT(s.OK());
  // Note: num_rows may increase.
  dimension_type num_rows = s.num_rows();
  const dimension_type num_columns = s.num_columns();
  const dimension_type num_vars = num_columns - 1;

  std::vector<Coefficient> scaling(num_rows, 1);
  std::vector<bool> basis;
  basis.reserve(num_vars + num_rows);
  std::vector<dimension_type> mapping;
  mapping.reserve(num_vars + num_rows);
  std::vector<dimension_type> var_row;
  var_row.reserve(num_rows);
  std::vector<dimension_type> var_column;
  var_column.reserve(num_columns);

  // Column 0 is the constant term, not a variable
  var_column.push_back(not_a_dimension());
  for (dimension_type j = 1; j <= num_vars; ++j) {
    basis.push_back(true);
    mapping.push_back(j);
    var_column.push_back(j - 1);
  }
  for (dimension_type i = 0; i < num_rows; ++i) {
    basis.push_back(false);
    mapping.push_back(i);
    var_row.push_back(i + num_vars);
  }

  // Scaling factor (i.e., denominator) for pivot coefficients.
  PPL_DIRTY_TEMP_COEFFICIENT(pivot_denom);
  // Allocate once and for all: short life temporaries.
  PPL_DIRTY_TEMP_COEFFICIENT(product);
  PPL_DIRTY_TEMP_COEFFICIENT(gcd);
  PPL_DIRTY_TEMP_COEFFICIENT(scale_factor);

  // Perform simplex pivots on the context
  // until we find an empty solution or an optimum.
  while (true) {
    // Check if the client has requested abandoning all expensive
    // computations. If so, the exception specified by the client
    // is thrown now.
    maybe_abandon();

    // pi is the pivot's row index.
    dimension_type pi = num_rows;
    // pj is the pivot's column index.
    dimension_type pj = 0;

    bool found_positive_pivot_candidate
      = compatibility_check_find_pivot(s, mapping, basis, pi, pj);

    if (!found_positive_pivot_candidate)
      return false;

    if (pj == 0) {
      // No negative RHS: fractional optimum found.
      // If it is integer, then the test is successful.
      // Otherwise, generate a new cut.
      bool all_integer_vars = true;
      // NOTE: iterating downwards would be correct, but it would change
      // the ordering of cut generation.
      WEIGHT_BEGIN();
      for (dimension_type i = 0; i < num_vars; ++i) {
        if (basis[i])
          // Basic variable = 0, hence integer.
          continue;
        // Not a basic variable.
        WEIGHT_ADD(70);
        const dimension_type mi = mapping[i];
        Coefficient_traits::const_reference denom = scaling[mi];
        if (s[mi].get(0) % denom == 0)
          continue;
        // Here constant term is not integer.
        all_integer_vars = false;
        // Generate a new cut.
        var_row.push_back(mapping.size());
        basis.push_back(false);
        mapping.push_back(num_rows);
        s.add_zero_rows(1, Row_Flags());
        Row& cut = s[num_rows];
        ++num_rows;
        const Row& s_mi = s[mi];
        cut = s_mi;
        for (Row::iterator
               j = cut.begin(), j_end = cut.end(); j != j_end; ++j) {
          WEIGHT_ADD(32);
          pos_rem_assign(*j, *j, denom);
        }
        cut[0] -= denom;
        scaling.push_back(denom);
      }
      // Check if an integer solution was found.
      if (all_integer_vars)
        return true;
      else
        continue;
    }

    // Here we have a positive s[pi][pj] pivot.

    // Normalize the tableau before pivoting.
    for (dimension_type i = num_rows; i-- > 0; )
      row_normalize(s[i], scaling[i]);

    // Update basis.
    {
      const dimension_type var_pi = var_row[pi];
      const dimension_type var_pj = var_column[pj];
      var_row[pi] = var_pj;
      var_column[pj] = var_pi;
      basis[var_pi] = true;
      basis[var_pj] = false;
      mapping[var_pi] = pj;
      mapping[var_pj] = pi;
    }

    // Create an identity row corresponding to basic variable pj.
    s.add_zero_rows(1, Row_Flags());
    Row& pivot = s[num_rows];
    pivot[pj] = 1;

    // Swap identity row with the pivot row previously found.
    using std::swap;
    swap(pivot, s[pi]);
    // Save original pivot scaling factor in a temporary,
    // then reset scaling factor for identity row.
    pivot_denom = scaling[pi];
    scaling[pi] = 1;

    // Perform a pivot operation on the matrix.
    Coefficient_traits::const_reference pivot_pj = pivot.get(pj);
    {
      for (Row::const_iterator
             j = pivot.begin(), j_end = pivot.end(); j != j_end; ++j) {
        if (j.index() == pj)
          continue;
        Coefficient_traits::const_reference pivot_j = *j;
        // Do nothing if the j-th pivot element is zero.
        if (pivot_j == 0)
          continue;
        WEIGHT_BEGIN();
        for (dimension_type i = num_rows; i-- > 0; ) {
          Row& s_i = s[i];
          product = s_i.get(pj) * pivot_j;
          if (product % pivot_pj != 0) {
            WEIGHT_ADD(103);
            // Must scale row s_i to stay in integer case.
            gcd_assign(gcd, product, pivot_pj);
            exact_div_assign(scale_factor, pivot_pj, gcd);
            for (Row::iterator
                   k = s_i.begin(), k_end = s_i.end(); k != k_end; ++k) {
              WEIGHT_ADD(30);
              *k *= scale_factor;
            }
            product *= scale_factor;
            scaling[i] *= scale_factor;
          }
          PPL_ASSERT(product % pivot_pj == 0);
          exact_div_assign(product, product, pivot_pj);
          s_i[j.index()] -= product;
          WEIGHT_ADD(134);
        }
      }
    }
    // Update column only if pivot coordinate != 1.
    if (pivot_pj != pivot_denom) {
      WEIGHT_BEGIN();
      for (dimension_type i = num_rows; i-- > 0; ) {
        Row& s_i = s[i];
        Coefficient& s_i_pj = s_i[pj];
        product = s_i_pj * pivot_denom;
        if (product % pivot_pj != 0) {
          WEIGHT_ADD(98);
          // As above, perform row scaling.
          gcd_assign(gcd, product, pivot_pj);
          exact_div_assign(scale_factor, pivot_pj, gcd);
          for (Row::iterator
                 k = s_i.begin(), k_end = s_i.end(); k != k_end; ++k) {
            WEIGHT_ADD(26);
            *k *= scale_factor;
          }
          product *= scale_factor;
          scaling[i] *= scale_factor;
        }
        PPL_ASSERT(product % pivot_pj == 0);
        exact_div_assign(s_i_pj, product, pivot_pj);
        WEIGHT_ADD(97);
      }
    }
    // Drop pivot to restore proper matrix size.
    s.remove_trailing_rows(1);
  }

  // This point should be unreachable.
  PPL_UNREACHABLE;
  return false;
}

bool Parma_Polyhedra_Library::PIP_Tree_Node::compatibility_check	(	const Matrix &	context,
		const Row &	row
	)

staticprotected

Helper method: checks for satisfiability of the restricted context obtained by adding row to context.

Definition at line 2043 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::Sparse_Matrix::add_row(), and compatibility_check().

                                                                        {
  // CHECKME: do `context' and `row' have compatible (row) capacity?
  Matrix s(context);
  s.add_row(row);
  return compatibility_check(s);
}

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.

Definition at line 75 of file PIP_Tree.inlines.hh.

References constraints_.

                                 {
  return constraints_;
}

memory_size_type Parma_Polyhedra_Library::PIP_Tree_Node::external_memory_in_bytes ( ) const

pure virtual

Returns the size in bytes of the memory managed by *this.

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

Definition at line 3526 of file PIP_Tree.cc.

References art_parameter_begin(), art_parameter_end(), artificial_parameters, constraints_, and Parma_Polyhedra_Library::Constraint_System::external_memory_in_bytes().

                                              {
  memory_size_type n = constraints_.external_memory_in_bytes();
  // Adding the external memory for `artificial_parameters'.
  n += artificial_parameters.capacity() * sizeof(Artificial_Parameter);
  for (Artificial_Parameter_Sequence::const_iterator
         ap = art_parameter_begin(),
         ap_end = art_parameter_end(); ap != ap_end; ++ap)
    n += (ap->external_memory_in_bytes());

  return n;
}

const PIP_Problem * Parma_Polyhedra_Library::PIP_Tree_Node::get_owner ( ) const

inlineprotected

Returns a pointer to the PIP_Problem owning object.

Definition at line 70 of file PIP_Tree.inlines.hh.

References owner_.

Referenced by Parma_Polyhedra_Library::PIP_Solution_Node::check_ownership(), Parma_Polyhedra_Library::PIP_Decision_Node::check_ownership(), Parma_Polyhedra_Library::PIP_Solution_Node::parametric_values(), print(), Parma_Polyhedra_Library::PIP_Solution_Node::solve(), and Parma_Polyhedra_Library::PIP_Solution_Node::update_solution().

                               {
  return owner_;
}

void Parma_Polyhedra_Library::PIP_Tree_Node::indent_and_print	(	std::ostream &	s,
		int	indent,
		const char *	str
	)

staticprotected

A helper function used when printing PIP trees.

Definition at line 3584 of file PIP_Tree.cc.

References PPL_ASSERT.

Referenced by Parma_Polyhedra_Library::PIP_Problem::print_solution(), print_tree(), Parma_Polyhedra_Library::PIP_Solution_Node::print_tree(), Parma_Polyhedra_Library::PIP_Decision_Node::print_tree(), Parma_Polyhedra_Library::PIP_Solution_Node::solve(), and Parma_Polyhedra_Library::PIP_Decision_Node::solve().

                                                 {
  PPL_ASSERT(indent >= 0);
  s << std::setw(2 * indent) << "" << str;
}

bool Parma_Polyhedra_Library::PIP_Tree_Node::OK ( ) const

pure virtual

Returns true if and only if *this is well formed.

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

Definition at line 1142 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Solution_Node::ascii_dump(), Parma_Polyhedra_Library::Constraint_System::begin(), constraints_, and Parma_Polyhedra_Library::Constraint_System::end().

Referenced by Parma_Polyhedra_Library::PIP_Tree_Node::Artificial_Parameter::ascii_load(), Parma_Polyhedra_Library::PIP_Solution_Node::OK(), Parma_Polyhedra_Library::PIP_Decision_Node::OK(), and Parma_Polyhedra_Library::PIP_Decision_Node::solve().

                        {
#ifndef NDEBUG
  using std::endl;
  using std::cerr;
#endif

  // Parameter constraint system should contain no strict inequalities.
  for (Constraint_System::const_iterator
         i = constraints_.begin(), i_end = constraints_.end(); i != i_end; ++i)
    if (i->is_strict_inequality()) {
#ifndef NDEBUG
      cerr << "The feasible region of the PIP_Problem parameter context"
           << "is defined by a constraint system containing strict "
           << "inequalities."
           << endl;
      ascii_dump(cerr);
#endif
      return false;
    }
  return true;
}

const PIP_Decision_Node * Parma_Polyhedra_Library::PIP_Tree_Node::parent ( ) const

inlineprotected

Returns a pointer to this node's parent.

Definition at line 65 of file PIP_Tree.inlines.hh.

References parent_.

Referenced by Parma_Polyhedra_Library::PIP_Solution_Node::generate_cut(), parent_merge(), print(), Parma_Polyhedra_Library::PIP_Solution_Node::solve(), and Parma_Polyhedra_Library::PIP_Decision_Node::solve().

                            {
  return parent_;
}

void Parma_Polyhedra_Library::PIP_Tree_Node::parent_merge ( )

protected

Merges parent's artificial parameters into *this.

Definition at line 1194 of file PIP_Tree.cc.

References art_parameter_begin(), art_parameter_end(), artificial_parameters, Parma_Polyhedra_Library::PIP_Solution_Node::OK(), parent(), parent_, and PPL_ASSERT.

Referenced by Parma_Polyhedra_Library::PIP_Decision_Node::solve().

                            {
  const PIP_Decision_Node& parent = *parent_;

  // Merge the parent's artificial parameters.
  artificial_parameters.insert(artificial_parameters.begin(),
                               parent.art_parameter_begin(),
                               parent.art_parameter_end());

  PPL_ASSERT(OK());
}

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.

Definition at line 3592 of file PIP_Tree.cc.

References get_owner(), Parma_Polyhedra_Library::PIP_Problem::parameter_space_dimensions(), parent(), Parma_Polyhedra_Library::PIP_Solution_Node::print_tree(), and Parma_Polyhedra_Library::PIP_Problem::space_dimension().

Referenced by Parma_Polyhedra_Library::IO_Operators::operator<<().

                                                          {
  const dimension_type pip_space_dim = get_owner()->space_dimension();
  const Variables_Set& pip_params = get_owner()->parameter_space_dimensions();

  std::vector<bool> pip_dim_is_param(pip_space_dim);
  for (Variables_Set::const_iterator p = pip_params.begin(),
         p_end = pip_params.end(); p != p_end; ++p)
    pip_dim_is_param[*p] = true;

  dimension_type first_art_dim = pip_space_dim;
  for (const PIP_Tree_Node* node = parent(); node != 0; node = node->parent())
    first_art_dim += node->art_parameter_count();

  print_tree(s, indent, pip_dim_is_param, first_art_dim);
}

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.

Definition at line 3609 of file PIP_Tree.cc.

References art_parameter_begin(), art_parameter_end(), Parma_Polyhedra_Library::Constraint_System::begin(), constraints_, Parma_Polyhedra_Library::Constraint_System::empty(), Parma_Polyhedra_Library::Constraint_System::end(), indent_and_print(), and PPL_ASSERT.

                                                              {
  using namespace IO_Operators;

  // Print artificial parameters.
  for (Artificial_Parameter_Sequence::const_iterator
         api = art_parameter_begin(),
         api_end = art_parameter_end(); api != api_end; ++api) {
    indent_and_print(s, indent, "Parameter ");
    s << Variable(first_art_dim) << " = " << *api << "\n";
    ++first_art_dim;
  }

  // Print constraints, if any.
  if (!constraints_.empty()) {
    indent_and_print(s, indent, "if ");

    Constraint_System::const_iterator ci = constraints_.begin();
    Constraint_System::const_iterator ci_end = constraints_.end();
    PPL_ASSERT(ci != ci_end);
    s << *ci;
    for (++ci; ci != ci_end; ++ci)
      s << " and " << *ci;

    s << " then\n";
  }
}

virtual void Parma_Polyhedra_Library::PIP_Tree_Node::set_owner ( const PIP_Problem * owner )

protectedpure virtual

Sets the pointer to the PIP_Problem owning object.

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

Referenced by Parma_Polyhedra_Library::PIP_Problem::PIP_Problem(), and Parma_Polyhedra_Library::PIP_Decision_Node::set_owner().

void Parma_Polyhedra_Library::PIP_Tree_Node::set_parent ( const PIP_Decision_Node * p )

inlineprotected

Set this node's parent to *p.

Definition at line 60 of file PIP_Tree.inlines.hh.

References parent_.

Referenced by Parma_Polyhedra_Library::PIP_Decision_Node::PIP_Decision_Node(), and Parma_Polyhedra_Library::PIP_Decision_Node::solve().

                                                    {
  parent_ = p;
}

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,
		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.

Referenced by Parma_Polyhedra_Library::PIP_Problem::solve(), and Parma_Polyhedra_Library::PIP_Solution_Node::solve().

virtual memory_size_type Parma_Polyhedra_Library::PIP_Tree_Node::total_memory_in_bytes ( ) const

pure virtual

Returns the total size in bytes of the memory occupied by *this.

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

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.

Referenced by Parma_Polyhedra_Library::PIP_Problem::solve().

Friends And Related Function Documentation

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

Definition at line 845 of file PIP_Tree.cc.

                                                   {
  x.print(os);
  return os;
}

friend class PIP_Decision_Node

friend

Definition at line 140 of file PIP_Tree.defs.hh.

Referenced by Parma_Polyhedra_Library::PIP_Decision_Node::ascii_load(), Parma_Polyhedra_Library::PIP_Decision_Node::clone(), and Parma_Polyhedra_Library::PIP_Solution_Node::solve().

friend class PIP_Problem

friend

Definition at line 139 of file PIP_Tree.defs.hh.

friend class PIP_Solution_Node

friend

Reimplemented in Parma_Polyhedra_Library::PIP_Decision_Node.

Definition at line 141 of file PIP_Tree.defs.hh.

Member Data Documentation

Artificial_Parameter_Sequence Parma_Polyhedra_Library::PIP_Tree_Node::artificial_parameters

protected

The local sequence of expressions for local artificial parameters.

Definition at line 153 of file PIP_Tree.defs.hh.

Referenced by art_parameter_begin(), art_parameter_count(), art_parameter_end(), ascii_dump(), ascii_load(), external_memory_in_bytes(), Parma_Polyhedra_Library::PIP_Solution_Node::generate_cut(), parent_merge(), Parma_Polyhedra_Library::PIP_Solution_Node::solve(), and Parma_Polyhedra_Library::PIP_Decision_Node::solve().

Constraint_System Parma_Polyhedra_Library::PIP_Tree_Node::constraints_

protected

The local system of parameter constraints.

Definition at line 150 of file PIP_Tree.defs.hh.

Referenced by add_constraint(), ascii_dump(), ascii_load(), constraints(), external_memory_in_bytes(), OK(), Parma_Polyhedra_Library::PIP_Decision_Node::OK(), print_tree(), Parma_Polyhedra_Library::PIP_Solution_Node::print_tree(), Parma_Polyhedra_Library::PIP_Solution_Node::solve(), and Parma_Polyhedra_Library::PIP_Decision_Node::solve().

const PIP_Problem* Parma_Polyhedra_Library::PIP_Tree_Node::owner_

protected

A pointer to the PIP_Problem object owning this node.

Definition at line 144 of file PIP_Tree.defs.hh.

Referenced by get_owner(), Parma_Polyhedra_Library::PIP_Solution_Node::set_owner(), and Parma_Polyhedra_Library::PIP_Decision_Node::set_owner().

const PIP_Decision_Node* Parma_Polyhedra_Library::PIP_Tree_Node::parent_

protected

A pointer to the parent of *this, null if *this is the root.

Definition at line 147 of file PIP_Tree.defs.hh.

Referenced by parent(), parent_merge(), and set_parent().

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

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Friends

Related Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation