Module: ppl/ppl Branch: pip Commit: 9d6df94a8a65aa86474a9e2f26322e3954c36e7d URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9d6df94a8a65a... Author: François Galea <francois.galea@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),