[PPL-devel] [GIT] ppl/ppl(pip): Added a control parameter for cut generation strategy.
François Galea
francois.galea at uvsq.fr
Fri Nov 13 17:23:57 CET 2009
Module: ppl/ppl
Branch: pip
Commit: 3a6efe8316708d58e15c9912ce65ef84df005601
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3a6efe8316708d58e15c9912ce65ef84df005601
Author: François Galea <francois.galea at 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 at 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. "
More information about the PPL-devel
mailing list