The type for parametric simplex tableau. More...

Public Member Functions
	Tableau ()
	Default constructor. More...

	Tableau (const Tableau &y)
	Copy constructor. More...

	~Tableau ()
	Destructor. More...

bool	is_integer () const
	Tests whether the matrix is integer, i.e., the denominator is 1. More...

void	scale (Coefficient_traits::const_reference ratio)
	Multiplies all coefficients and denominator with ratio. More...

void	normalize ()
	Normalizes the modulo of coefficients so that they are mutually prime. More...

bool	is_better_pivot (const std::vector< dimension_type > &mapping, const std::vector< bool > &basis, const dimension_type row_0, const dimension_type col_0, const dimension_type row_1, const dimension_type col_1) const
	Compares two pivot row and column pairs before pivoting. More...

Coefficient_traits::const_reference	denominator () const
	Returns the value of the denominator. More...

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

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

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

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

Public Attributes
Matrix< Row >	s
	The matrix of simplex coefficients. More...

Matrix< Row >	t
	The matrix of parameter coefficients. More...

Coefficient	denom
	A common denominator for all matrix elements. More...

Detailed Description

The type for parametric simplex tableau.

Definition at line 413 of file PIP_Tree_defs.hh.

Constructor & Destructor Documentation

Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::Tableau ( )

inline

Default constructor.

Definition at line 30 of file PIP_Tree_inlines.hh.

References OK().

   : s(), t(), denom(1) {
   PPL_ASSERT(OK());
 }

Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::Tableau ( const Tableau & y )

inline

Copy constructor.

Definition at line 36 of file PIP_Tree_inlines.hh.

References OK().

   : s(y.s), t(y.t), denom(y.denom) {
   PPL_ASSERT(OK());
 }

Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::~Tableau ( )

inline

Destructor.

Definition at line 42 of file PIP_Tree_inlines.hh.

42 {

43 }

Member Function Documentation

void Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::ascii_dump ( std::ostream & os ) const

Dumps to os an ASCII representation of *this.

Definition at line 1873 of file PIP_Tree.cc.

                                                          {
   os << "denominator " << denom << "\n";
   os << "variables ";
   s.ascii_dump(os);
   os << "parameters ";
   t.ascii_dump(os);
 }

bool Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::ascii_load ( std::istream & is )

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

Definition at line 1882 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::PIP_Solution_Node::OK().

                                                    {
   std::string str;
   if (!(is >> str) || str != "denominator") {
     return false;
   }
   Coefficient d;
   if (!(is >> d)) {
     return false;
   }
   denom = d;
   if (!(is >> str) || str != "variables") {
     return false;
   }
   if (!s.ascii_load(is)) {
     return false;
   }
   if (!(is >> str) || str != "parameters") {
     return false;
   }
   if (!t.ascii_load(is)) {
     return false;
   }
   PPL_ASSERT(OK());
   return true;
 }

Coefficient_traits::const_reference Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::denominator ( ) const

inline

Returns the value of the denominator.

Definition at line 51 of file PIP_Tree_inlines.hh.

                                             {
   return denom;
 }

memory_size_type Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::external_memory_in_bytes ( ) const

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

Note: No need for a total_memory_in_bytes() method, since class Tableau is a private inner class of PIP_Solution_Node.

Definition at line 3771 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::external_memory_in_bytes().

                                                          {
   return Parma_Polyhedra_Library::external_memory_in_bytes(denom)
     + s.external_memory_in_bytes()
     + t.external_memory_in_bytes();
 }

bool Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::is_better_pivot	(	const std::vector< dimension_type > &	mapping,
		const std::vector< bool > &	basis,
		const dimension_type	row_0,
		const dimension_type	col_0,
		const dimension_type	row_1,
		const dimension_type	col_1
	)		const

Compares two pivot row and column pairs before pivoting.

