[PPL-devel] [GIT] ppl/ppl(master): Started working on incrementality.
Enea Zaffanella
zaffanella at cs.unipr.it
Fri Feb 19 22:34:59 CET 2010
Module: ppl/ppl
Branch: master
Commit: 3cb3ce1f0be968a3a73804e7f63837e0d10aee96
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3cb3ce1f0be968a3a73804e7f63837e0d10aee96
Author: Enea Zaffanella <zaffanella at 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) \
More information about the PPL-devel
mailing list