- PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: use a hint iterator for insertions in working_cost, in process_pending_constraints().
by Marco Poletti 15 Sep '10

15 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: 343524886abe52d344037a76b186c913eec2f8d4 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=343524886abe… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 11:32:27 2010 +0200 MIP_Problem: use a hint iterator for insertions in working_cost, in process_pending_constraints(). --- src/MIP_Problem.cc | 11 ++++++++--- 1 files changed, 8 insertions(+), 3 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 1b54d00..58c2112 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -842,12 +842,16 @@ PPL::MIP_Problem::process_pending_constraints() { // constraint, will enter the base and will have coefficient -1 in // the cost function. + // This is used as a hint for insertions in working_cost. + working_cost_type::iterator cost_itr = working_cost.end(); + // First go through nonpending constraints that became unfeasible // due to re-merging of split variables. for (dimension_type i = 0; i < unfeasible_tableau_rows_size; ++i) { tableau[unfeasible_tableau_rows[i]].find_create(artificial_index, Coefficient_one()); - working_cost[artificial_index] = -1; + cost_itr = working_cost.find_create(cost_itr, artificial_index); + *cost_itr = -1; base[unfeasible_tableau_rows[i]] = artificial_index; ++artificial_index; } @@ -858,7 +862,8 @@ PPL::MIP_Problem::process_pending_constraints() { if (worked_out_row[i]) continue; tableau[i].find_create(artificial_index, Coefficient_one()); - working_cost[artificial_index] = -1; + cost_itr = working_cost.find_create(cost_itr, artificial_index); + *cost_itr = -1; base[i] = artificial_index; ++artificial_index; } @@ -868,7 +873,7 @@ PPL::MIP_Problem::process_pending_constraints() { // Set the extra-coefficient of the cost functions to record its sign. // This is done to keep track of the possible sign's inversion. const dimension_type last_obj_index = working_cost.size() - 1; - working_cost[last_obj_index] = 1; + working_cost.find_create(cost_itr, last_obj_index, Coefficient_one()); // Express the problem in terms of the variables in base. {

1 0

[GIT] ppl/ppl(MPI): New commits
by Roberto Bagnara 14 Sep '10

14 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8f3954c15599… Merge: 2ade37d6b3e355a4086d47adbb98cecabb657d58 c68f9092edf4b116fc1a595e8a997a3614ab3cac Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 15:54:22 2010 +0200 Merge remote branch 'origin/sparse_matrices' into MPI Conflicts: src/MIP_Problem.cc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2ade37d6b3e3… Merge: 9abc1a01465c0c041a332bc803503a3d5e34f590 92e46ffb3c1023ee0fb67f149674023a947f9563 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 15:48:51 2010 +0200 Merge commit '92e46ff' into MPI URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9abc1a01465c… Merge: 06ffe61bf2d1c245e5909b7bd9e84b02bd6ff134 c2aa82c4a7c984a3f71664734c1b37dc1bea7ab1 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 15:47:21 2010 +0200 Merge commit 'c2aa82c' into MPI URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=06ffe61bf2d1… Merge: ce64d4874f6b95581ad9b6f89dca537c60a731b6 ee1d1d7f9add38f040d24ca1d426d22758efde12 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 15:45:40 2010 +0200 Merge commit 'ee1d1d7' into MPI URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ce64d4874f6b… Merge: b04819828fcd89846fd1b2938460a3133aaf1141 1c643c26434574b11f0cfdbd46f8d4f58a0c0647 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 15:42:17 2010 +0200 Merge commit '1c643c2' into MPI URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b04819828fcd… Merge: 56a26e1958ee213970e36f1d1b10daade6ea5cc7 24ec2790edae6b616014adc2ab0f446b6f5711d6 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 15:25:41 2010 +0200 Merge commit '24ec279' into MPI URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=56a26e1958ee… Merge: f7e4405f7ff414e9b511b5dea4f219da9bd07553 ffe3720ee01517aa167654b4151f72fab4d7f006 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 15:16:40 2010 +0200 Merge commit 'ffe3720' into MPI Conflicts: src/Sparse_Row.defs.hh src/Sparse_Row.inlines.hh URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c68f9092edf4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:56:42 2010 +0200 MIP_Problem: optimize further steepest_edge_float_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=30a048b00fe9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:56:03 2010 +0200 MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f2479e2b3e49… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:34:19 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=07dfb14d484e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:26:46 2010 +0200 MIP_Problem: fix regression in textbook_entering_index(), introduced in commit 6880A6. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f6a93645a5b8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:39:00 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#4). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2c0d6052ae00… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:38:42 2010 +0200 MIP_Problem: avoid an unnecessary copy of the working_cost row, in second_phase(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2d1cbd6415ae… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:26:37 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#3). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8bbd7540511b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:24:01 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#2). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=42a7e27f4267… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:21:59 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#1). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b5e34c885640… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:36:09 2010 +0200 MIP_Problem: little optimizations for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6880a6746e15… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:30:38 2010 +0200 MIP_Problem: optimize textbook_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=92e46ffb3c10… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:28:37 2010 +0200 MIP_Problem: optimize steepest_edge_float_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c2aa82c4a7c9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:23:52 2010 +0200 MIP_Problem: optimize steepest_edge_exact_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ee1d1d7f9add… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 11:53:55 2010 +0200 MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1c643c264345… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 11:53:30 2010 +0200 Sparse_Row: add some assertions. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=24ec2790edae… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 10:39:22 2010 +0200 MIP_Problem: use a sparse working_cost when using sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ffe3720ee015… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 10:38:34 2010 +0200 Sparse_Row: add a constructor and two copy-constructors that take a capacity parameter.

1 0

[GIT] ppl/ppl(MPI): New commits
by Roberto Bagnara 14 Sep '10

14 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f7e4405f7ff4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 13 13:36:03 2010 +0200 Distributed_Sparse_Matrix: optimize get_exiting_and_pivot() (#2). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=14427c80ab4e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 13 12:29:54 2010 +0200 Distributed_Sparse_Matrix: optimize get_exiting_and_pivot() (#1). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=fe21222b228a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 13 12:00:45 2010 +0200 Distributed_Sparse_Matrix: add a get_exiting_and_pivot() method and use it in MIP_Problem. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4f3e7964e321… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 13 09:12:50 2010 +0200 Distributed_Sparse_Matrix: inline simple methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2939e43d9cd9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 13 08:37:05 2010 +0200 Distributed_Sparse_Matrix: use linear_combine in linear_combine_with_base_rows__common(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=08886d33c11a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Sep 13 08:36:33 2010 +0200 tests/MIP_Problem: don't check the optimum point in mipproblem3's test08. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b5af9ae9799b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 21:15:26 2010 +0200 Add an --enable-mpirun-jobs option to configure. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3cb42cdde800… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 19:30:05 2010 +0200 Distributed_Sparse_Matrix: check that the nodes store no data at exit. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=fb96027aa9b7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 19:17:03 2010 +0200 Distributed_Sparse_Matrix: add an argument to linear_combine_matrix(), avoiding an additional broadcast in MIP_Problem::pivot(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0e749958ce4c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 19:10:27 2010 +0200 Distributed_Sparse_Matrix: remove debug messages from operator==(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8e09e240ef6f… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 18:47:43 2010 +0200 Distributed_Sparse_Matrix::Worker: use the same code paths for both stored and unstored row chunks, simplifying code and improving maintainability. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2b566d9b1dc5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 18:46:30 2010 +0200 Distributed_Sparse_Matrix::Worker: add a get_row_chunk() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4449ebb5bc97… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 17:42:54 2010 +0200 Distributed_Sparse_Matrix: specialize boost::mpi::is_commutative when needed. Fix existing specialization. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0615afb7adc2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 17:31:57 2010 +0200 MIP_Problem: rename distributed_tableau into tableau. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a1629bad8fd2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 17:31:32 2010 +0200 Distributed_Sparse_Matrix: add typedef for row_type. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=bd003735058e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 17:13:42 2010 +0200 MIP_Problem: don't keep a Sparse_Matrix copy of the tableau when using distributed matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9689c9fbf825… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 16:45:33 2010 +0200 Distributed_Sparse_Matrix: process candidates backwards in exact_entering_index(), to pass the PPL tests. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=14a758152946… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 14:18:57 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::base_variables_occur_once() in OK(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7be32c883b31… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 14:18:30 2010 +0200 Distributed_Sparse_Matrix: add a base_variables_occur_once() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f36456c7bce6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 13:29:18 2010 +0200 Distributed_Sparse_Matrix: simplify worker_main_loop(), using macros. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=207bcfe68df8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 12:36:34 2010 +0200 Distributed_Sparse_Matrix: merge the add_row_into_base() and remove_row_from_base() methods into a single set_base_column() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=31f6d132938c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 12:27:45 2010 +0200 MIP_Problem: take into account the external memory occupied by distributed_tableau in external_memory_in_bytes(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3a31bce55738… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 12:27:02 2010 +0200 Distributed_Sparse_Matrix: add a external_memory_in_bytes() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cbcc18f8c3ed… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 12:16:50 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::remove_row(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2f56d327db6a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 12:16:16 2010 +0200 Distributed_Sparse_Matrix: add a remove_row() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c2b247862430… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 11:29:57 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::get_row() in erase_artificials(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=33109c91d5b9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 11:10:53 2010 +0200 MIP_Problem: use Distributed_Sparse_Matrix::exiting_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4952882351e3… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 11:10:26 2010 +0200 Distributed_Sparse_Matrix: add an exiting_index() method.

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: optimize further steepest_edge_float_entering_index() for sparse working_cost rows.
by Marco Poletti 14 Sep '10

14 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: c68f9092edf4b116fc1a595e8a997a3614ab3cac URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c68f9092edf4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:56:42 2010 +0200 MIP_Problem: optimize further steepest_edge_float_entering_index() for sparse working_cost rows. --- src/MIP_Problem.cc | 18 ++++++++++++------ 1 files changed, 12 insertions(+), 6 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 9db9ffb..1b54d00 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -996,9 +996,13 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { #if USE_PPL_SPARSE_MATRIX const dimension_type tableau_num_columns_minus_1 = tableau_num_columns - 1; + // This is static to improve performance. // A vector of <column_index, challenger_den> pairs, ordered by // column_index. - std::vector<std::pair<dimension_type, double> > columns; + static std::vector<std::pair<dimension_type, double> > columns; + columns.clear(); + // (working_cost.size() - 2) is an upper bound only. + columns.reserve(working_cost.size() - 2); { working_cost_type::const_iterator i = working_cost.lower_bound(1); // Note that find() is used instead of lower_bound(). @@ -1020,12 +1024,14 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { = columns.end(); while (j != j_end && k != k_end) { const dimension_type column = j.index(); - if (k->first != column) { - if (k->first < column) - ++k; - else - j = tableau_i.lower_bound(j, k->first); + while (k != k_end && column > k->first) + ++k; + if (k == k_end) + break; + if (k->first > column) { + j = tableau_i.lower_bound(j, k->first); } else { + PPL_ASSERT(k->first == column); Coefficient_traits::const_reference tableau_ij = *j; WEIGHT_BEGIN(); if (tableau_ij != 0) {

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows.
by Marco Poletti 14 Sep '10

14 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: 30a048b00fe98b60a13b378261908e4373a275d3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=30a048b00fe9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:56:03 2010 +0200 MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows. --- src/MIP_Problem.cc | 14 +++++++++++--- 1 files changed, 11 insertions(+), 3 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 784880d..9db9ffb 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -871,9 +871,17 @@ PPL::MIP_Problem::process_pending_constraints() { working_cost[last_obj_index] = 1; // Express the problem in terms of the variables in base. - for (dimension_type i = tableau_num_rows; i-- > 0; ) - if (working_cost.get(base[i]) != 0) - linear_combine(working_cost, tableau[i], base[i]); + { + working_cost_type::const_iterator itr = working_cost.end(); + for (dimension_type i = tableau_num_rows; i-- > 0; ) { + itr = working_cost.lower_bound(itr, base[i]); + if (itr != working_cost.end() && itr.index() == base[i] && *itr != 0) { + linear_combine(working_cost, tableau[i], base[i]); + // itr has been invalidated by the call to linear_combine(). + itr = working_cost.end(); + } + } + } // Deal with zero dimensional problems. if (space_dimension() == 0) {

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: optimize second_phase() for sparse working_cost rows.
by Marco Poletti 14 Sep '10

14 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: f2479e2b3e49803d56e972cf3e036d238037030b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f2479e2b3e49… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:34:19 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows. --- src/MIP_Problem.cc | 18 +++++++++++++----- 1 files changed, 13 insertions(+), 5 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 560b47a..784880d 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1857,12 +1857,20 @@ PPL::MIP_Problem::second_phase() { i = new_cost.begin(), i_end = new_cost.end(); i != i_end; ++i) neg_assign(*i); - // Substitute properly the cost function in the `costs' matrix. const dimension_type cost_zero_size = working_cost.size(); - working_cost_type tmp_cost = working_cost_type(cost_zero_size, - cost_zero_size, - new_cost.flags()); - tmp_cost.swap(working_cost); + + // Substitute properly the cost function in the `costs' matrix. +#if USE_PPL_SPARSE_MATRIX + working_cost.clear(); + working_cost.flags() = Row_Flags(); +#else + { + working_cost_type tmp_cost = working_cost_type(cost_zero_size, + cost_zero_size, + new_cost.flags()); + tmp_cost.swap(working_cost); + } +#endif { working_cost_type::iterator itr

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: fix regression in textbook_entering_index(), introduced in commit 6880A6.
by Marco Poletti 14 Sep '10

14 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: 07dfb14d484ef7b552388152934e3e0ae6f1099b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=07dfb14d484e… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 14:26:46 2010 +0200 MIP_Problem: fix regression in textbook_entering_index(), introduced in commit 6880A6. --- src/MIP_Problem.cc | 10 +++++++--- 1 files changed, 7 insertions(+), 3 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 3538b33..560b47a 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1266,9 +1266,13 @@ PPL::MIP_Problem::textbook_entering_index() const { const dimension_type cost_sign_index = working_cost.size() - 1; const int cost_sign = sgn(working_cost.get(cost_sign_index)); PPL_ASSERT(cost_sign != 0); - for (working_cost_type::const_iterator - i = working_cost.lower_bound(1), i_end = working_cost.end(); - i != i_end; ++i) + + working_cost_type::const_iterator i = working_cost.lower_bound(1); + // Note that find() is used instead of lower_bound() because they are + // equivalent when searching the last element in the row. + working_cost_type::const_iterator i_end + = working_cost.find(cost_sign_index); + for ( ; i != i_end; ++i) if (sgn(*i) == cost_sign) return i.index(); // No variable has to enter the base:

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 14 Sep '10

14 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f6a93645a5b8… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:39:00 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#4). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2c0d6052ae00… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:38:42 2010 +0200 MIP_Problem: avoid an unnecessary copy of the working_cost row, in second_phase(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2d1cbd6415ae… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:26:37 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#3). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8bbd7540511b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:24:01 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#2). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=42a7e27f4267… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 13:21:59 2010 +0200 MIP_Problem: optimize second_phase() for sparse working_cost rows (#1). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b5e34c885640… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:36:09 2010 +0200 MIP_Problem: little optimizations for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6880a6746e15… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:30:38 2010 +0200 MIP_Problem: optimize textbook_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=92e46ffb3c10… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:28:37 2010 +0200 MIP_Problem: optimize steepest_edge_float_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c2aa82c4a7c9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 12:23:52 2010 +0200 MIP_Problem: optimize steepest_edge_exact_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ee1d1d7f9add… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 11:53:55 2010 +0200 MIP_Problem: optimize process_pending_constraints() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1c643c264345… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 11:53:30 2010 +0200 Sparse_Row: add some assertions. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=24ec2790edae… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 10:39:22 2010 +0200 MIP_Problem: use a sparse working_cost when using sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ffe3720ee015… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 10:38:34 2010 +0200 Sparse_Row: add a constructor and two copy-constructors that take a capacity parameter. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=620592736a50… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 12 10:56:32 2010 +0200 MIP_Problem: improve a little bit the get_exiting_base_index() performance. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ad3694d4bbf7… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Thu Sep 9 17:13:48 2010 +0200 Reflected the changes in http://gcc.gnu.org/bugzilla/show_bug.cgi?id=8966 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4974d4f39e8c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Sep 9 08:25:24 2010 +0200 MIP_Problem: don't copy Coefficient objects to cache accesses, in steepest_edge_exact_entering_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ab1231051fa8… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Wed Sep 8 07:31:19 2010 +0200 Mentioned the fix to Interval::Interval(const char*). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3e2fe287b4ef… Author: Abramo Bagnara <abramo.bagnara(a)gmail.com> Date: Tue Sep 7 23:13:17 2010 +0200 Fixed interval construction from strings. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=22c92f00fb9e… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Sep 7 20:01:44 2010 +0200 Announced a couple of new features and bugfixes. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f949a0fced31… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Tue Sep 7 19:31:56 2010 +0200 Mention the use of sparse matrices in MIP and PIP solvers. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=46655e57eb7d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 7 19:05:39 2010 +0200 MIP_Problem: fix some debug messages and comments, in OK(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8df25ad97af2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 7 18:49:40 2010 +0200 MIP_Problem: fix typos in some debug messages and comments, in OK(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=359b3a83e66e… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Tue Sep 7 16:07:22 2010 +0200 test06 fails with 8-bit coefficients. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=384f089de7b9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 5 19:33:59 2010 +0200 tests/CO_Tree: modify the tests so that they pass even with 8-bit coefficients. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=fbd049063bb7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 5 19:32:52 2010 +0200 tests/Sparse_Matrix: modify the tests so that they pass even when using 8-bit coefficients. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=eaf5206df76c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Sep 5 12:14:47 2010 +0200 tests/CO_Tree: use DO_TEST_F8 when a test is expected to fail with 8-bit coefficients.

1 0

[GIT] ppl/ppl(floating_point): Adapted tests on digital filters to latest changes.
by Fabio Bossi 13 Sep '10

13 Sep '10

Module: ppl/ppl Branch: floating_point Commit: ebcd55e82f73703737752a66ca25891ece02661a URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ebcd55e82f73… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Mon Sep 13 17:42:12 2010 +0200 Adapted tests on digital filters to latest changes. --- tests/Concrete_Expression/Makefile.am | 1 + tests/Concrete_Expression/digitalfilters1.cc | 371 +++++++++++++++----------- 2 files changed, 210 insertions(+), 162 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=ebcd55e8…

1 0

[GIT] ppl/ppl(floating_point): Do not fail automatically when linearizing approximable
by Fabio Bossi 13 Sep '10

13 Sep '10

Module: ppl/ppl Branch: floating_point Commit: 219f235033052dd7e24399eb9d1e494911ed0401 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=219f23503305… Author: Fabio Bossi <bossi(a)cs.unipr.it> Date: Mon Sep 13 14:08:29 2010 +0200 Do not fail automatically when linearizing approximable references having more than one associated dimension. --- src/Float.defs.hh | 16 ++++++--- src/linearize.hh | 44 +++++++++++++++++++++----- tests/Concrete_Expression/C_Expr.defs.hh | 12 +++--- tests/Concrete_Expression/C_Expr.inlines.hh | 5 ++- tests/Concrete_Expression/linearize.cc | 45 ++++++++++++++++++++++++-- 5 files changed, 96 insertions(+), 26 deletions(-) diff --git a/src/Float.defs.hh b/src/Float.defs.hh index 059d3e4..ad67317 100644 --- a/src/Float.defs.hh +++ b/src/Float.defs.hh @@ -433,14 +433,18 @@ public: FP_Interval_Type& result) const = 0; /*! \brief - Asks the external analyzer for the space dimension associated to - the approximable reference \p expr. + Asks the external analyzer for the possible space dimensions that + are associated to the approximable reference \p expr. + Result is stored into \p result. + + \return <CODE>true</CODE> if the analyzer was able to return + the (possibly empty!) set, <CODE>false</CODE> otherwise. - \return the associated space dimension if succesful, - <CODE>not_a_dimension()<CODE> otherwise. + The resulting set MUST NOT contain <CODE>not_a_dimension()</CODE>. */ - virtual dimension_type get_associated_dimension( - const Approximable_Reference<Target>& expr) const = 0; + virtual bool get_associated_dimensions( + const Approximable_Reference<Target>& expr, + std::set<dimension_type>& result) const = 0; }; diff --git a/src/linearize.hh b/src/linearize.hh index 0aaa464..8767f80 100644 --- a/src/linearize.hh +++ b/src/linearize.hh @@ -738,15 +738,22 @@ linearize(const Concrete_Expression<Target>& expr, { const Approximable_Reference<Target>* ref_expr = expr.template as<Approximable_Reference>(); - /* Variable references are the only that we are currently - able to analyze */ - dimension_type variable_index = oracle.get_associated_dimension(*ref_expr); - if (variable_index == not_a_dimension()) + std::set<dimension_type> associated_dimensions; + if (!oracle.get_associated_dimensions(*ref_expr, associated_dimensions) + || associated_dimensions.empty()) + /* + We were unable to find any associated space dimension: + linearization fails. + */ return false; - else { - /* If a linear form associated to the referenced variable - exists in lf_store, return that form. Otherwise, return - the simplest linear form. */ + + if (associated_dimensions.size() == 1) { + /* If a linear form associated to the only referenced + space dimension exists in lf_store, return that form. + Otherwise, return the simplest linear form. */ + dimension_type variable_index = *associated_dimensions.begin(); + PPL_ASSERT(variable_index != not_a_dimension()); + typename FP_Linear_Form_Abstract_Store::const_iterator variable_value = lf_store.find(variable_index); if (variable_value == lf_store.end()) { @@ -759,6 +766,27 @@ linearize(const Concrete_Expression<Target>& expr, that an unbounded linear form was saved into lf_store? */ return !result.overflows(); } + + /* + Here associated_dimensions.size() > 1. Try to return the LUB + of all intervals associated to each space dimension. + */ + std::set<dimension_type>::const_iterator i = associated_dimensions.begin(); + std::set<dimension_type>::const_iterator i_end = + associated_dimensions.end(); + FP_Interval_Type lub(EMPTY); + for (; i != i_end; ++i) { + FP_Interval_Type curr_int; + PPL_ASSERT(*i != not_a_dimension()); + if (!oracle.get_interval(*i, curr_int)) + return false; + + lub.join_assign(curr_int); + } + + result = FP_Linear_Form(lub); + return !result.overflows(); + break; } case Cast_Operator<Target>::KIND: diff --git a/tests/Concrete_Expression/C_Expr.defs.hh b/tests/Concrete_Expression/C_Expr.defs.hh index 40de1c0..32104eb 100644 --- a/tests/Concrete_Expression/C_Expr.defs.hh +++ b/tests/Concrete_Expression/C_Expr.defs.hh @@ -227,10 +227,10 @@ class Approximable_Reference<C_Expr> : public Concrete_Expression<C_Expr>, public Approximable_Reference_Common<C_Expr> { public: - //! Builds a reference to the variable having the given index. + //! Builds a reference to the entity having the given index. Approximable_Reference<C_Expr>(Concrete_Expression_Type type, - const Integer_Interval_Type& val, - dimension_type var_index); + const Integer_Interval_Type& val, + dimension_type index); //! Do-nothing destructor. ~Approximable_Reference<C_Expr>(); @@ -241,11 +241,11 @@ public: //! Constant identifying approximable reference nodes. enum { KIND = APPROX_REF }; - //! An interval in which the variable's value falls. + //! An interval in which the referenced entity's value falls. Integer_Interval_Type value; - //! The index of the referenced variable. - dimension_type var_dimension; + //! The set of possible indexes for the referenced entity. + std::set<dimension_type> dimensions; }; } // namespace Parma_Polyhedra_Library diff --git a/tests/Concrete_Expression/C_Expr.inlines.hh b/tests/Concrete_Expression/C_Expr.inlines.hh index accb5d0..d12ccd5 100644 --- a/tests/Concrete_Expression/C_Expr.inlines.hh +++ b/tests/Concrete_Expression/C_Expr.inlines.hh @@ -165,10 +165,11 @@ inline Approximable_Reference<C_Expr>:: Approximable_Reference(Concrete_Expression_Type type, const Integer_Interval_Type& val, - dimension_type var_index) + dimension_type index) : Concrete_Expression<C_Expr>(type, APPROX_REF), value(val), - var_dimension(var_index) { + dimensions() { + dimensions.insert(index); } inline diff --git a/tests/Concrete_Expression/linearize.cc b/tests/Concrete_Expression/linearize.cc index 1cf9ae9..26dcf0e 100644 --- a/tests/Concrete_Expression/linearize.cc +++ b/tests/Concrete_Expression/linearize.cc @@ -58,9 +58,11 @@ public: return true; } - dimension_type get_associated_dimension( - const Approximable_Reference<C_Expr>& expr) const { - return expr.var_dimension; + bool get_associated_dimensions( + const Approximable_Reference<C_Expr>& expr, + std::set<dimension_type>& result) const { + result = expr.dimensions; + return true; } FP_Interval_Abstract_Store int_store; @@ -99,10 +101,13 @@ test02() { Binary_Operator<C_Expr> dif(FP_Type, Binary_Operator<C_Expr>::SUB, &var1, &con); Binary_Operator<C_Expr> mul(FP_Type, Binary_Operator<C_Expr>::MUL, &dif, &var0); FP_Linear_Form result; - linearize(mul, oracle, FP_Linear_Form_Abstract_Store(), result); + if (!linearize(mul, oracle, FP_Linear_Form_Abstract_Store(), result)) + return false; FP_Linear_Form known_result(compute_absolute_error<FP_Interval>(ANALYZED_FP_FORMAT)); + nout << "*** result ***" << endl + << result << endl; nout << "*** known_result ***" << endl << known_result << endl; bool ok = (result == known_result); @@ -274,6 +279,37 @@ test08() { return ok1 && ok2; } +/* + Tests linearization of an approximable reference having more than + one associated index. +*/ +bool +test09() { + Test_Oracle oracle(FP_Interval_Abstract_Store(4)); + oracle.int_store.set_interval(Variable(0), FP_Interval(0)); + oracle.int_store.set_interval(Variable(1), FP_Interval(10)); + oracle.int_store.set_interval(Variable(2), FP_Interval(20)); + oracle.int_store.set_interval(Variable(3), FP_Interval(5)); + Approximable_Reference<C_Expr> ref(FP_Type, Int_Interval(mpz_class(0)), 0); + ref.dimensions.insert(1); + ref.dimensions.insert(3); + FP_Linear_Form result; + if (!linearize(ref, oracle, FP_Linear_Form_Abstract_Store(), result)) + return false; + + FP_Interval known_int(FP_Interval(0)); + known_int.join_assign(FP_Interval(10)); + FP_Linear_Form known_result(known_int); + + nout << "*** result ***" << endl + << result << endl; + nout << "*** known_result ***" << endl + << known_result << endl; + bool ok = (result == known_result); + + return ok; +} + } // namespace BEGIN_MAIN @@ -285,4 +321,5 @@ BEGIN_MAIN DO_TEST(test06); DO_TEST(test07); DO_TEST(test08); + DO_TEST(test09); END_MAIN

1 0