Module: ppl/ppl Branch: master Commit: 3cb3ce1f0be968a3a73804e7f63837e0d10aee96 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3cb3ce1f0be96...
Author: Enea Zaffanella zaffanella@cs.unipr.it Date: Fri Feb 19 22:32:24 2010 +0100
Started working on incrementality. Dealt with a FIXME in PIP_Solution_Node::update_tableau(): when adding new problem variables and parameters, the columns of the existing artificial parameters are moved to the right of the tableau.t matrix.
---
src/PIP_Tree.cc | 82 ++++++++++++++++++++++++++-------------- src/PIP_Tree.defs.hh | 9 +++- tests/PIP_Problem/Makefile.am | 3 +- 3 files changed, 61 insertions(+), 33 deletions(-)
diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b13e3a2..222efeb 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1429,48 +1429,73 @@ PIP_Solution_Node::update_tableau(const PIP_Problem& problem, const dimension_type first_pending_constraint, const Constraint_Sequence& input_cs, const Variables_Set& parameters) { - dimension_type initial_space_dim; - if (tableau.t.num_columns() > 0) - initial_space_dim = tableau.s.num_columns() + tableau.t.num_columns() - 1; - else { - // Create parameter column, corresponding to the constant term. + // Make sure a parameter column exists, for the inhomogeneous term. + if (tableau.t.num_columns() == 0) tableau.t.add_zero_columns(1); - initial_space_dim = 0; + + // NOTE: here 'params' stands for problem (i.e., non artificial) parameters. + const dimension_type old_num_vars = tableau.s.num_columns(); + const dimension_type old_num_params + = problem.internal_space_dim - old_num_vars; + const dimension_type num_added_dims + = problem.external_space_dim - problem.internal_space_dim; + const dimension_type new_num_params = parameters.size(); + const dimension_type num_added_params = new_num_params - old_num_params; + const dimension_type num_added_vars = num_added_dims - num_added_params; + + const dimension_type old_num_art_params + = tableau.t.num_columns() - 1 - old_num_params; + + // Resize the two tableau matrices. + if (num_added_vars > 0) + tableau.s.add_zero_columns(num_added_vars); + if (num_added_params > 0) + tableau.t.add_zero_columns(num_added_params); + + if (num_added_params > 0 && old_num_art_params > 0) { + // Shift to the right the columns of artificial parameters. + std::vector<dimension_type> swaps; + swaps.reserve(3*old_num_art_params); + const dimension_type first_ap = 1 + old_num_params; + for (dimension_type i = 0; i < old_num_art_params; ++i) { + dimension_type old_ap = first_ap + i; + dimension_type new_ap = old_ap + num_added_params; + swaps.push_back(old_ap); + swaps.push_back(new_ap); + swaps.push_back(0); + } + tableau.t.permute_columns(swaps); }
- // Add new columns to the tableau. - /* FIXME: when the node or its parents have artificial parameters, we - must insert new parameter columns before the columns corresponding to - the artificial parameters. Meanwhile parameter insertion after a first - solve (incremental solving) is broken. */ + dimension_type new_var_column = old_num_vars; + const dimension_type initial_space_dim = old_num_vars + old_num_params; for (dimension_type i = initial_space_dim; i < external_space_dim; ++i) { - if (parameters.count(i) == 1) - // A new parameter. - tableau.t.add_zero_columns(1); - else { - // A new variable. - const dimension_type new_column = tableau.s.num_columns(); - tableau.s.add_zero_columns(1); + if (parameters.count(i) == 0) { + // A new problem variable. if (tableau.s.num_rows() == 0) { // No rows have been added yet basis.push_back(true); - mapping.push_back(new_column); - } else { - /* Need to insert the original variable id before the slack variable - id's to respect variable ordering */ - basis.insert(basis.begin() + new_column, true); - mapping.insert(mapping.begin() + new_column, new_column); - // update variable id's of slack variables + mapping.push_back(new_var_column); + } + else { + /* + Need to insert the original variable id + before the slack variable id's to respect variable ordering. + */ + basis.insert(basis.begin() + new_var_column, true); + mapping.insert(mapping.begin() + new_var_column, new_var_column); + // Update variable id's of slack variables. for (dimension_type j = var_row.size(); j-- > 0; ) - if (var_row[j] >= new_column) + if (var_row[j] >= new_var_column) ++var_row[j]; for (dimension_type j = var_column.size(); j-- > 0; ) - if (var_column[j] >= new_column) + if (var_column[j] >= new_var_column) ++var_column[j]; if (special_equality_row > 0) ++special_equality_row; } - var_column.push_back(new_column); + var_column.push_back(new_var_column); + ++new_var_column; } }
@@ -1487,7 +1512,6 @@ PIP_Solution_Node::update_tableau(const PIP_Problem& problem, c_iter = input_cs.begin() + first_pending_constraint, c_end = input_cs.end(); c_iter != c_end; ++c_iter) { const Constraint& constraint = *c_iter; - // (Tentatively) Add new rows to s and t matrices. // These will be removed at the end if they turn out to be useless. const dimension_type row_id = tableau.s.num_rows(); diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index 81a000f..a8cc6a9 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -36,9 +36,12 @@ site: http://www.cs.unipr.it/ppl/ . */
namespace Parma_Polyhedra_Library {
-/*! \brief - The base class for the nodes of the trees representing the solutions - of PIP problems. +//! 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. */ class PIP_Tree_Node { protected: diff --git a/tests/PIP_Problem/Makefile.am b/tests/PIP_Problem/Makefile.am index 19ea24e..f9d2598 100644 --- a/tests/PIP_Problem/Makefile.am +++ b/tests/PIP_Problem/Makefile.am @@ -52,7 +52,7 @@ $(top_builddir)/src/libppl.la \ TESTS = \ ascii_dump_load1 \ exceptions1 \ -pipproblem1 pipproblem2 +pipproblem1 pipproblem2 pipproblem3
XFAIL_TESTS =
@@ -68,6 +68,7 @@ exceptions1_SOURCES = exceptions1.cc
pipproblem1_SOURCES = pipproblem1.cc pipproblem2_SOURCES = pipproblem2.cc +pipproblem3_SOURCES = pipproblem3.cc
check_PROGRAMS = \ $(TESTS) \