The algorithm searches the first (ie, leftmost) column $k$ in parameter matrix for which the $c=s_{*j}\frac{t_{ik}}{s_{ij}}$ and $c'=s_{*j'}\frac{t_{i'k}}{s_{i'j'}}$ columns are different, where $s_{*j}$ denotes the $j$ ^th column from the $s$ matrix and $s_{*j'}$ is the $j'$ ^th column of $s$ .

$c$ is the computed column that would be subtracted to column $k$ in parameter matrix if pivoting is done using the $(i,j)$ row and column pair. $c'$ is the computed column that would be subtracted to column $k$ in parameter matrix if pivoting is done using the $(i',j')$ row and column pair.

The test is true if the computed $-c$ column is lexicographically bigger than the $-c'$ column. Due to the column ordering in the parameter matrix of the tableau, leftmost search will enforce solution increase with respect to the following priority order:

the constant term
the coefficients for the original parameters
the coefficients for the oldest artificial parameters.

Returns: true if pivot row and column pair is more suitable for pivoting than the pair

Parameters

mapping	The PIP_Solution_Node::mapping vector for the tableau.
basis	The PIP_Solution_Node::basis vector for the tableau.
row_0	The row number for the first pivot row and column pair to be compared.
col_0	The column number for the first pivot row and column pair to be compared.
row_1	The row number for the second pivot row and column pair to be compared.
col_1	The column number for the second pivot row and column pair to be compared.

Definition at line 1733 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::Sparse_Row::begin(), Parma_Polyhedra_Library::Sparse_Row::end(), Parma_Polyhedra_Library::Sparse_Row::get(), Parma_Polyhedra_Library::CO_Tree::const_iterator::index(), PPL_DIRTY_TEMP_COEFFICIENT, WEIGHT_ADD, and WEIGHT_BEGIN.

                                                     {
   const dimension_type num_params = t.num_columns();
   const dimension_type num_rows = s.num_rows();
   const Row& s_0 = s[row_0];
   const Row& s_1 = s[row_1];
   Coefficient_traits::const_reference s_0_0 = s_0.get(col_0);
   Coefficient_traits::const_reference s_1_1 = s_1.get(col_1);
   const Row& t_0 = t[row_0];
   const Row& t_1 = t[row_1];
   PPL_DIRTY_TEMP_COEFFICIENT(product_0);
   PPL_DIRTY_TEMP_COEFFICIENT(product_1);
   WEIGHT_BEGIN();
   // On exit from the loop, if j_mismatch == num_params then
   // no column mismatch was found.
   dimension_type j_mismatch = num_params;
   Row::const_iterator j0 = t_0.end();
   Row::const_iterator j0_end = t_0.end();
   Row::const_iterator j1 = t_1.end();
   Row::const_iterator j1_end = t_1.end();
   for (dimension_type i = 0; i < num_rows; ++i) {
     const Row& s_i = s[i];
     Coefficient_traits::const_reference s_i_col_0 = s_i.get(col_0);
     Coefficient_traits::const_reference s_i_col_1 = s_i.get(col_1);
     j0 = t_0.begin();
     j1 = t_1.begin();
     while (j0 != j0_end && j1 != j1_end) {
       if (j0.index() == j1.index()) {
         WEIGHT_ADD(1361);
         product_0 = (*j0) * s_1_1 * s_i_col_0;
         product_1 = (*j1) * s_0_0 * s_i_col_1;
         if (product_0 != product_1) {
           // Mismatch found: exit from both loops.
           j_mismatch = j0.index();
           goto end_loop;
         }
         ++j0;
         ++j1;
       }
       else
         if (j0.index() < j1.index()) {
           if (*j0 != 0 && s_1_1 != 0 && s_i_col_0 != 0) {
             // Mismatch found: exit from both loops.
             j_mismatch = j0.index();
             goto end_loop;
           }
           ++j0;
         }
         else {
           PPL_ASSERT(j0.index() > j1.index());
           if (*j1 != 0 && s_0_0 != 0 && s_i_col_1 != 0) {
             // Mismatch found: exit from both loops.
             j_mismatch = j1.index();
             goto end_loop;
           }
           ++j1;
         }
     }
     while (j0 != j0_end) {
       if (*j0 != 0 && s_1_1 != 0 && s_i_col_0 != 0) {
         // Mismatch found: exit from both loops.
         j_mismatch = j0.index();
         goto end_loop;
       }
       ++j0;
     }
     while (j1 != j1_end) {
       if (*j1 != 0 && s_0_0 != 0 && s_i_col_1 != 0) {
         // Mismatch found: exit from both loops.
         j_mismatch = j1.index();
         goto end_loop;
       }
     }
   }
 
  end_loop:
   return (j_mismatch != num_params)
     && column_lower(s, mapping, basis, s_0, col_0, s_1, col_1, *j0, *j1);
 }

bool Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::is_integer ( ) const

inline

Tests whether the matrix is integer, i.e., the denominator is 1.

Definition at line 46 of file PIP_Tree_inlines.hh.

                                            {
   return denom == 1;
 }

void Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::normalize ( )

Normalizes the modulo of coefficients so that they are mutually prime.

Computes the Greatest Common Divisor (GCD) among the elements of the matrices and normalizes them and the denominator by the GCD itself.

Definition at line 1654 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::Sparse_Row::begin(), Parma_Polyhedra_Library::Sparse_Row::end(), Parma_Polyhedra_Library::exact_div_assign(), Parma_Polyhedra_Library::gcd_assign(), PPL_DIRTY_TEMP_COEFFICIENT, WEIGHT_ADD, and WEIGHT_BEGIN.

                                     {
   if (denom == 1) {
     return;
   }
 
   const dimension_type num_rows = s.num_rows();
 
   // Compute global gcd.
   PPL_DIRTY_TEMP_COEFFICIENT(gcd);
   gcd = denom;
   for (dimension_type i = num_rows; i-- > 0; ) {
     WEIGHT_BEGIN();
     const Row& s_i = s[i];
     for (Row::const_iterator
            j = s_i.begin(), j_end = s_i.end(); j != j_end; ++j) {
       Coefficient_traits::const_reference s_ij = *j;
       if (s_ij != 0) {
         WEIGHT_ADD(30);
         gcd_assign(gcd, s_ij, gcd);
         if (gcd == 1) {
           return;
         }
       }
     }
     WEIGHT_BEGIN();
     const Row& t_i = t[i];
     for (Row::const_iterator
            j = t_i.begin(), j_end = t_i.end(); j != j_end; ++j) {
       Coefficient_traits::const_reference t_ij = *j;
       if (t_ij != 0) {
         WEIGHT_ADD(14);
         gcd_assign(gcd, t_ij, gcd);
         if (gcd == 1) {
           return;
         }
       }
     }
   }
   PPL_ASSERT(gcd > 1);
   // Normalize all coefficients.
   WEIGHT_BEGIN();
   for (dimension_type i = num_rows; i-- > 0; ) {
     Row& s_i = s[i];
     for (Row::iterator j = s_i.begin(), j_end = s_i.end(); j != j_end; ++j) {
       Coefficient& s_ij = *j;
       WEIGHT_ADD(19);
       exact_div_assign(s_ij, s_ij, gcd);
     }
     Row& t_i = t[i];
     for (Row::iterator j = t_i.begin(), j_end = t_i.end(); j != j_end; ++j) {
       Coefficient& t_ij = *j;
       WEIGHT_ADD(27);
       exact_div_assign(t_ij, t_ij, gcd);
     }
   }
   // Normalize denominator.
   exact_div_assign(denom, denom, gcd);
 }

bool Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::OK ( ) const

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

Definition at line 1168 of file PIP_Tree.cc.

References t.

Referenced by Tableau().

                                    {
   if (s.num_rows() != t.num_rows()) {
 #ifndef NDEBUG
     std::cerr << "PIP_Solution_Node::Tableau matrices "
               << "have a different number of rows.\n";
 #endif
     return false;
   }
 
   if (!s.OK() || !t.OK()) {
 #ifndef NDEBUG
     std::cerr << "A PIP_Solution_Node::Tableau matrix is broken.\n";
 #endif
     return false;
   }
 
   if (denom <= 0) {
 #ifndef NDEBUG
     std::cerr << "PIP_Solution_Node::Tableau with non-positive "
               << "denominator.\n";
 #endif
     return false;
   }
 
   // All tests passed.
   return true;
 }

void Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::scale ( Coefficient_traits::const_reference ratio )

Multiplies all coefficients and denominator with ratio.

Definition at line 1714 of file PIP_Tree.cc.

References Parma_Polyhedra_Library::Sparse_Row::begin(), Parma_Polyhedra_Library::Sparse_Row::end(), WEIGHT_ADD, and WEIGHT_BEGIN.

                                                                        {
   WEIGHT_BEGIN();
   for (dimension_type i = s.num_rows(); i-- > 0; ) {
     Row& s_i = s[i];
     for (Row::iterator j = s_i.begin(), j_end = s_i.end(); j != j_end; ++j) {
       WEIGHT_ADD(19);
       *j *= ratio;
     }
     Row& t_i = t[i];
     for (Row::iterator j = t_i.begin(), j_end = t_i.end(); j != j_end; ++j) {
       WEIGHT_ADD(25);
       *j *= ratio;
     }
   }
   denom *= ratio;
 }

Member Data Documentation

Coefficient Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::denom

A common denominator for all matrix elements.

Definition at line 419 of file PIP_Tree_defs.hh.

Matrix<Row> Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::s

The matrix of simplex coefficients.

Definition at line 415 of file PIP_Tree_defs.hh.

Matrix<Row> Parma_Polyhedra_Library::PIP_Solution_Node::Tableau::t

The matrix of parameter coefficients.

Definition at line 417 of file PIP_Tree_defs.hh.

Referenced by OK().

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

Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation