Module: ppl/ppl Branch: pip Commit: 37b1e615b392957dbf9a03cdfa0afc24afca7368 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=37b1e615b3929... Author: François Galea <francois.galea@uvsq.fr> Date: Wed Dec 16 08:32:19 2009 +0100 Added a more aggressive cutting strategy which generates all possible cuts. --- demos/ppl_pips/ppl_pips.cc | 14 ++++++++++---- interfaces/C/ppl_c_header.h | 5 +++++ interfaces/C/ppl_c_implementation_common.cc | 3 +++ src/PIP_Problem.cc | 10 +++++++++- src/PIP_Problem.defs.hh | 2 ++ src/PIP_Tree.cc | 18 ++++++++++++++---- 6 files changed, 43 insertions(+), 9 deletions(-) diff --git a/demos/ppl_pips/ppl_pips.cc b/demos/ppl_pips/ppl_pips.cc index d7d191c..95668c0 100644 --- a/demos/ppl_pips/ppl_pips.cc +++ b/demos/ppl_pips/ppl_pips.cc @@ -436,6 +436,7 @@ struct option long_options[] = { #endif {"first", no_argument, 0, 'f'}, {"deepest", no_argument, 0, 'd'}, + {"all", no_argument, 0, 'a'}, {0, 0, 0, 0} }; #endif @@ -461,6 +462,7 @@ static const char* usage_string "\nCut generation options:\n" " -f, --first use the first non-integer row (default)\n" " -d, --deepest try to generate the deepest cut\n" +" -a, --all always generate all possible cuts\n" #ifndef PPL_HAVE_GETOPT_H "\n" "NOTE: this version does not support long options.\n" @@ -469,9 +471,9 @@ static const char* usage_string "Report bugs to <ppl-devel@cs.unipr.it>.\n"; #if defined(USE_PPL) -#define OPTION_LETTERS "R:ho:Pptvi:Vc:df" +#define OPTION_LETTERS "R:ho:Pptvi:Vc:fda" #else -#define OPTION_LETTERS "R:ho:Pptvi:df" +#define OPTION_LETTERS "R:ho:Pptvi:fda" #endif const char* program_name = 0; @@ -668,12 +670,16 @@ process_options(int argc, char* argv[]) { #endif + case 'f': + cutting_strategy = PPL::PIP_Problem::CUTTING_STRATEGY_FIRST; + break; + case 'd': cutting_strategy = PPL::PIP_Problem::CUTTING_STRATEGY_DEEPEST; break; - case 'f': - cutting_strategy = PPL::PIP_Problem::CUTTING_STRATEGY_FIRST; + case 'a': + cutting_strategy = PPL::PIP_Problem::CUTTING_STRATEGY_ALL; break; default: diff --git a/interfaces/C/ppl_c_header.h b/interfaces/C/ppl_c_header.h index 1966dce..806b1ea 100644 --- a/interfaces/C/ppl_c_header.h +++ b/interfaces/C/ppl_c_header.h @@ -2358,6 +2358,11 @@ extern int PPL_PIP_PROBLEM_CONTROL_PARAMETER_CUTTING_STRATEGY_FIRST; */ extern int PPL_PIP_PROBLEM_CONTROL_PARAMETER_CUTTING_STRATEGY_DEEPEST; +/*! \relates ppl_PIP_Problem_tag \brief + Code of PIP problem's "all" cutting strategy. +*/ +extern int PPL_PIP_PROBLEM_CONTROL_PARAMETER_CUTTING_STRATEGY_ALL; + /*@}*/ /* Symbolic Constants */ /*! \brief \name Constructors, Assignment and Destructor */ diff --git a/interfaces/C/ppl_c_implementation_common.cc b/interfaces/C/ppl_c_implementation_common.cc index ba7b911..edd583e 100644 --- a/interfaces/C/ppl_c_implementation_common.cc +++ b/interfaces/C/ppl_c_implementation_common.cc @@ -167,6 +167,7 @@ int PPL_PIP_PROBLEM_STATUS_OPTIMIZED; int PPL_PIP_PROBLEM_CONTROL_PARAMETER_NAME_CUTTING_STRATEGY; int PPL_PIP_PROBLEM_CONTROL_PARAMETER_CUTTING_STRATEGY_FIRST; int PPL_PIP_PROBLEM_CONTROL_PARAMETER_CUTTING_STRATEGY_DEEPEST; +int PPL_PIP_PROBLEM_CONTROL_PARAMETER_CUTTING_STRATEGY_ALL; int PPL_OPTIMIZATION_MODE_MINIMIZATION; int PPL_OPTIMIZATION_MODE_MAXIMIZATION; @@ -219,6 +220,8 @@ ppl_initialize(void) try { = PIP_Problem::CUTTING_STRATEGY_FIRST; PPL_PIP_PROBLEM_CONTROL_PARAMETER_CUTTING_STRATEGY_DEEPEST = PIP_Problem::CUTTING_STRATEGY_DEEPEST; + PPL_PIP_PROBLEM_CONTROL_PARAMETER_CUTTING_STRATEGY_ALL + = PIP_Problem::CUTTING_STRATEGY_ALL; PPL_OPTIMIZATION_MODE_MINIMIZATION = MINIMIZATION; PPL_OPTIMIZATION_MODE_MAXIMIZATION = MAXIMIZATION; diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 4fc5607..9fb89e3 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -229,7 +229,8 @@ PPL::PIP_Problem::OK() const { // Test validity of control parameter values. Control_Parameter_Value strategy = control_parameters[CUTTING_STRATEGY]; if (strategy != CUTTING_STRATEGY_FIRST - && strategy != CUTTING_STRATEGY_DEEPEST) { + && strategy != CUTTING_STRATEGY_DEEPEST + && strategy != CUTTING_STRATEGY_ALL) { #ifndef NDEBUG cerr << "Invalid value for the CUTTING_STRATEGY control parameter." << endl; @@ -305,6 +306,9 @@ PPL::PIP_Problem::ascii_dump(std::ostream& s) const { case CUTTING_STRATEGY_DEEPEST: s << "CUTTING_STRATEGY_DEEPEST"; break; + case CUTTING_STRATEGY_ALL: + s << "CUTTING_STRATEGY_ALL"; + break; default: s << "Invalid control parameter value"; } @@ -406,6 +410,8 @@ PPL::PIP_Problem::ascii_load(std::istream& s) { value = CUTTING_STRATEGY_FIRST; if (str == "CUTTING_STRATEGY_DEEPEST") value = CUTTING_STRATEGY_DEEPEST; + if (str == "CUTTING_STRATEGY_ALL") + value = CUTTING_STRATEGY_ALL; else return false; control_parameters[i] = value; @@ -528,6 +534,8 @@ PPL::PIP_Problem::set_control_parameter(Control_Parameter_Value value) { case CUTTING_STRATEGY_FIRST: // Intentionally fall through. case CUTTING_STRATEGY_DEEPEST: + // Intentionally fall through. + case CUTTING_STRATEGY_ALL: control_parameters[CUTTING_STRATEGY] = value; break; default: diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index e98c66a..2dfe292 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -490,6 +490,8 @@ public: CUTTING_STRATEGY_FIRST, //! Choose row which generates the deepest cut CUTTING_STRATEGY_DEEPEST, + //! Always generate all possible cuts + CUTTING_STRATEGY_ALL, //! Number of different enumeration values. CONTROL_PARAMETER_VALUE_SIZE diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 6272b06..23fc4a6 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1802,10 +1802,11 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, best_i = i; } } - i = best_i; + generate_cut(best_i, parameters, context, space_dimension); } else { - assert(cutting_strategy == PIP_Problem::CUTTING_STRATEGY_DEEPEST); + 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); @@ -1815,6 +1816,7 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, dimension_type best_i = n_a_d; dimension_type best_pcount = n_a_d; dimension_type pcount; + std::vector<dimension_type> all_best_is; for (i_ = 0; i_ < num_vars; ++i_) { if (basis[i_]) continue; @@ -1849,14 +1851,22 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, && (best_i == n_a_d || (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; } + if (pcount > 0) + all_best_is.push_back(i); + } + if (cutting_strategy == PIP_Problem::CUTTING_STRATEGY_DEEPEST) + generate_cut(best_i, parameters, context, space_dimension); + 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_dimension); } - i = best_i; } - generate_cut(i, parameters, context, space_dimension); } // if (i__ != n_a_d) } // Main loop of the simplex algorithm