Module: ppl/ppl Branch: pip Commit: 3a6efe8316708d58e15c9912ce65ef84df005601 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3a6efe8316708...
Author: François Galea francois.galea@uvsq.fr Date: Fri Nov 13 17:10:40 2009 +0100
Added a control parameter for cut generation strategy.
---
demos/ppl_pips/ppl_pips.cc | 19 ++++++++++++- src/PIP_Problem.cc | 32 ++++++++++++++++++++++- src/PIP_Problem.defs.hh | 1 + src/PIP_Problem.types.hh | 8 ++++++ src/PIP_Tree.cc | 60 ++++++++++++++++++++++++------------------- 5 files changed, 89 insertions(+), 31 deletions(-)
diff --git a/demos/ppl_pips/ppl_pips.cc b/demos/ppl_pips/ppl_pips.cc index b7f7a4e..997df16 100644 --- a/demos/ppl_pips/ppl_pips.cc +++ b/demos/ppl_pips/ppl_pips.cc @@ -105,6 +105,9 @@ ppl_set_GMP_memory_allocation_functions(void) {
namespace {
+PPL::PIP_Problem_Control_Parameter_Value cutting_strategy + = PPL::PIP_CUTTING_STRATEGY_DEEPEST; + void pip_display_sol(std::ostream& out, const Parma_Polyhedra_Library::PIP_Tree pip, @@ -168,6 +171,7 @@ pip_display_sol(std::ostream& out, class PIP_Parser { public: PIP_Parser() : pip() { + pip.set_control_parameter(PPL::PIP_CUTTING_STRATEGY, cutting_strategy); }
virtual ~PIP_Parser() { @@ -459,6 +463,9 @@ static const char* usage_string " -V, --version prints version information to stdout\n" " -cPATH, --check=PATH checks if the result is equal to what is in PATH\n" #endif +"\nCut generation options:\n" +" -d, --deepest try to generate the deepest cut (default)\n" +" -f, --first use the first non-integer row\n" #ifndef PPL_HAVE_GETOPT_H "\n" "NOTE: this version does not support long options.\n" @@ -467,9 +474,9 @@ static const char* usage_string "Report bugs to ppl-devel@cs.unipr.it.\n";
#if defined(USE_PPL) -#define OPTION_LETTERS "R:ho:PptvVc:" +#define OPTION_LETTERS "R:ho:PptvVc:df" #else -#define OPTION_LETTERS "R:ho:Pptv" +#define OPTION_LETTERS "R:ho:Pptvdf" #endif
const char* program_name = 0; @@ -660,6 +667,14 @@ process_options(int argc, char* argv[]) {
#endif
+ case 'd': + cutting_strategy = PPL::PIP_CUTTING_STRATEGY_DEEPEST; + break; + + case 'f': + cutting_strategy = PPL::PIP_CUTTING_STRATEGY_FIRST; + break; + default: abort(); } diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index b495d62..84544d7 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -73,6 +73,7 @@ PPL::PIP_Problem::~PIP_Problem() {
void PPL::PIP_Problem::control_parameters_init() { + control_parameters[PIP_CUTTING_STRATEGY] = PIP_CUTTING_STRATEGY_DEEPEST; }
void @@ -230,6 +231,16 @@ PPL::PIP_Problem::OK() const { }
// Test validity of control parameter values. + PIP_Problem_Control_Parameter_Value strategy + = control_parameters[PIP_CUTTING_STRATEGY]; + if (strategy < PIP_CUTTING_STRATEGY_FIRST + || strategy > PIP_CUTTING_STRATEGY_DEEPEST) { +#ifndef NDEBUG + cerr << "Invalid value for the PIP_CUTTING_STRATEGY control parameter." + << endl; + ascii_dump(cerr); +#endif + }
if (!parameters.OK()) return false; @@ -284,6 +295,12 @@ PPL::PIP_Problem::ascii_dump(std::ostream& s) const { for (dimension_type i=0; i<PIP_PROBLEM_CONTROL_PARAMETER_NAME_SIZE; ++i) { PIP_Problem_Control_Parameter_Value value = control_parameters[i]; switch (value) { + case PIP_CUTTING_STRATEGY_FIRST: + s << "PIP_CUTTING_STRATEGY_FIRST"; + break; + case PIP_CUTTING_STRATEGY_DEEPEST: + s << "PIP_CUTTING_STRATEGY_DEEPEST"; + break; default: s << "Invalid control parameter value"; } @@ -379,8 +396,11 @@ PPL::PIP_Problem::ascii_load(std::istream& s) { if (!(s >> str)) return false; PIP_Problem_Control_Parameter_Value value; - // set of if / else if string comparisons to get the correct value - // else + if (str == "PIP_CUTTING_STRATEGY_FIRST") + value = PIP_CUTTING_STRATEGY_FIRST; + if (str == "PIP_CUTTING_STRATEGY_DEEPEST") + value = PIP_CUTTING_STRATEGY_DEEPEST; + else return false; control_parameters[i] = value; } @@ -501,6 +521,14 @@ void PPL::PIP_Problem::set_control_parameter(PIP_Problem_Control_Parameter_Name n, PIP_Problem_Control_Parameter_Value v) { switch (n) { + case PIP_CUTTING_STRATEGY: + if (v != PIP_CUTTING_STRATEGY_FIRST && v != PIP_CUTTING_STRATEGY_DEEPEST) + throw std::invalid_argument("PPL::PIP_Problem::set_control_parameter" + "(n,v):\ninvalid value for n. " + "Valid choices are " + "PIP_CUTTING_STRATEGY_FIRST or" + "PIP_CUTTING_STRATEGY_DEEPEST."); + break; default: throw std::invalid_argument("PPL::PIP_Problem::set_control_parameter(n,v)" ":\ninvalid value for n."); diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index de455b6..9ff18ee 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -83,6 +83,7 @@ operator<<(std::ostream& s, const PIP_Problem& p); the change of objective function and the change of optimization mode. */ class Parma_Polyhedra_Library::PIP_Problem { + friend class PIP_Solution_Node; public: //! Builds a trivial PIP problem. /*! diff --git a/src/PIP_Problem.types.hh b/src/PIP_Problem.types.hh index 85f1484..b981e3e 100644 --- a/src/PIP_Problem.types.hh +++ b/src/PIP_Problem.types.hh @@ -28,6 +28,9 @@ enum PIP_Problem_Status { //! Possible name values for PIP_Problem control parameters. /*! \ingroup PPL_CXX_interface */ enum PIP_Problem_Control_Parameter_Name { + //! Cutting strategy + PIP_CUTTING_STRATEGY, + /*! Number of different possible values of PIP_Problem_Control_Parameter_Name enumeration. */ PIP_PROBLEM_CONTROL_PARAMETER_NAME_SIZE @@ -36,6 +39,11 @@ enum PIP_Problem_Control_Parameter_Name { //! Possible values for PIP_Problem control parameters. /*! \ingroup PPL_CXX_interface */ enum PIP_Problem_Control_Parameter_Value { + //! Choose the first non-integer row + PIP_CUTTING_STRATEGY_FIRST, + //! Choose row which generates the deepest cut + PIP_CUTTING_STRATEGY_DEEPEST, + /*! Number of different possible values of PIP_Problem_Control_Parameter_Value enumeration. */ PIP_PROBLEM_CONTROL_PARAMETER_VALUE_SIZE diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 98827ed..d7263f4 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -22,6 +22,7 @@ site: http://www.cs.unipr.it/ppl/ . */
#include <ppl-config.h> #include "PIP_Tree.defs.hh" +#include "PIP_Problem.defs.hh"
#include <algorithm>
@@ -1515,36 +1516,41 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, } else { /* The solution is non-integer. We have to generate a cut. */ - - /* Look for row which will generate the "deepest" cut */ - PPL_DIRTY_TEMP_COEFFICIENT(score); - PPL_DIRTY_TEMP_COEFFICIENT(score1); - PPL_DIRTY_TEMP_COEFFICIENT(score2); PPL_DIRTY_TEMP_COEFFICIENT(mod); - Coefficient best = 0; - dimension_type best_i = 0; - for (i_ = 0; i_ < num_rows; ++i_) { - const Row& row_t = tableau.t[i_]; - const Row& row_s = tableau.s[i_]; - score1 = 0; - for (j = 0; j < num_params; ++j) { - mod_assign(mod, row_t[j], d); - if (mod != 0) - score1 += d - mod; - } - score2 = 0; - for (j = 0; j < num_vars; ++j) { - mod_assign(mod, row_s[j], d); - if (mod != 0) - score2 += d - mod; - } - score = score1*score2; - if (score > best) { - best = score; - best_i = i_; + if (problem.control_parameters[PIP_CUTTING_STRATEGY] + == PIP_CUTTING_STRATEGY_FIRST) { + /* Just choose the row corresponding to variable i */ + i = mapping[i]; + } else /* PIP_CUTTING_STRATEGY_DEEPEST */ { + /* Look for the row which will generate the "deepest" cut */ + PPL_DIRTY_TEMP_COEFFICIENT(score); + PPL_DIRTY_TEMP_COEFFICIENT(score1); + PPL_DIRTY_TEMP_COEFFICIENT(score2); + Coefficient best = 0; + dimension_type best_i = 0; + for (i_ = 0; i_ < num_rows; ++i_) { + const Row& row_t = tableau.t[i_]; + const Row& row_s = tableau.s[i_]; + score1 = 0; + for (j = 0; j < num_params; ++j) { + mod_assign(mod, row_t[j], d); + if (mod != 0) + score1 += d - mod; + } + score2 = 0; + for (j = 0; j < num_vars; ++j) { + mod_assign(mod, row_s[j], d); + if (mod != 0) + score2 += d - mod; + } + score = score1*score2; + if (score > best) { + best = score; + best_i = i_; + } } + i = best_i; } - i = best_i;
#ifdef NOISY_PIP std::cout << "Row " << i << " contains non-integer coefficients. "