Module: ppl/ppl Branch: sparse_matrices Commit: 30a048b00fe98b60a13b378261908e4373a275d3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=30a048b00fe98...

Author: Marco Poletti poletti.marco@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) {