[PPL-devel] [GIT] ppl/ppl(master): Improved specification and implementation of erase_artificials().

[Enea Zaffanella]

Module: ppl/ppl
Branch: master
Commit: 16cbdda5d7d356f811034951fa25bb45f89aa9cc
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=16cbdda5d7d356f811034951fa25bb45f89aa9cc

Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date:   Mon Jun 28 09:36:56 2010 +0200

Improved specification and implementation of erase_artificials().

---

 src/MIP_Problem.cc      |   29 ++++++++++++++---------------
 src/MIP_Problem.defs.hh |   12 ++++++++++++
 2 files changed, 26 insertions(+), 15 deletions(-)

diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc
index 30e88e6..c388715 100644
--- a/src/MIP_Problem.cc
+++ b/src/MIP_Problem.cc
@@ -832,8 +832,8 @@ PPL::MIP_Problem::process_pending_constraints() {
     base[i] = artificial_index;
     ++artificial_index;
   }
-  // The last column index of the tableau containing an artificial variable.
-  const dimension_type end_artificials = artificial_index - 1;
+  // One past the last tableau column index containing an artificial variable.
+  const dimension_type end_artificials = artificial_index;
 
   // Set the extra-coefficient of the cost functions to record its sign.
   // This is done to keep track of the possible sign's inversion.
@@ -1326,16 +1326,18 @@ PPL::MIP_Problem::compute_simplex_using_exact_pricing() {
 void
 PPL::MIP_Problem::erase_artificials(const dimension_type begin_artificials,
 				    const dimension_type end_artificials) {
-  const dimension_type tableau_last_index = tableau.num_columns() - 1;
+  PPL_ASSERT(0 < begin_artificials && begin_artificials < end_artificials);
+
+  const dimension_type old_last_column = tableau.num_columns() - 1;
   dimension_type tableau_n_rows = tableau.num_rows();
   // Step 1: try to remove from the base all the remaining slack variables.
   for (dimension_type i = 0; i < tableau_n_rows; ++i)
-    if (begin_artificials <= base[i] && base[i] <= end_artificials) {
+    if (begin_artificials <= base[i] && base[i] < end_artificials) {
       // Search for a non-zero element to enter the base.
       Row& tableau_i = tableau[i];
       bool redundant = true;
-      for (dimension_type j = end_artificials+1; j-- > 1; )
-	if (!(begin_artificials <= j && j <= end_artificials)
+      for (dimension_type j = end_artificials; j-- > 1; )
+	if (!(begin_artificials <= j && j < end_artificials)
 	    && tableau_i[j] != 0) {
 	  pivot(j, i);
 	  redundant = false;
@@ -1360,21 +1362,18 @@ PPL::MIP_Problem::erase_artificials(const dimension_type begin_artificials,
 
   // Step 2: Adjust data structures so as to enter phase 2 of the simplex.
 
-  // Compute the dimensions of the new tableau.
-  dimension_type num_artificials = 0;
-  for (dimension_type i = end_artificials + 1; i-- > 1; )
-    if (begin_artificials <= i && i <= end_artificials) {
-      ++num_artificials;
-      tableau.remove_trailing_columns(1);
-    }
+  // Resize the tableau.
+  const dimension_type num_artificials = end_artificials - begin_artificials;
+  tableau.remove_trailing_columns(num_artificials);
 
   // Zero the last column of the tableau.
+  const dimension_type new_last_column = tableau.num_columns() - 1;
   for (dimension_type i = tableau_n_rows; i-- > 0; )
-    tableau[i][tableau.num_columns()-1] = 0;
+    tableau[i][new_last_column] = 0;
 
   // ... then properly set the element in the (new) last column,
   // encoding the kind of optimization; ...
-  working_cost[tableau.num_columns()-1] = working_cost[tableau_last_index];
+  working_cost[new_last_column] = working_cost[old_last_column];
   // ... and finally remove redundant columns.
   const dimension_type working_cost_new_size
     = working_cost.size() - num_artificials;
diff --git a/src/MIP_Problem.defs.hh b/src/MIP_Problem.defs.hh
index f39f453..63a39db 100644
--- a/src/MIP_Problem.defs.hh
+++ b/src/MIP_Problem.defs.hh
@@ -728,6 +728,18 @@ private:
   /*! \brief
     Drop unnecessary artificial variables from the tableau and get ready
     for the second phase of the simplex algorithm.
+
+    \note
+    The two parameters denote a STL-like half-open range.
+    It is assumed that \p begin_artificials is strictly greater than 0
+    and smaller than \p end_artificials.
+
+    \param begin_artificials
+    The start of the tableau column index range for artificial variables.
+
+    \param end_artificials
+    The end of the tableau column index range for artificial variables.
+    Note that column index end_artificial is \e excluded from the range.
   */
   void erase_artificials(dimension_type begin_artificials,
 			 dimension_type end_artificials);