[PPL-devel] [GIT] ppl/ppl(pip): Context compatibility check now searches for valid integer solutions.

[François Galea]

Module: ppl/ppl
Branch: pip
Commit: 9d6df94a8a65aa86474a9e2f26322e3954c36e7d
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9d6df94a8a65aa86474a9e2f26322e3954c36e7d

Author: François Galea <francois.galea at uvsq.fr>
Date:   Wed Oct 21 12:39:17 2009 +0200

Context compatibility check now searches for valid integer solutions.

---

 src/PIP_Tree.cc                  |   32 +++++++++++++++++++++++++++++---
 src/PIP_Tree.defs.hh             |    3 +++
 tests/PIP_Problem/pipproblem1.cc |    2 +-
 3 files changed, 33 insertions(+), 4 deletions(-)

diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 355f8f1..6f04139 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -686,6 +686,8 @@ PIP_Solution_Node::row_sign(const Row &x) {
 
 bool
 PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) {
+  if (ctx.num_rows() == 0)
+    return true;
   Matrix s(ctx);
   s.add_row(cnst);
   dimension_type i, i_, j, k, j_, j__, var_i, var_j;
@@ -732,8 +734,32 @@ PIP_Solution_Node::compatibility_check(const Matrix &ctx, const Row &cnst) {
     }
 
     if (j == 0) {
-      // No negative RHS: optimum found
-      return true;
+      // No negative RHS: fractional optimum found. If it is integer, then
+      // the test is successful. Otherwise, generate a new cut.
+      for (i=0; i<num_vars; ++i) {
+        if (basis[i])
+          // basic variable = 0 -> integer
+          continue;
+        // nonbasic variable
+        i_ = mapping[i];
+        if (s[i_][0] % scaling[i_] != 0)
+          // constant term is not integer
+          break;
+      }
+      if (i==num_vars) {
+        // Found an integer solution, thus the check is successful
+        return true;
+      }
+      // Generate a new cut
+      s.add_zero_rows(1, Row::Flags());
+      const Row& row = s[i_];
+      Row& cut = s[num_rows++];
+      scaling.push_back(1);
+      const Coefficient& sc = scaling[i_];
+      for (j=0; j<num_cols; ++j)
+        mod_assign(cut[j], row[j], sc);
+      cut[0] -= sc;
+      continue;
     }
 
     // Now we have a positive s[i][j] pivot
@@ -1340,7 +1366,7 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx,
     }
 
     /* Otherwise, all parameters are positive: we have found a continuous
-     * solution. If the solution happens to be integer, then it is a
+     * solution. If the solution happens to be integer, then it is the
      * solution of the  integer problem. Otherwise, we may need to generate
      * a new cut to try and get back into the integer case. */
     else {
diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh
index c2a8186..8c3704f 100644
--- a/src/PIP_Tree.defs.hh
+++ b/src/PIP_Tree.defs.hh
@@ -335,6 +335,9 @@ private:
     Matrix consisting in the original matrix with the constraint inserted. If
     the simplex terminates with a feasible (optimal) solution, then the
     restrained context is not empty. Otherwise, it is.
+
+    The algorithm ensures the feasible solutions are integer, by applying a
+    cut generation method when intermediate non-integer solutions are found.
   */
   static bool compatibility_check(const Matrix &ctx, const Row &cnst);
 
diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc
index 65b58aa..f250ccb 100644
--- a/tests/PIP_Problem/pipproblem1.cc
+++ b/tests/PIP_Problem/pipproblem1.cc
@@ -241,7 +241,7 @@ test06() {
 
   PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params);
 
-  bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM);
+  bool ok = (pip.solve() == UNFEASIBLE_PIP_PROBLEM);
   if (ok) {
     const PIP_Tree solution = pip.solution();
     display_solution(solution, params, Variables_Set(i),