[PPL-devel] [GIT] ppl/ppl(master): A few improvements to PIP_Problem documentation.
Enea Zaffanella
zaffanella at cs.unipr.it
Tue Feb 16 20:07:43 CET 2010
Module: ppl/ppl
Branch: master
Commit: ac846ef3f2f47c8c6f6474331857211b318ad24f
URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ac846ef3f2f47c8c6f6474331857211b318ad24f
Author: Enea Zaffanella <zaffanella at cs.unipr.it>
Date: Tue Feb 16 20:05:36 2010 +0100
A few improvements to PIP_Problem documentation.
---
src/PIP_Problem.cc | 14 +++---
src/PIP_Problem.defs.hh | 106 +++++++++++++++++++++++++----------------------
2 files changed, 64 insertions(+), 56 deletions(-)
diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc
index c91abbb..07248d4 100644
--- a/src/PIP_Problem.cc
+++ b/src/PIP_Problem.cc
@@ -605,17 +605,17 @@ PPL::PIP_Problem::set_control_parameter(Control_Parameter_Value value) {
}
void
-PPL::PIP_Problem::set_big_parameter_dimension(dimension_type x) {
- if (parameters.count(x) == 0)
+PPL::PIP_Problem::set_big_parameter_dimension(dimension_type big_dim) {
+ if (parameters.count(big_dim) == 0)
throw std::invalid_argument("PPL::PIP_Problem::"
- "set_big_parameter_dimension(x):\n"
- "dimension 'x' is not a parameter.");
- if (x < internal_space_dim)
+ "set_big_parameter_dimension(big_dim):\n"
+ "dimension 'big_dim' is not a parameter.");
+ if (big_dim < internal_space_dim)
throw std::invalid_argument("PPL::PIP_Problem::"
- "set_big_parameter_dimension(x):\n"
+ "set_big_parameter_dimension(big_dim):\n"
"only newly-added parameters can be"
"converted into the big parameter.");
- big_parameter_dimension = x;
+ big_parameter_dimension = big_dim;
}
PPL::memory_size_type
diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh
index e7d908b..459a309 100644
--- a/src/PIP_Problem.defs.hh
+++ b/src/PIP_Problem.defs.hh
@@ -51,23 +51,24 @@ operator<<(std::ostream& s, const PIP_Problem& p);
//! A Parametric Integer (linear) Programming problem.
/*! \ingroup PPL_CXX_interface
An object of this class encodes a parametric integer (linear)
- programming problem.
- The PIP problem is specified by providing:
+ programming problem. The PIP problem is specified by providing:
- the dimension of the vector space;
- the subset of those dimensions of the vector space that are
interpreted as integer parameters (the other space dimensions
are interpreted as non-parameter integer variables);
- - the feasible region, by means of a finite set of linear equality
- and (strict or non-strict) inequality constraints involving both
- variables and parameters;
- - optionally, an initial context restricting the definition domain for
- the parameters, by means of a finite set of linear equality and
- (strict or non-strict) inequality constraints involving only
- parameters;
- - optionally, the dimension of a parameter to be considered arbitrarily
- big; such a parameter is called the “big parameter”.
-
- All variables and parameters are considered non-negative integers.
+ - a finite set of linear equality and (strict or non-strict)
+ inequality constraints involving variables and/or parameters;
+ these constraints are used to define:
+ - the <EM>feasible region</EM>, if they involve one or more
+ problem variable (and maybe some parameters);
+ - the <EM>initial context</EM>, if they only involve the
+ parameters;
+ - optionally, the so-called <EM>big parameter</EM>,
+ i.e., a problem parameter to be considered arbitrarily big.
+
+ Note that all problem variables and problem parameters are assumed
+ to take non-negative integer values, so that there is no need
+ to specify non-negativity constraints.
The class provides support for the (incremental) solution of the
PIP problem based on variations of the revised simplex method and
@@ -81,29 +82,31 @@ operator<<(std::ostream& s, const PIP_Problem& p);
As the feasibility and the solution value of a PIP problem depend on the
values of the parameters, the solution is a binary decision tree,
- dividing the context parameter set into subsets. The tree nodes are:
- - decision nodes, encoding one or more linear tests on the parameters;
- if all the tests are true, then the solution is the node's
- “true” child, otherwise the solution is the node's
- “false” child;
- - solution nodes, encoding the solution of the problem in the current
- context subset, where each variable is defined in terms of a linear
- expression of the parameters. Solution nodes also embed an optionally
- not empty set of parameter constraints, meaning if all constraint tests
- are true, the solution is described by the node, otherwise the problem
- is empty.
-
- Concerning the decision nodes, it may happen that a decision node has no
- “false” or “true” child. This means the
- corresponding test leads to an unfeasible solution. In addition, decision
- nodes with two or more linear tests cannot have a “false”
- child.
-
- Both tree node types may also contain the definition of extra parameters
- which are artificially introduced by the solver to keep the solution
- values integer. Such artificial parameters are defined by the integer
- division of a linear expression on the parameters by an integer
- coefficient.
+ dividing the context parameter set into subsets.
+ The tree nodes are of three kinds:
+ - \e Decision nodes.
+ These are internal tree nodes encoding one or more linear tests
+ on the parameters; if all the tests are satisfied, then the solution
+ is the node's \e true child; otherwise, the solution is the node's
+ \e false child;
+ - \e Solution nodes.
+ These are leaf nodes in the tree, encoding the solution of the problem
+ in the current context subset, where each variable is defined in terms
+ of a linear expression of the parameters.
+ Solution nodes also optionally embed a set of parameter constraints:
+ if all these constraints are satisfied, the solution is described by
+ the node, otherwise the problem has no solution.
+
+ It may happen that a decision node has no \e false or \e true child.
+ This means that there is no solution satisfying the corresponding
+ constraints. Decision nodes having two or more linear tests on the
+ parameters cannot have a \e false child.
+
+ Both kinds of tree nodes may also contain the definition of extra
+ parameters which are artificially introduced by the solver to enforce
+ an integral solution. Such artificial parameters are defined by
+ the integer division of a linear expression on the parameters
+ by an integer coefficient.
By exploiting the incremental nature of the solver, it is possible
to reuse part of the computational work already done when solving
@@ -134,12 +137,12 @@ operator<<(std::ostream& s, const PIP_Problem& p);
else
_|_
\endcode
- The \f$\perp\f$ notation, also called “bottom”, denotes
- the lexicographic minimum of an empty set, here meaning the problem is
- infeasible.\n
- Also notice that a new parameter is defined after the first \c else. It
- is only valid inside the block where it is defined, and is used when
- formulating the value of the <tt>{i,j}</tt> vector.
+ The \f$\perp\f$ notation, also called \e bottom, denotes the
+ lexicographic minimum of an empty set, here meaning the problem is
+ unfeasible. Notice that a new parameter is defined after
+ the first \c else. It is only valid inside the block where it is
+ defined, and it is used when formulating the value of the
+ <tt>{i,j}</tt> vector.
\par Context restriction
The above solution is correct in an unrestricted original context,
@@ -271,13 +274,13 @@ operator<<(std::ostream& s, const PIP_Problem& p);
FIXME: different uses of the big parameter.
*/
class Parma_Polyhedra_Library::PIP_Problem {
- friend class PIP_Solution_Node;
public:
//! Builds a trivial PIP problem.
/*!
- A trivial PIP problem requires to minimize the objective function
- \f$0\f$ on a vector space under no constraints and with no parameters:
- the origin of the vector space is an optimal solution.
+ A trivial PIP problem requires to compute the lexicographic minimum
+ on a vector space under no constraints and with no parameters:
+ due to the implicit non-negativity constraints, the origin of the
+ vector space is an optimal solution.
\param dim
The dimension of the vector space enclosing \p *this
@@ -477,8 +480,9 @@ public:
CUTTING_STRATEGY,
//! Pivot row strategy
PIVOT_ROW_STRATEGY,
-
+#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
//! Number of different enumeration values.
+#endif // PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
CONTROL_PARAMETER_NAME_SIZE
};
@@ -496,7 +500,9 @@ public:
//! Choose the row which generates the lexico-maximal pivot column
PIVOT_ROW_STRATEGY_MAX_COLUMN,
+#ifdef PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
//! Number of different enumeration values.
+#endif // PPL_DOXYGEN_INCLUDE_IMPLEMENTATION_DETAILS
CONTROL_PARAMETER_VALUE_SIZE
};
@@ -507,8 +513,8 @@ public:
//! Sets control parameter \p value.
void set_control_parameter(Control_Parameter_Value value);
- //! Sets the dimension for the big parameter
- void set_big_parameter_dimension(dimension_type x);
+ //! Sets the dimension for the big parameter to \p big_dim.
+ void set_big_parameter_dimension(dimension_type big_dim);
/*! \brief
Returns the space dimension for the big parameter.
@@ -581,6 +587,8 @@ private:
if not set.
*/
dimension_type big_parameter_dimension;
+
+ friend class PIP_Solution_Node;
};
namespace std {
More information about the PPL-devel
mailing list