[PPL-devel] [GIT] ppl/ppl(pip): Added a more aggressive cutting strategy which generates all possible cuts .
François Galea
francois.galea at uvsq.fr
Mon Jan 4 18:54:34 CET 2010
Module: ppl/ppl
Branch: pip
Commit: 37b1e615b392957dbf9a03cdfa0afc24afca7368
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=37b1e615b392957dbf9a03cdfa0afc24afca7368
Author: François Galea <francois.galea at 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 at 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
More information about the PPL-devel
mailing list