[PPL-devel] [GIT] ppl/ppl(pip): Improved the last part of method PIP_Solution_Node:: solve().
Enea Zaffanella
zaffanella at cs.unipr.it
Wed Feb 3 19:01:26 CET 2010
Module: ppl/ppl
Branch: pip
Commit: 8fe9538a0dade2eed5ef50bab52f76339f9476b0
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8fe9538a0dade2eed5ef50bab52f76339f9476b0
Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date: Wed Feb 3 19:00:36 2010 +0100
Improved the last part of method PIP_Solution_Node::solve().
---
src/PIP_Tree.cc | 126 ++++++++++++++++++++++++++++---------------------------
1 files changed, 64 insertions(+), 62 deletions(-)
diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc
index 0a7eec8..1194450 100644
--- a/src/PIP_Tree.cc
+++ b/src/PIP_Tree.cc
@@ -1959,119 +1959,121 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref,
#endif
tableau.normalize();
- // Look for a row with non integer parameter coefficients (first is okay)
- const Coefficient& d = tableau.get_denominator();
- dimension_type i;
- for (i = 0; i < num_vars; ++i) {
- if (basis[i])
- // basic variable = 0 -> integer
+ // Look for any row having non integer parameter coefficients.
+ const Coefficient& den = tableau.get_denominator();
+ for (dimension_type k = 0; k < num_vars; ++k) {
+ if (basis[k])
+ // Basic variable = 0, hence integer.
continue;
- const Row& row = tableau.t[mapping[i]];
- for (dimension_type j = 0; j < num_params; ++j) {
- if (row[j] % d != 0)
- goto endsearch;
+ const dimension_type i = mapping[k];
+ const Row& t_i = tableau.t[i];
+ for (dimension_type j = num_params; j-- > 0; ) {
+ if (t_i[j] % den != 0)
+ goto non_integer;
}
}
- endsearch:
-
- if (i == num_vars) {
- /* The solution is integer */
+ // The goto was not taken, the solution is integer.
#ifdef NOISY_PIP
- std::cout << "Solution found for problem in current node."
- << std::endl;
+ std::cout << "Solution found for problem in current node.\n";
#endif
- return OPTIMIZED_PIP_PROBLEM;
- }
- /* The solution is non-integer. We have to generate a cut. */
+ return OPTIMIZED_PIP_PROBLEM;
+
+ non_integer:
+ // The solution is non-integer: generate a cut.
PPL_DIRTY_TEMP_COEFFICIENT(mod);
+ dimension_type best_i = not_a_dim;
+ dimension_type best_pcount = not_a_dim;
+
const PIP_Problem::Control_Parameter_Value cutting_strategy
= problem.control_parameters[PIP_Problem::CUTTING_STRATEGY];
+
if (cutting_strategy == PIP_Problem::CUTTING_STRATEGY_FIRST) {
// Find the first row with simplest parametric part.
- dimension_type best_i = not_a_dim;
- dimension_type best_pcount = not_a_dim;
- dimension_type pcount;
for (dimension_type k = 0; k < num_vars; ++k) {
if (basis[k])
continue;
- i = mapping[k];
- const Row& row_t = tableau.t[i];
- pcount = 0;
- for (dimension_type j = 0; j < num_params; ++j) {
- mod_assign(mod, row_t[j], d);
+ const dimension_type i = mapping[k];
+ const Row& t_i = tableau.t[i];
+ // Count the number of non-integer parameter coefficients.
+ dimension_type pcount = 0;
+ for (dimension_type j = num_params; j-- > 0; ) {
+ mod_assign(mod, t_i[j], den);
if (mod != 0)
++pcount;
}
- if (pcount != 0 && (best_i == not_a_dim || (pcount < best_pcount))) {
+ if (pcount > 0 && (best_i == not_a_dim || pcount < best_pcount)) {
best_pcount = pcount;
best_i = i;
}
}
+ // Generate cut using 'best_i'.
generate_cut(best_i, parameters, context, space_dim);
}
else {
assert(cutting_strategy == PIP_Problem::CUTTING_STRATEGY_DEEPEST
|| cutting_strategy == PIP_Problem::CUTTING_STRATEGY_ALL);
- /* Find the row with simplest parametric part which will generate
- the "deepest" cut */
- PPL_DIRTY_TEMP_COEFFICIENT(score);
- PPL_DIRTY_TEMP_COEFFICIENT(score2);
+ // Find the row with simplest parametric part
+ // which will generate the "deepest" cut.
PPL_DIRTY_TEMP_COEFFICIENT(best_score);
best_score = 0;
- dimension_type best_i = not_a_dim;
- dimension_type best_pcount = not_a_dim;
- dimension_type pcount;
+ PPL_DIRTY_TEMP_COEFFICIENT(score);
+ PPL_DIRTY_TEMP_COEFFICIENT(s_score);
std::vector<dimension_type> all_best_is;
+
for (dimension_type k = 0; k < num_vars; ++k) {
if (basis[k])
continue;
- i = mapping[k];
- const Row& row_t = tableau.t[i];
- const Row& row_s = tableau.s[i];
+ const dimension_type i = mapping[k];
+ // Compute score and pcount.
score = 0;
- pcount = 0;
- for (dimension_type j = 0; j < num_params; ++j) {
- mod_assign(mod, row_t[j], d);
+ dimension_type pcount = 0;
+ const Row& t_i = tableau.t[i];
+ for (dimension_type j = num_params; j-- > 0; ) {
+ mod_assign(mod, t_i[j], den);
if (mod != 0) {
- score += d - mod;
+ score += den;
+ score -= mod;
++pcount;
}
}
- score2 = 0;
- for (dimension_type j = 0; j < num_vars; ++j) {
- mod_assign(mod, row_s[j], d);
- score2 += d - mod;
+ // Compute s_score.
+ s_score = 0;
+ const Row& s_i = tableau.s[i];
+ for (dimension_type j = num_vars; j-- > 0; ) {
+ mod_assign(mod, s_i[j], den);
+ s_score += den;
+ s_score -= mod;
}
- score *= score2;
- /* Choose row i if:
- row i is non-integer
- AND (no row has been chosen yet
- OR row i has number of non-integer parameter
- coefficients lower than the current best row
- OR row i has the same number of non-integer parameter
- coefficients as the current best row, and its score is
- better)
+ // Combine 'score' and 's_score'.
+ score *= s_score;
+ /*
+ Select row i if it is non integer AND
+ - no row has been chosen yet; OR
+ - it has fewer non-integer parameter coefficients; OR
+ - it has the same number of non-integer parameter coefficients,
+ but its score is greater.
*/
if (pcount != 0
&& (best_i == not_a_dim
- || (pcount < best_pcount)
+ || pcount < best_pcount
|| (pcount == best_pcount && score > best_score))) {
if (pcount < best_pcount)
all_best_is.clear();
- best_score = score;
- best_pcount = pcount;
best_i = i;
+ best_pcount = pcount;
+ best_score = score;
}
if (pcount > 0)
all_best_is.push_back(i);
}
if (cutting_strategy == PIP_Problem::CUTTING_STRATEGY_DEEPEST)
generate_cut(best_i, parameters, context, space_dim);
- else /* cutting_strategy == PIP_Problem::CUTTING_STRATEGY_ALL */ {
- for (i = all_best_is.size(); i-- > 0; )
- generate_cut(all_best_is[i], parameters, context, space_dim);
+ else {
+ PPL_ASSERT(cutting_strategy == PIP_Problem::CUTTING_STRATEGY_ALL);
+ for (dimension_type k = all_best_is.size(); k-- > 0; )
+ generate_cut(all_best_is[k], parameters, context, space_dim);
}
- }
+ } // End of processing for non-integer solutions.
} // Main loop of the simplex algorithm
More information about the PPL-devel
mailing list