[PPL-devel] [GIT] ppl/ppl(pip): Improved the documentation of the PIP solver.

[François Galea]

Module: ppl/ppl
Branch: pip
Commit: 4394384f20722ac901f4b934780238580eae1767
URL:    http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4394384f20722ac901f4b934780238580eae1767

Author: François Galea <francois.galea at uvsq.fr>
Date:   Mon Nov 30 17:08:59 2009 +0100

Improved the documentation of the PIP solver.

---

 src/PIP_Problem.defs.hh |   86 +++++++++++++++++++++++++++++++++++++++++------
 1 files changed, 75 insertions(+), 11 deletions(-)

diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh
index d080e3c..e6768bb 100644
--- a/src/PIP_Problem.defs.hh
+++ b/src/PIP_Problem.defs.hh
@@ -88,7 +88,10 @@ operator<<(std::ostream& s, const PIP_Problem& p);
      “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.
+     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
@@ -186,25 +189,86 @@ operator<<(std::ostream& s, const PIP_Problem& p);
   values.
 
   \par Solution tree spanning
-  Retrieve the optimized decision tree:
+  Retrieve the optimized solution decision tree:
   \code
   const PIP_Tree_Node* node = solution();
   \endcode
   If the pointer designates a \f$\perp\f$ solution (infeasible), its value
   is \c 0.\n
-  FIXME: insert_artificials()
-
   To check whether a non-null tree node pointer designates a solution or a
-  decision node, you can call the as_decision() and as_solution() virtual
-  methods:
+  decision node, you can call the PIP_Tree_Node::as_decision() and
+  PIP_Tree_Node::as_solution() virtual methods:
   \code
   const PIP_Solution_Node* sol = node->as_solution();
-  const PIP_Decision_Node* dec = node->as_decision();
+  if (sol != 0) {
+    // The node is a solution node
+    ...
+  }
+  else {
+    // The node is a decision node
+    const PIP_Decision_Node* dec = node->as_decision();
+    ...
+  }
   \endcode
-  Exactly one of the \c sol and \c dec pointers will be \c 0. Then the
-  node type is of the kind of the non-null pointer.\n
-  FIXME: list of decision node tests, get true and false children
-  FIXME: list expressions of variables.
+
+  \par
+  To access the two child nodes of a Decision Node, use the
+  PIP_Tree_Node::child_node(bool) method, using \b true or \b false as an
+  argument to access the child node you want.
+
+  \par Artificial parameters
+  The expression of an artificial parameter is stored in an
+  PIP_Tree_Node::Artificial_Parameter object, which encodes the integer
+  division of a Linear_Expression (only expressed in terms of the other
+  parameters, including the previously-defined artificials) by a
+  denominator Coefficient.
+  To get the effective value of an artificial parameter, just divide the
+  result of the Linear_Expression applied to the effective values of the
+  other parameters by the value of the denominator.
+  The dimensions of the artificial parameters in a node can be computed as
+  <tt>dim</tt>, <tt>dim+1</tt>, ... where <tt>dim</tt>'s value is computed
+  the following way:
+   - for the root node \c dim is the maximum space dimension of the
+     original problem, plus one.
+   - for any other node of the tree, it is the sum of the \c dim value
+     computed for the parent node, plus the total number of artificial
+     parameters in the parent node.
+  \par
+  The definition of artificial parameters' dimension values always follow
+  this rule. If you choose to add a new variable or parameter on a problem
+  which already has a solution (incremental solving), all artificial
+  parameters in the solution will have their dimension values incremented.
+
+  \par Node constraints
+  All node types can embed parameter-only constraints. Decision nodes
+  contain at least one of them. You can access the node's constraints set
+  using the PIP_Tree_Node::constraints() method.
+  The signification of the node constraints is the following:
+   - On a decision node, if all tests in the constraints are true, then the
+     solution is the “true” child; otherwise it is the
+     “false” child. If the number of constraints is greater than
+     one, the “false” child is always infeasible.
+   - On a solution node, if the constraint set is empty or all tests in the
+     constraints are true, then the solution is described by the node;
+     otherwise the solution is \f$\perp\f$ (infeasible problem).
+  \par
+  Node constraints always are defined in terms of the parameters, including
+  those from the original problem and any of the artificial parameters
+  defined in nodes which belong to the path from the root to the concerned
+  node.
+
+  \par Getting the optimal values for the variables
+  Once having spanned the solution tree using the actual values of the
+  parameters, and having ended at a solution node, you can fetch the
+  parametric expression of any of the variables using the
+  PIP_Solution_Node::parametric_values() method.
+  \par
+  Variable expressions always are defined in terms of the parameters,
+  including those from the original problem and any of the artificial
+  parameters defined in nodes which belong to the path from the root to the
+  concerned node.
+
+  FIXME: different uses of the big parameter.
 */
 
 class Parma_Polyhedra_Library::PIP_Problem {