[PPL-devel] [GIT] ppl/ppl(pip): Improved basis handling with support for slack variables and bijective variable mapping .
François Galea
francois.galea at uvsq.fr
Wed Nov 4 12:26:02 CET 2009
Module: ppl/ppl
Branch: pip
Commit: 3c4cfb2bdf11e8a0c2064b5e4c71513d65625b62
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3c4cfb2bdf11e8a0c2064b5e4c71513d65625b62
Author: François Galea <francois.galea at uvsq.fr>
Date: Wed Nov 4 08:45:20 2009 +0100
Improved basis handling with support for slack variables and bijective variable mapping.
---
src/PIP_Tree.cc | 69 ++++++++++++++++++++++++++++++++++----------------
src/PIP_Tree.defs.hh | 19 +++++++++++++
2 files changed, 66 insertions(+), 22 deletions(-)
diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 4c47ff5..f8cd682 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -200,6 +200,8 @@ PIP_Solution_Node::PIP_Solution_Node()
tableau(),
basis(),
mapping(),
+ var_row(),
+ var_column(),
sign(),
solution(),
solution_valid(false) {
@@ -210,6 +212,8 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x)
tableau(x.tableau),
basis(x.basis),
mapping(x.mapping),
+ var_row(x.var_row),
+ var_column(x.var_column),
sign(x.sign),
solution(x.solution),
solution_valid(x.solution_valid) {
@@ -221,6 +225,8 @@ PIP_Solution_Node::PIP_Solution_Node(const PIP_Solution_Node &x,
tableau(x.tableau),
basis(x.basis),
mapping(x.mapping),
+ var_row(x.var_row),
+ var_column(x.var_column),
sign(x.sign),
solution(x.solution),
solution_valid(x.solution_valid) {
@@ -862,9 +868,27 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim,
if (parameters.count(i) == 1)
tableau.t.add_zero_columns(1);
else {
+ dimension_type column = tableau.s.num_columns();
tableau.s.add_zero_columns(1);
- basis.push_back(true);
- mapping.push_back(tableau.s.num_columns()-1);
+ if (tableau.s.num_rows() == 0) {
+ // No rows have been added yet
+ basis.push_back(true);
+ mapping.push_back(column);
+ } else {
+ /* Need to insert the original variable id before the slack variable
+ id's to respect variable ordering */
+ dimension_type j;
+ basis.insert(basis.begin()+column, true);
+ mapping.insert(mapping.begin()+column, column);
+ // update variable id's of slack variables
+ for (j = var_row.size(); j-- > 0; )
+ if (var_row[j] >= column)
+ ++var_row[j];
+ for (j = var_column.size(); j-- > 0; )
+ if (var_column[j] >= column)
+ ++var_column[j];
+ }
+ var_column.push_back(column);
}
}
internal_space_dim = external_space_dim;
@@ -903,15 +927,25 @@ PIP_Solution_Node::update_tableau(dimension_type external_space_dim,
/* parametric-only constraints have already been inserted in initial
context, so no need to insert them in the tableau
*/
+ dimension_type var_id = mapping.size();
+ dimension_type row_id = tableau.s.num_rows();
tableau.s.add_row(var);
tableau.t.add_row(param);
sign.push_back(row_sign(param));
+ basis.push_back(false);
+ mapping.push_back(row_id);
+ var_row.push_back(var_id);
if (cst->is_equality()) {
+ ++var_id;
+ ++row_id;
negate_assign(var, var, 0);
negate_assign(param, param, 0);
tableau.s.add_row(var);
tableau.t.add_row(param);
sign.push_back(row_sign(param));
+ basis.push_back(false);
+ mapping.push_back(row_id);
+ var_row.push_back(var_id);
}
}
}
@@ -1123,27 +1157,15 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx,
/* ** Perform pivot operation ** */
- /* Check if column j_ or row i_ correspond to a problem variable */
- dimension_type var_j = n_a_d;
- dimension_type var_i = n_a_d;
- for (j=0; j<num_vars; ++j) {
- if (basis[j]) {
- if (mapping[j] == j_)
- var_j = j;
- } else {
- if (mapping[j] == i_)
- var_i = j;
- }
- }
/* update basis */
- if (var_j != n_a_d) {
- basis[var_j] = false;
- mapping[var_j] = i_;
- }
- if (var_i != n_a_d) {
- basis[var_i] = true;
- mapping[var_i] = j_;
- }
+ dimension_type var_j = var_column[j_];
+ dimension_type var_i = var_row[i_];
+ basis[var_j] = false;
+ mapping[var_j] = i_;
+ var_row[i_] = var_j;
+ basis[var_i] = true;
+ mapping[var_i] = j_;
+ var_column[j_] = var_i;
/* create the identity matrix row corresponding to basic variable j_ */
Row prs(num_vars, tableau.s_capacity(), Row::Flags());
@@ -1548,6 +1570,9 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx,
<< std::endl;
}
#endif
+ var_row.push_back(num_rows+num_vars);
+ basis.push_back(false);
+ mapping.push_back(num_rows);
sign.push_back(NEGATIVE);
}
}
diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh
index c9d3d1d..e9746df 100644
--- a/src/PIP_Tree.defs.hh
+++ b/src/PIP_Tree.defs.hh
@@ -296,6 +296,17 @@ private:
/*! \brief
A boolean vector for identifying the basic variables.
+ Variable identifiers are numbered from 0 to <tt>n+m-1</tt>, where \p n
+ is the number of columns in the simplex tableau corresponding to variables,
+ and \p m is the number of rows.
+
+ Indices from 0 to <tt>n-1</tt> correspond to the original variables.
+
+ Indices from \p n to <tt>n+m-1</tt> correspond to the slack variables
+ associated to the internal constraints, which do not strictly correspond
+ to original constraints, since these may have been transformed to fit the
+ standard form of the dual simplex.
+
The value for <tt>basis[i]</tt> is:
- \b true if variable \p i is basic,
- \b false if variable \p i is nonbasic.
@@ -314,6 +325,14 @@ private:
*/
std::vector<dimension_type> mapping;
+ /*! A vector of the variable identifiers associated to each row of the
+ simplex tableau. */
+ std::vector<dimension_type> var_row;
+
+ /*! A vector of the variable identifiers associated to each column of the
+ simplex tableau. */
+ std::vector<dimension_type> var_column;
+
//! The possible values for the sign of a parametric linear expression.
enum Row_Sign {
//! Not computed yet (default)
More information about the PPL-devel
mailing list