November 2009 - PPL-devel - BUGSENG Mailman

Problems with test suite on alpha
by Michael Tautschnig 09 Sep '10

09 Sep '10

Hi PPL developers, I've reported problems with some test cases because of suspected gcc bugs on alpha earlier already. Now it seems that even more test cases are broken, most probably because of the very same bug (I suspect it to be http://gcc.gnu.org/bugzilla/show_bug.cgi?id=8966). My question now is: How to proceed? Shall I specifically disable the failing test cases by surrounding them with an #ifndef __alpha__ or disable the entire test suite on alpha? Thanks, Michael

2 6

Windows, Java interface
by Krzysztof Jakubczyk 30 Dec '09

30 Dec '09

Hi, I've managed to compile PPL to a windows dll along with java interface using MinGW. I will describe how I achieved this step by step. First thing was to build the ppl library (not java interface) to a dll. I found out that to do this AC_LIBTOOL_WIN32_DLL must be added to autoconf along with '-no-undefined' to LDFLAGS (see http://sourceware.org/autobook/autobook/autobook_254.html ). I also based this on gmp's autoconf file. Patch is available in attached patch.configure.ac file (running autoconf is needed to create configure file). To compile ppl to a dll you need to run configure with parameters: "--disable-static --enable-shared". I didn't manage to compile ppl dll to use static gmp library version. I compiled gmp as a shared library (configure --enable-cxx --disable-static --enable-shared). Unfortunately make check fails when gmp is compiled like this - but it seems the library works ok. After compiling gmp I made copy of libgmp.dll.a as libgmp.a and libgmpxx.dll.a to libgmpxx.a so that PPL can be linked to it (possibly there is another solution). Later I had to compile the Java library (add --enable-interfaces=java, to configure arguments). I had some problems with configuring java path (--with-java=DIR) this is because I use the 64 bit windows system - java is installed in "C:\Program Files (x86)\Java\jdk1.6.0_17". (i passed --with-java="/c/Program Files (x86)/Java/jdk1.6.0_17") I had to manually update makefiles for java interface because javah was not properly found, includes were not properly generated (there was "-I/c/Program Files (x86)/Java/jdk1.6.0_17/include/mingw" instead of "-I/c/Program Files (x86)/Java/jdk1.6.0_17/include/win32") and had manually fix java directory issues (add "'s). Another important thing was to modify Makefile for the jni dll file (interfaces/Java/jni) (see http://www.mingw.org/node/41 ) - add " -D_JNI_IMPLEMENTATION_ -Wl,--kill-at" flags to libppl_java_la_LDFLAGS. After these modifications the dll was successfully build. PS. Also I'm not sure when the jni compilation flags should be added (gcc and windows machines?) and I'm not autoconf expert - this hopefully could be automatized. regards, Krzysztof Jakubczyk

2 1

[GIT] ppl/ppl(pip): Improved the documentation of the PIP solver.
by François Galea 30 Nov '09

30 Nov '09

Module: ppl/ppl Branch: pip Commit: 4394384f20722ac901f4b934780238580eae1767 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4394384f2072… Author: François Galea <francois.galea(a)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 {

1 0

[GIT] ppl/ppl(pip): Simplified the solution tree exploration method.
by François Galea 30 Nov '09

30 Nov '09

Module: ppl/ppl Branch: pip Commit: 031a0a56e158d2bf0c8f96d8f55d90b56c265776 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=031a0a56e158… Author: François Galea <francois.galea(a)uvsq.fr> Date: Mon Nov 30 15:31:58 2009 +0100 Simplified the solution tree exploration method. Including, the PIP_Tree_Node::insert_artificials method has been removed. --- demos/ppl_pips/ppl_pips.cc | 19 +++------ interfaces/C/ppl_c_header.h | 39 +------------------- interfaces/C/ppl_c_implementation_common.cc | 22 +---------- interfaces/C/tests/pip_test.c | 14 +++---- src/PIP_Tree.cc | 19 +++++++-- src/PIP_Tree.defs.hh | 54 +++++++++++++-------------- tests/PIP_Problem/pipproblem1.cc | 19 +++------ 7 files changed, 62 insertions(+), 124 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=031a0a56…

1 0

[GIT] ppl/ppl(floating_point): Fixed a typo.
by Fabio Biselli 29 Nov '09

29 Nov '09

Module: ppl/ppl Branch: floating_point Commit: bb5e95b8994a0e00073fb55fe6ccab4f88d03492 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=bb5e95b8994a… Author: Fabio Biselli <fabio.biselli(a)studenti.unipr.it> Date: Sun Nov 29 18:22:21 2009 +0100 Fixed a typo. --- tests/Floating_Point_Expression/Makefile.am | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/tests/Floating_Point_Expression/Makefile.am b/tests/Floating_Point_Expression/Makefile.am index 1ed83d4..3bdf297 100644 --- a/tests/Floating_Point_Expression/Makefile.am +++ b/tests/Floating_Point_Expression/Makefile.am @@ -132,7 +132,7 @@ print_INSTANCES: # Sources for the tests # -reatelimiter_SOURCES = ratelimiter.cc +ratelimiter_SOURCES = ratelimiter.cc digitalfilters1_SOURCES = digitalfilters1.cc

1 0

[GIT] ppl/ppl(floating_point): Added a rate limiter test that pass without intersection between
by Fabio Biselli 29 Nov '09

29 Nov '09

Module: ppl/ppl Branch: floating_point Commit: c8e299d57c031c5ddbe4212980867b3d805f5319 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c8e299d57c03… Author: Fabio Biselli <fabio.biselli(a)studenti.unipr.it> Date: Sun Nov 29 18:04:16 2009 +0100 Added a rate limiter test that pass without intersection between the two domain. --- tests/Floating_Point_Expression/Makefile.am | 5 +- tests/Floating_Point_Expression/ratelimiter.cc | 197 ++++++++++++++++++++++++ 2 files changed, 201 insertions(+), 1 deletions(-) diff --git a/tests/Floating_Point_Expression/Makefile.am b/tests/Floating_Point_Expression/Makefile.am index e1ecc84..1ed83d4 100644 --- a/tests/Floating_Point_Expression/Makefile.am +++ b/tests/Floating_Point_Expression/Makefile.am @@ -51,7 +51,8 @@ $(top_builddir)/src/libppl.la \ @extra_libraries@ ORIGINAL_TESTS = \ -digitalfilters1 +digitalfilters1 \ +ratelimiter #bdshape2 \ #bdshape1 \ @@ -131,6 +132,8 @@ print_INSTANCES: # Sources for the tests # +reatelimiter_SOURCES = ratelimiter.cc + digitalfilters1_SOURCES = digitalfilters1.cc #bdshape2_SOURCES = bdshape2.cc diff --git a/tests/Floating_Point_Expression/ratelimiter.cc b/tests/Floating_Point_Expression/ratelimiter.cc new file mode 100644 index 0000000..4b9034f --- /dev/null +++ b/tests/Floating_Point_Expression/ratelimiter.cc @@ -0,0 +1,197 @@ +/* Test Rate Limiter on differents abstract domains. + Copyright (C) 2001-2009 Roberto Bagnara <bagnara(a)cs.unipr.it> + +This file is part of the Parma Polyhedra Library (PPL). + +The PPL is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3 of the License, or (at your +option) any later version. + +The PPL is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software Foundation, +Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA. + +For the most up-to-date information see the Parma Polyhedra Library +site: http://www.cs.unipr.it/ppl/ . */ + +#include "ppl_test.hh" + +namespace { + +using namespace Parma_Polyhedra_Library::IO_Operators; + +/* +This file tests a rate limiter that, given random input flows of floating +point values X and D, bounded respectively by [-128, 128] and [0, 16], +computes an output flow Y that tries to follow X while having a change rate +limited by D. The pseudo-code of such rate limiter is the following: + +Y = 0; +for (n = 0; n < N; ++n) { + X = [-128, 128]; + D = [0, 16]; + S = Y; + R = X - S; + Y = X; + if (R <= -D) + Y = S - D; + if (R >= D) + Y = S + D; +} +*/ + +// Tests rate limiter using octagons abstract domain. +bool +test01() { + // Input signal. + Variable X(0); + // Maximum allowed for |R|. + Variable D(1); + // Output signal. + Variable Y(2); + // Last output. + Variable S(3); + // Actual rate. + Variable R(4); + + FP_Interval_Abstract_Store abstract_store(5); + FP_Interval_Abstract_Store as_begin(5); + FP_Linear_Form_Abstract_Store lf_abstract_store; + FP_Octagonal_Shape oc(5); + FP_Octagonal_Shape oc_begin(5); + FP_Interval y(0); + FP_Interval y_begin(1); + FP_Interval tmp(0); + FP_Linear_Form lx; + FP_Linear_Form ly; + FP_Linear_Form lr; + FP_Linear_Form lk; + FP_Linear_Form ls; + + // M represents the threshold: the smallest integer larger than + // M0 computed in Miné's thèse + PPL_DIRTY_TEMP_COEFFICIENT(M); + assign_r(M, 145, ROUND_DOWN); + + Constraint_System cs; + cs.insert(Y <= M); + cs.insert(Y >= -M); + + Con_FP_Expression con_y(0, 0); + // The constant floating point expression con_y is linearized into + // the interval linear form lk. + con_y.linearize(abstract_store, lf_abstract_store, lk); + // Here we model the assignment Y = 0, invoking affine_image method. + // FIXME: In order to refine the analysis, all the transer function are + // performed in parallel in the interval domain and in the octagon + // domain. + // Then, we consider the intersection between these abstract domains. + oc.affine_image(Y, lk); + Box<FP_Interval> box(oc); + + // This loop iterate until the value of Y reaches a fixed point. + for(unsigned short n = 0; y_begin != y; ++n) { + + // Iteration no. n+1: the abstract domains and the value of Y + // are saved into the corresponding variables. + nout << "*** n = " << n << " ***" << endl; + oc_begin = oc; + y_begin = y; + print_constraints(Box<FP_Interval>(oc), "*** before loop ***"); + + // X = [-128, 128]. + Con_FP_Expression con_x(-128, 128); + con_x.linearize(abstract_store, lf_abstract_store, lk); + oc.affine_image(X, lk); + + // D = [0, 16]. + Con_FP_Expression con_d(0, 16); + con_d.linearize(abstract_store, lf_abstract_store, lk); + oc.affine_image(D, lk); + + // S = Y. + Var_FP_Expression var_y(Y.id()); + var_y.linearize(abstract_store, lf_abstract_store, ly); + var_y.linearize(abstract_store, lf_abstract_store, ls); + oc.affine_image(S, ly); + + // R = X - S. + Var_FP_Expression* px = new Var_FP_Expression(X.id()); + Var_FP_Expression* ps = new Var_FP_Expression(S.id()); + Dif_FP_Expression x_dif_s(px, ps); + x_dif_s.linearize(abstract_store, lf_abstract_store, lr); + oc.affine_image(R, lr); + + // Y = X. + Var_FP_Expression var_x(X.id()); + var_x.linearize(abstract_store, lf_abstract_store, lx); + oc.affine_image(Y, lx); + + + // if (R <= -D). + FP_Octagonal_Shape oc_then(oc); + oc_then.refine_with_linear_form_inequality(lr, -lk); + + // then Y = S - D. + Var_FP_Expression* pd = new Var_FP_Expression(D.id()); + Var_FP_Expression* ps2 = new Var_FP_Expression(S.id()); + Dif_FP_Expression s_dif_d(ps2, pd); + s_dif_d.linearize(abstract_store, lf_abstract_store, ly); + // Y <= S holds. + oc_then.refine_with_linear_form_inequality(ly, ls); + oc_then.affine_image(Y, ly); + // else skip. + oc.refine_with_linear_form_inequality(-lk, lr); + + // LUB between then and else branches. + oc.upper_bound_assign(oc_then); + print_constraints(Box<FP_Interval>(oc), + "*** after if (R <= -D) Y = S - D; ***"); + + // if (R >= D). + oc_then = oc; + oc_then.refine_with_linear_form_inequality(lk, lr); + // then Y = S + D. + Var_FP_Expression* pd1 = new Var_FP_Expression(D.id()); + Var_FP_Expression* ps3 = new Var_FP_Expression(S.id()); + Sum_FP_Expression s_sum_d(ps3, pd1); + s_sum_d.linearize(abstract_store, lf_abstract_store, ly); + // -S <= Y holds. + oc_then.refine_with_linear_form_inequality(-ls, ly); + oc_then.affine_image(Y, ly); + + // else skip. + oc.refine_with_linear_form_inequality(lr, lk); + + // LUB between then and else branches. + oc.upper_bound_assign(oc_then); + print_constraints(Box<FP_Interval>(oc), + "*** after if (R >= D) Y = S + D; ***"); + + // LUB between the actual abstract domains and the corresponding + // domains at the beginning of the loop. + oc.upper_bound_assign(oc_begin); + + // Limited extrapolation: we enforce the satisfaction + // of the constraint system cs = {Y <= N; Y >= -N} + oc.limited_BHMZ05_extrapolation_assign(oc_begin, cs); + box = Box<FP_Interval>(oc); + print_constraints(box,"*** end loop ***"); + y = box.get_interval(Y); + } + + nout << "*** Y in " << y << " ***" << endl; + return y.is_bounded(); +} + +} // namespace + +BEGIN_MAIN + DO_TEST(test01); +END_MAIN

1 0

[GIT] ppl/ppl(floating_point): Improved tests on rate limiter. They all pass now.
by Roberto Amadini 28 Nov '09

28 Nov '09

Module: ppl/ppl Branch: floating_point Commit: dc2ec7594e5d208c181a87260840add74b6ff972 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=dc2ec7594e5d… Author: Roberto Amadini <r.amadini(a)virgilio.it> Date: Sat Nov 28 18:05:06 2009 +0100 Improved tests on rate limiter. They all pass now. --- tests/Floating_Point_Expression/digitalfilters1.cc | 443 ++++++++++++++------ 1 files changed, 325 insertions(+), 118 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=dc2ec759…

1 0

[GIT] ppl/ppl(pip): Modified the documentation of the PIP_Problem class.
by François Galea 27 Nov '09

27 Nov '09

Module: ppl/ppl Branch: pip Commit: f9022a7ee764af85090f790bb738641c58dc9249 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f9022a7ee764… Author: François Galea <francois.galea(a)uvsq.fr> Date: Fri Nov 27 16:39:59 2009 +0100 Modified the documentation of the PIP_Problem class. --- src/PIP_Problem.defs.hh | 153 ++++++++++++++++++++++++++++++++++++++++++---- 1 files changed, 139 insertions(+), 14 deletions(-) diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index 3668569..d080e3c 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -54,34 +54,159 @@ operator<<(std::ostream& s, const PIP_Problem& p); programming problem. The PIP problem is specified by providing: - the dimension of the vector space; - - the feasible region, by means of a finite set of linear equality - and (strict or non-strict) inequality constraints; - 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”. - // FIXME: should the non-negativity constraints be assumed? - // If that is the case, the problem will always be either - // unfeasible or optimizable (since the origin of the vector - // space is the minimum for the unconstrained non-negative problem). - - - the optimization mode (either maximization or minimization). + All variables and parameters are considered non-negative integers. The class provides support for the (incremental) solution of the PIP problem based on variations of the revised simplex method and - on branch-and-bound techniques. The result of the resolution - process is expressed in terms of an enumeration, encoding the - feasibility and the unboundedness of the optimization problem. - The class supports simple feasibility tests (i.e., no optimization), - as well as the extraction of an optimal (resp., feasible) point, - provided the PIP_Problem is optimizable (resp., feasible). + on Gomory cut generation techniques. + + The solution for a PIP problem is the lexicographic minimum of the + integer points of the feasible region, expressed in terms of the + parameters. As the problem to be solved only involves non-negative + variables and parameters, the problem will always be either unfeasible + or optimizable. + + 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. + + 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. By exploiting the incremental nature of the solver, it is possible to reuse part of the computational work already done when solving variants of a given PIP_Problem: currently, incremental resolution supports the addition of space dimensions, the addition of constraints, the change of objective function and the change of optimization mode. + + \par Example problem + An example PIP problem can be defined the following: + \code + 3*j >= -2*i+8 + j <= 4*i - 4 + i <= n + j <= m + \endcode + where \c i and \c j are variables, and \c n and \c m are parameters. + The resulting solution tree is: + \code + if 7*n >= 10 then + if 7*m >= 12 then + {i = 2 ; j = 2} + else + New Parameter P = (m) div 2 + if 2*n + 3*m >= 8 then + {i = -m - P + 4 ; j = m} + else + _|_ + 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. + + \par Context restriction + The above solution is correct in an unrestricted original context, + meaning all possible values are allowed for the parameters. If we + restrict the context with the following parameter inequalities: + \code + m >= n + n >= 5 + \endcode + then the result will simply be: + \code + {i = 2 ; j = 2} + \endcode + + \par Problem object creation + The PIP_Problem object correspondind to the above example problem can be + created like follows: + \code + Variable i(0); + Variable j(1); + Variable n(2); + Variable m(3); + Variables_Set params(n, m); + Constraint_System cs; + cs.insert(3*j >= -2*i+8); + cs.insert(j <= 4*i - 4); + cs.insert(j <= m); + cs.insert(i <= n); + PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); + \endcode + If you want to restrict the original context, simply add the parameter + constraints the same way as for normal constraints. + \code + cs.insert(m >= n); + cs.insert(n >= 5); + \endcode + + \par Problem solving + Once a PIP_Problem object has been created, you can start the + resolution of the problem by calling the solve() method: + \code + PIP_Problem_Status status; + status = pip.solve(); + \endcode + where the returned \c status indicates if the problem has been optimized + or if it is unfeasible for any possible configuration of the parameter + values. + + \par Solution tree spanning + Retrieve the optimized 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: + \code + const PIP_Solution_Node* sol = node->as_solution(); + 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. */ + class Parma_Polyhedra_Library::PIP_Problem { friend class PIP_Solution_Node; public:

1 0

[GIT] ppl/ppl(pip): Fixed a regression.
by François Galea 27 Nov '09

27 Nov '09

Module: ppl/ppl Branch: pip Commit: 3e53583567375b62f1496c262334691f51a716df URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3e5358356737… Author: François Galea <francois.galea(a)uvsq.fr> Date: Fri Nov 27 08:10:18 2009 +0100 Fixed a regression. --- src/PIP_Tree.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index 139df97..72e1d1e 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1270,7 +1270,7 @@ PIP_Solution_Node::update_tableau(const PIP_Problem& problem, ++v; } } - if (row_sign(var, 0) != ZERO) { + if (row_sign(var, not_a_dimension()) != ZERO) { /* parametric-only constraints have already been inserted in initial context, so no need to insert them in the tableau */

1 0

[GIT] ppl/ppl(pip): Test test10() in pipproblem2. cc seems to show another bug.
by Enea Zaffanella 26 Nov '09

26 Nov '09

Module: ppl/ppl Branch: pip Commit: 05f65d328f6e2e1a0b9819f84fbe966e4a516002 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=05f65d328f6e… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Nov 26 14:42:56 2009 +0100 Test test10() in pipproblem2.cc seems to show another bug. --- tests/PIP_Problem/pipproblem2.cc | 13 +++++++++++++ 1 files changed, 13 insertions(+), 0 deletions(-) diff --git a/tests/PIP_Problem/pipproblem2.cc b/tests/PIP_Problem/pipproblem2.cc index 51e21e1..590f672 100644 --- a/tests/PIP_Problem/pipproblem2.cc +++ b/tests/PIP_Problem/pipproblem2.cc @@ -184,6 +184,18 @@ test09() { return ok; } +bool +test10() { + Variable A(0); + Constraint_System cs; + cs.insert(A >= 5); + + PIP_Problem pip1(3, cs.begin(), cs.end(), Variables_Set()); + bool ok = (pip1.solve() == OPTIMIZED_PIP_PROBLEM); + + return ok; +} + } // namespace BEGIN_MAIN @@ -196,4 +208,5 @@ BEGIN_MAIN DO_TEST(test07); DO_TEST(test08); DO_TEST(test09); + DO_TEST(test10); END_MAIN

1 0