October 2009 - PPL-devel - BUGSENG Mailman

[GIT] ppl/w3ppl(master): Added the online version of BagnaraHZ09CGTA.
by Roberto Bagnara 11 Oct '09

11 Oct '09

Module: ppl/w3ppl Branch: master Commit: 57fed23b89c35e081641fb8c0d533d82aabc2896 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/w3ppl.git;a=commit;h=57fed23b89… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Sun Oct 11 08:09:38 2009 +0200 Added the online version of BagnaraHZ09CGTA. --- htdocs/Documentation/ppl.bib | 3 ++- 1 files changed, 2 insertions(+), 1 deletions(-) diff --git a/htdocs/Documentation/ppl.bib b/htdocs/Documentation/ppl.bib index e3bcf0d..cec9899 100644 --- a/htdocs/Documentation/ppl.bib +++ b/htdocs/Documentation/ppl.bib @@ -876,7 +876,8 @@ Journal = "Computational Geometry: Theory and Applications", Publisher = "Elsevier", Year = 2009, - Note = "To appear", + Note = "To appear in print. Available online at + \url{http://dx.doi.org/10.1016/j.comgeo.2009.09.002}", Abstract = "Deciding whether the union of two convex polyhedra is itself a convex polyhedron is a basic problem in polyhedral computations; having important applications

1 0

[GIT] ppl/ppl(pip): Uncommented C interface code for PIP_Problem assignment .
by Enea Zaffanella 10 Oct '09

10 Oct '09

Module: ppl/ppl Branch: pip Commit: ea3ca40fe59ee37cebe9da2996d46e048447d858 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ea3ca40fe59e… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Sat Oct 10 12:07:01 2009 +0200 Uncommented C interface code for PIP_Problem assignment. --- interfaces/C/ppl_c_implementation_common.cc | 14 +++++++------- 1 files changed, 7 insertions(+), 7 deletions(-) diff --git a/interfaces/C/ppl_c_implementation_common.cc b/interfaces/C/ppl_c_implementation_common.cc index e1201b8..2d5f45d 100644 --- a/interfaces/C/ppl_c_implementation_common.cc +++ b/interfaces/C/ppl_c_implementation_common.cc @@ -2099,7 +2099,7 @@ ppl_new_PIP_Problem_from_space_dimension(ppl_PIP_Problem_t* ppip, return 0; } CATCH_ALL -/* FIXME: Waiting for c++ method for operator=() to be implemented. + int ppl_new_PIP_Problem_from_PIP_Problem(ppl_PIP_Problem_t* dpip, ppl_const_PIP_Problem_t pip) try { @@ -2108,8 +2108,7 @@ ppl_new_PIP_Problem_from_PIP_Problem(ppl_PIP_Problem_t* dpip, return 0; } CATCH_ALL -*/ -/* FIXME: Waiting for c++ method for operator=() to be implemented. + int ppl_assign_PIP_Problem_from_PIP_Problem(ppl_PIP_Problem_t dst, ppl_const_PIP_Problem_t src) try { @@ -2119,13 +2118,14 @@ ppl_assign_PIP_Problem_from_PIP_Problem(ppl_PIP_Problem_t dst, return 0; } CATCH_ALL -*/ + int ppl_delete_PIP_Problem(ppl_const_PIP_Problem_t pip) try { delete to_const(pip); return 0; } CATCH_ALL + int ppl_PIP_Problem_space_dimension(ppl_const_PIP_Problem_t pip, ppl_dimension_type* m) try { @@ -2135,8 +2135,8 @@ ppl_PIP_Problem_space_dimension(ppl_const_PIP_Problem_t pip, CATCH_ALL int -ppl_PIP_Problem_number_of_parameter_space_dimensions(ppl_const_PIP_Problem_t pip, - ppl_dimension_type* m) try { +ppl_PIP_Problem_number_of_parameter_space_dimensions +(ppl_const_PIP_Problem_t pip, ppl_dimension_type* m) try { const PIP_Problem& ppip = *to_const(pip); *m = ppip.parameter_space_dimensions().size(); return 0; @@ -2145,7 +2145,7 @@ CATCH_ALL int ppl_PIP_Problem_parameter_space_dimensions(ppl_const_PIP_Problem_t pip, - ppl_dimension_type ds[]) try { + ppl_dimension_type ds[]) try { const Variables_Set& vars = to_const(pip)->parameter_space_dimensions(); ppl_dimension_type* ds_i = ds; for (Variables_Set::const_iterator v_iter = vars.begin(),

1 0

[GIT] ppl/ppl(pip): More functions for the C interface to the PIP Tree class
by Patricia Hill 10 Oct '09

10 Oct '09

Module: ppl/ppl Branch: pip Commit: 4002ecca8f7a3b0400289e1998f3bb3b068a2c9a URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4002ecca8f7a… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Fri Oct 9 23:25:07 2009 +0100 More functions for the C interface to the PIP Tree class - in particular, corresponding to the PIP_Solution_Node and PIP_Decision_Node C++ methods. Various small bugs fixed in the PIP_Problem C interface code. --- interfaces/C/ppl_c_header.h | 91 ++++++++++++++++++++------- interfaces/C/ppl_c_implementation_common.cc | 59 +++++++++++++++++ 2 files changed, 127 insertions(+), 23 deletions(-) diff --git a/interfaces/C/ppl_c_header.h b/interfaces/C/ppl_c_header.h index 142431c..8d48fbe 100644 --- a/interfaces/C/ppl_c_header.h +++ b/interfaces/C/ppl_c_header.h @@ -2768,7 +2768,7 @@ int ppl_PIP_Problem_solve PPL_PROTO((ppl_const_PIP_Problem_t pip)); /*! \relates ppl_PIP_Problem_tag \brief - Returns a feasible solution for \p *this, if it exists. + Writes to \p pip_tree a solution for \p pip, if it exists. \param pip The PIP problem; @@ -2784,7 +2784,7 @@ ppl_PPL_Problem_solution PPL_PROTO((ppl_const_PIP_Problem_t pip, ppl_const_PIP_Tree_Node_t* pip_tree)); /*! \relates ppl_PIP_Problem_tag \brief - Returns an optimizing solution for \p *this, if it exists. + Writes to \p pip_tree an optimizing solution for \p pip, if it exists. \param pip The PIP problem; @@ -2793,7 +2793,7 @@ ppl_PPL_Problem_solution PPL_PROTO((ppl_const_PIP_Problem_t pip, The PIP tree; \exception std::domain_error - Thrown if \p *this doesn't not have an optimizing point, i.e., + Thrown if \p pip does not not have an optimizing point, i.e., if the PIP problem is unbounded or not satisfiable. */ int @@ -2803,25 +2803,9 @@ PPL_PROTO((ppl_const_PIP_Problem_t pip, /*@}*/ /* Computing the Solution of the PIP_Problem */ -/*! \brief \name Querying/Setting Control Parameters */ -/*@{*/ - -/*! \relates ppl_PIP_Problem_tag \brief - Returns the value of control parameter \p name in problem \p pip. -*/ -int -ppl_PIP_Problem_get_control_parameter -PPL_PROTO((ppl_const_PIP_Problem_t pip, int name)); - -/*! \relates ppl_PIP_Problem_tag \brief - Sets control parameter \p value in problem \p pip. -*/ -int -ppl_PIP_Problem_set_control_parameter -PPL_PROTO((ppl_PIP_Problem_t pip, int value)); - /*! \relates ppl_PIP_Problem_tag \brief - Returns \p this if \p *this is a solution node, 0 otherwise. + Writes to \p dpip_tree the solution node if \p spip_tree is + a solution node, and 0 otherwise. */ int ppl_PIP_Tree_Node_as_solution @@ -2829,7 +2813,8 @@ PPL_PROTO((ppl_const_PIP_Tree_Node_t spip_tree, ppl_const_PIP_Solution_Node_t* dpip_tree)); /*! \relates ppl_PIP_Problem_tag \brief - Returns \p this if \p *this is a decision node, 0 otherwise. + Writes to \p dpip_tree the decision node if \p spip_tree + is a decision node, and 0 otherwise. */ int ppl_PIP_Tree_Node_as_decision @@ -2837,7 +2822,8 @@ PPL_PROTO((ppl_const_PIP_Tree_Node_t spip_tree, ppl_const_PIP_Decision_Node_t* dpip_tree)); /*! \relates ppl_PIP_Problem_tag \brief - Returns the value of control parameter \p name in problem \p pip. + Writes to \p pcs the local system of parameter constraints + at the pip tree node \p pip_tree. */ int ppl_PIP_Tree_Node_get_constraints @@ -2899,6 +2885,61 @@ PPL_PROTO((ppl_const_PIP_Tree_Node_t pip_tree, ppl_dimension_type inserted)); /*! \relates ppl_PIP_Problem_tag \brief + Builds a trivial PIP problem of dimension \p d and writes an + handle to it at address \p pmip. +*/ +int +ppl_new_PIP_Solution_Node PPL_PROTO((ppl_PIP_Solution_Node_t* ppip_sol)); + +/*! \relates ppl_PIP_Problem_tag \brief + Invalidates the handle \p pip_sol: this makes sure the corresponding + resources will eventually be released. +*/ +int +ppl_delete_PIP_Solution_Node PPL_PROTO((ppl_const_PIP_Solution_Node_t pip_sol)); + +/*! \relates ppl_PIP_Problem_tag \brief + Writes to \p le a parametric expression of the values of variable \p v. + + The returned linear expression only involves parameters. + + \param v + the variable which is queried about + + \param pars + a \c std::set of indices of the parameters in the constraints + + \exception std::invalid_argument + Thrown if \p v is dimension-incompatible with \p *this + or if \p v is a parameter. +*/ +int +ppl_PIP_Solution_Node_get_parametric_values +PPL_PROTO((ppl_const_PIP_Solution_Node_t pip_sol, + ppl_dimension_type v, + ppl_dimension_type pars[], + size_t n, + ppl_Linear_Expression_t le)); + + +/*! \relates ppl_PIP_Problem_tag \brief + Invalidates the handle \p pip_dec: this makes sure the corresponding + resources will eventually be released. +*/ +int +ppl_delete_PIP_Decision_Node PPL_PROTO((ppl_const_PIP_Decision_Node_t pip_dec)); + +/*! \relates ppl_PIP_Problem_tag \brief + Writes to \p pip_tree a const pointer to the \p b (true or false) branch + of \p pip_dec. +*/ +int +ppl_PIP_Decision_Node_get_child_node +PPL_PROTO((ppl_const_PIP_Decision_Node_t pip_dec, + int b, + ppl_const_PIP_Tree_Node_t* pip_tree)); + +/*! \relates ppl_PIP_Problem_tag \brief Creates a new artificial parameter corresponding to the constant 0 in a zero-dimensional space; writes a handle for the new artificial parameter at address \p pap. @@ -2942,6 +2983,10 @@ PPL_DECLARE_AND_DOCUMENT_IO_FUNCTIONS(PIP_Problem) PPL_DECLARE_AND_DOCUMENT_IO_FUNCTIONS(PIP_Tree_Node) +PPL_DECLARE_AND_DOCUMENT_IO_FUNCTIONS(PIP_Solution_Node) + +PPL_DECLARE_AND_DOCUMENT_IO_FUNCTIONS(PIP_Decision_Node) + PPL_DECLARE_AND_DOCUMENT_IO_FUNCTIONS(Artificial_Parameter) #include "ppl_c_domains.h" diff --git a/interfaces/C/ppl_c_implementation_common.cc b/interfaces/C/ppl_c_implementation_common.cc index 9ff417c..e1201b8 100644 --- a/interfaces/C/ppl_c_implementation_common.cc +++ b/interfaces/C/ppl_c_implementation_common.cc @@ -2321,6 +2321,65 @@ ppl_PIP_Tree_Node_insert_artificials(ppl_const_PIP_Tree_Node_t pip_tree, CATCH_ALL int +ppl_new_PIP_Solution_Node(ppl_PIP_Solution_Node_t* ppip_sol) try { + *ppip_sol = to_nonconst(new PIP_Solution_Node()); + return 0; +} +CATCH_ALL + +int +ppl_delete_PIP_Solution_Node(ppl_const_PIP_Solution_Node_t pip_sol) try { + delete to_const(pip_sol); + return 0; +} +CATCH_ALL + +int +ppl_PIP_Solution_Node_get_parametric_values + (ppl_const_PIP_Solution_Node_t pip_sol, + ppl_dimension_type v, + ppl_dimension_type pars[], + size_t n, + ppl_const_Linear_Expression_t* le) try { + const PIP_Solution_Node& spip_sol = *to_const(pip_sol); + Variables_Set vars; + for (ppl_dimension_type i = n; i-- > 0; ) + vars.insert(pars[i]); + const Linear_Expression& lle = spip_sol.parametric_values(Variable(v),vars); + *le = to_const(&lle); + return 0; +} +CATCH_ALL + +int +ppl_PIP_Solution_Node_OK(ppl_const_PIP_Solution_Node_t pip_sol) try { + return to_const(pip_sol)->OK() ? 1 : 0; +} +CATCH_ALL + +int +ppl_delete_PIP_Decision_Node(ppl_const_PIP_Decision_Node_t pip_dec) try { + delete to_const(pip_dec); + return 0; +} +CATCH_ALL + +int +ppl_PIP_Decision_Node_OK(ppl_const_PIP_Decision_Node_t pip_dec) try { + return to_const(pip_dec)->OK() ? 1 : 0; +} +CATCH_ALL + +int +ppl_PIP_Decision_Node_get_child_node(ppl_const_PIP_Decision_Node_t pip_dec, + int b, + ppl_const_PIP_Tree_Node_t* pip_tree) try { + *pip_tree = to_const(to_const(pip_dec)->child_node(b)); + return 0; +} +CATCH_ALL + +int ppl_new_Artificial_Parameter(ppl_Artificial_Parameter_t* pap) try { *pap = to_nonconst(new Artificial_Parameter()); return 0;

1 0

[GIT] ppl/ppl(pip): Fixed various bugs in the C interface for PIP_Problem methods.
by Patricia Hill 10 Oct '09

10 Oct '09

Module: ppl/ppl Branch: pip Commit: 2e43b1a4200b1ac07f6ab0f58c5b04edb4782b2f URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2e43b1a4200b… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Fri Oct 9 21:00:56 2009 +0100 Fixed various bugs in the C interface for PIP_Problem methods. --- interfaces/C/ppl_c_header.h | 138 ++++++--------------------- interfaces/C/ppl_c_implementation_common.cc | 46 ++++++++- 2 files changed, 71 insertions(+), 113 deletions(-) diff --git a/interfaces/C/ppl_c_header.h b/interfaces/C/ppl_c_header.h index 85ed99e..142431c 100644 --- a/interfaces/C/ppl_c_header.h +++ b/interfaces/C/ppl_c_header.h @@ -2609,17 +2609,6 @@ ppl_new_PIP_Problem_from_space_dimension PPL_PROTO((ppl_PIP_Problem_t* pmip, ppl_dimension_type d)); /*! \relates ppl_PIP_Problem_tag \brief - Builds an PIP problem of space dimension \p d having feasible region \p cs, - objective function \p le and optimization mode \p m; writes a handle to - it at address \p ppip. -*/ -int -ppl_new_PIP_Problem PPL_PROTO((ppl_PIP_Problem_t* ppip, - ppl_dimension_type d, - ppl_const_Constraint_System_t cs, - ppl_const_Linear_Expression_t le, - int m)); -/*! \relates ppl_PIP_Problem_tag \brief Builds an PIP problem that is a copy of \p pip; writes a handle for the newly created system at address \p ppip. */ @@ -2654,19 +2643,19 @@ ppl_PIP_Problem_space_dimension PPL_PROTO((ppl_const_PIP_Problem_t pip, ppl_dimension_type* m)); /*! \relates ppl_PIP_Problem_tag \brief - Writes to \p m the number of integer space dimensions of \p pip. + Writes to \p m the number of parameter space dimensions of \p pip. */ int -ppl_PIP_Problem_number_of_integer_space_dimensions +ppl_PIP_Problem_number_of_parameter_space_dimensions PPL_PROTO((ppl_const_PIP_Problem_t pip, ppl_dimension_type* m)); /*! \relates ppl_PIP_Problem_tag \brief - Writes in the first positions of the array \p ds all the integer space + Writes in the first positions of the array \p ds all the parameter space dimensions of problem \p pip. If the array is not big enough to hold - all of the integer space dimensions, the behavior is undefined. + all of the parameter space dimensions, the behavior is undefined. */ int -ppl_PIP_Problem_integer_space_dimensions +ppl_PIP_Problem_parameter_space_dimensions PPL_PROTO((ppl_const_PIP_Problem_t pip, ppl_dimension_type ds[])); /*! \relates ppl_PIP_Problem_tag \brief @@ -2685,26 +2674,6 @@ int ppl_PIP_Problem_constraint_at_index PPL_PROTO((ppl_const_PIP_Problem_t pip, ppl_dimension_type i, ppl_const_Constraint_t* pc)); - -/*! \relates ppl_PIP_Problem_tag \brief - Writes a const handle to the linear expression defining the - objective function of the PIP problem \p pip at address \p ple. -*/ -int -ppl_PIP_Problem_objective_function -PPL_PROTO((ppl_const_PIP_Problem_t pip, ppl_const_Linear_Expression_t* ple)); - -/*! \relates ppl_PIP_Problem_tag \brief - Returns the optimization mode of the PIP problem \p pip. -*/ -int -ppl_PIP_Problem_optimization_mode PPL_PROTO((ppl_const_PIP_Problem_t pip)); - -/*! \relates ppl_PIP_Problem_tag \brief - Returns a positive integer if \p pip is well formed, i.e., if it - satisfies all its implementation invariants; returns 0 and perhaps - makes some noise if \p pip is broken. Useful for debugging purposes. -*/ int ppl_PIP_Problem_OK PPL_PROTO((ppl_const_PIP_Problem_t pip)); @@ -2720,12 +2689,34 @@ int ppl_PIP_Problem_clear PPL_PROTO((ppl_PIP_Problem_t pip)); /*! \relates ppl_PIP_Problem_tag \brief - Adds \p d new dimensions to the space enclosing the PIP problem \p pip - and to \p pip itself. + Adds <CODE>m_pip_vars + m_pip_params</CODE> new space dimensions + and embeds the PIP problem \p pip in the new vector space. + + \param pip + + \param pip_vars + The number of space dimensions to add that are interpreted as + PIP problem variables (i.e., non parameters). These are added + \e before adding the \p pip_params parameters. + + \param pip_params + The number of space dimensions to add that are interpreted as + PIP problem parameters. These are added \e after having added the + \p pip_vars problem variables. + + \exception std::length_error + Thrown if adding <CODE>pip_vars + pip_params</CODE> new space + dimensions would cause the vector space to exceed dimension + <CODE>max_space_dimension()</CODE>. + + The new space dimensions will be those having the highest indexes + in the new PIP problem; they are initially unconstrained. */ int ppl_PIP_Problem_add_space_dimensions_and_embed -PPL_PROTO((ppl_PIP_Problem_t pip, ppl_dimension_type d)); +PPL_PROTO((ppl_PIP_Problem_t pip, + ppl_dimension_type pip_vars, + ppl_dimension_type pip_params)); /*! \relates ppl_PIP_Problem_tag \brief Sets the space dimensions that are specified in first \p n positions @@ -2752,20 +2743,6 @@ int ppl_PIP_Problem_add_constraints PPL_PROTO((ppl_PIP_Problem_t pip, ppl_const_Constraint_System_t cs)); -/*! \relates ppl_PIP_Problem_tag \brief - Sets the objective function of the PIP problem \p pip to a copy of \p le. -*/ -int -ppl_PIP_Problem_set_objective_function -PPL_PROTO((ppl_PIP_Problem_t pip, ppl_const_Linear_Expression_t le)); - -/*! \relates ppl_PIP_Problem_tag \brief - Sets the optimization mode of the PIP problem \p pip to \p mode. -*/ -int -ppl_PIP_Problem_set_optimization_mode PPL_PROTO((ppl_PIP_Problem_t pip, - int mode)); - /*@}*/ /* Functions that May Modify the PIP_Problem */ /*! \brief \name Computing the Solution of the PIP_Problem */ @@ -2824,59 +2801,6 @@ ppl_PPL_Problem_optimizing_solution PPL_PROTO((ppl_const_PIP_Problem_t pip, ppl_const_PIP_Tree_Node_t* pip_tree)); -/*! \relates ppl_PIP_Problem_tag \brief - Evaluates the objective function of \p pip on point \p g. - - \param pip - The PIP problem defining the objective function; - - \param g - The generator on which the objective function will be evaluated; - - \param num - Will be assigned the numerator of the objective function value; - - \param den - Will be assigned the denominator of the objective function value; -*/ -int -ppl_PIP_Problem_evaluate_objective_function -PPL_PROTO((ppl_const_PIP_Problem_t pip, ppl_const_Generator_t g, - ppl_Coefficient_t num, ppl_Coefficient_t den)); - -/*! \relates ppl_PIP_Problem_tag \brief - Writes a const handle to a feasible point for the PIP problem \p pip - at address \p pg. -*/ -int -ppl_PIP_Problem_feasible_point PPL_PROTO((ppl_const_PIP_Problem_t pip, - ppl_const_Generator_t* pg)); - -/*! \relates ppl_PIP_Problem_tag \brief - Writes a const handle to an optimizing point for the PIP problem \p pip - at address \p pg. -*/ -int -ppl_PIP_Problem_optimizing_point PPL_PROTO((ppl_const_PIP_Problem_t pip, - ppl_const_Generator_t* pg)); - -/*! \relates ppl_PIP_Problem_tag \brief - Returns the optimal value for \p pip. - - \param pip - The PIP problem; - - \param num - Will be assigned the numerator of the optimal value; - - \param den - Will be assigned the denominator of the optimal value. -*/ -int -ppl_PIP_Problem_optimal_value -PPL_PROTO((ppl_const_PIP_Problem_t pip, - ppl_Coefficient_t num, ppl_Coefficient_t den)); - /*@}*/ /* Computing the Solution of the PIP_Problem */ /*! \brief \name Querying/Setting Control Parameters */ @@ -2968,7 +2892,7 @@ PPL_PROTO((ppl_const_PIP_Tree_Node_t pip_tree, */ int ppl_PIP_Tree_Node_insert_artificials -PPL_PROTO((ppl_const_PIP_Tree_Node_t pip, +PPL_PROTO((ppl_const_PIP_Tree_Node_t pip_tree, ppl_dimension_type ds[], size_t n, ppl_dimension_type space_dim, diff --git a/interfaces/C/ppl_c_implementation_common.cc b/interfaces/C/ppl_c_implementation_common.cc index d5331ee..9ff417c 100644 --- a/interfaces/C/ppl_c_implementation_common.cc +++ b/interfaces/C/ppl_c_implementation_common.cc @@ -2109,12 +2109,6 @@ ppl_new_PIP_Problem_from_PIP_Problem(ppl_PIP_Problem_t* dpip, } CATCH_ALL */ -int -ppl_delete_PIP_Problem(ppl_const_PIP_Problem_t pip) try { - delete to_const(pip); - return 0; -} -CATCH_ALL /* FIXME: Waiting for c++ method for operator=() to be implemented. int ppl_assign_PIP_Problem_from_PIP_Problem(ppl_PIP_Problem_t dst, @@ -2127,6 +2121,12 @@ ppl_assign_PIP_Problem_from_PIP_Problem(ppl_PIP_Problem_t dst, CATCH_ALL */ int +ppl_delete_PIP_Problem(ppl_const_PIP_Problem_t pip) try { + delete to_const(pip); + return 0; +} +CATCH_ALL +int ppl_PIP_Problem_space_dimension(ppl_const_PIP_Problem_t pip, ppl_dimension_type* m) try { *m = to_const(pip)->space_dimension(); @@ -2186,6 +2186,16 @@ ppl_PIP_Problem_clear(ppl_PIP_Problem_t pip) try { } CATCH_ALL int +ppl_PIP_Problem_add_space_dimensions_and_embed(ppl_PIP_Problem_t pip, + ppl_dimension_type pip_vars, + ppl_dimension_type pip_params) + try { + PIP_Problem& spip = *to_nonconst(pip); + spip.add_space_dimensions_and_embed(pip_vars,pip_params); + return 0; +} +CATCH_ALL +int ppl_PIP_Problem_add_constraint(ppl_PIP_Problem_t pip, ppl_const_Constraint_t c) try { const Constraint& cc = *to_const(c); @@ -2287,6 +2297,30 @@ ppl_PIP_Tree_Node_begin(ppl_const_PIP_Tree_Node_t pip_tree, CATCH_ALL int +ppl_PIP_Tree_Node_end(ppl_const_PIP_Tree_Node_t pip_tree, + ppl_Artificial_Parameter_Sequence_const_iterator_t pit) try { + PIP_Tree_Node::Artificial_Parameter_Sequence::const_iterator& spit + = *to_nonconst(pit); + spit = to_const(pip_tree)->art_parameter_end(); + return 0; +} +CATCH_ALL +int +ppl_PIP_Tree_Node_insert_artificials(ppl_const_PIP_Tree_Node_t pip_tree, + ppl_dimension_type ds[], + size_t n, + ppl_dimension_type space_dim, + ppl_dimension_type inserted) try { + const PIP_Tree_Node& spip_tree = *to_const(pip_tree); + Variables_Set vars; + for (ppl_dimension_type i = n; i-- > 0; ) + vars.insert(ds[i]); + inserted = spip_tree.insert_artificials(vars,space_dim); + return 0; +} +CATCH_ALL + +int ppl_new_Artificial_Parameter(ppl_Artificial_Parameter_t* pap) try { *pap = to_nonconst(new Artificial_Parameter()); return 0;

1 0

[GIT] ppl/ppl(pip): Improved best pivot row selection heuristic.
by François Galea 09 Oct '09

09 Oct '09

Module: ppl/ppl Branch: pip Commit: 9a9a350ade225d3d28b848da2caa4ccb63a8e0d0 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9a9a350ade22… Author: François Galea <francois.galea(a)uvsq.fr> Date: Fri Oct 9 17:57:18 2009 +0200 Improved best pivot row selection heuristic. --- src/PIP_Tree.cc | 18 ++++++++++++++++++ 1 files changed, 18 insertions(+), 0 deletions(-) diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index f52221b..7a470dd 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -1150,6 +1150,24 @@ PIP_Solution_Node::solve(PIP_Tree_Node*& parent_ref, const Matrix& ctx, std::cout << "Adding tautology: " << *c << std::endl; #endif } else { + /* Heuristically choose "best" pivoting row. */ + Coefficient score; + Coefficient best = 0; + dimension_type best_i = n_a_d; + for (i = i__; i < num_rows; ++i) { + if (sign[i] != MIXED) + continue; + const Row& row = tableau.t[i]; + score = 0; + for (j = 0; j < num_params; ++j) + score += row[j]; + if (best_i == n_a_d || score < best) { + best = score; + best_i = i; + } + } + i__ = best_i; + #ifdef NOISY_PIP { using namespace IO_Operators;

1 0

[GIT] ppl/ppl(pip): Added several C functions for PIP_Tree_Node and Artificial_Parameter*.
by Patricia Hill 09 Oct '09

09 Oct '09

Module: ppl/ppl Branch: pip Commit: 0d54e9631e1c6359d641e05bc7589f140ddf7962 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0d54e9631e1c… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Fri Oct 9 13:02:12 2009 +0100 Added several C functions for PIP_Tree_Node and Artificial_Parameter*. --- interfaces/C/ppl_c_header.h | 110 +++++++++++++++++++- interfaces/C/ppl_c_implementation_common.cc | 86 ++++++++++++++-- .../C/ppl_c_implementation_common.inlines.hh | 14 +++ 3 files changed, 200 insertions(+), 10 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=0d54e963…

1 0

[GIT] ppl/ppl(pip): Added the c interface for as_decision() and as_solution ().
by Patricia Hill 09 Oct '09

09 Oct '09

Module: ppl/ppl Branch: pip Commit: 50e259b4f41c623bdc490f3f2c2616b9c45eece2 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=50e259b4f41c… Author: Patricia Hill <p.m.hill(a)leeds.ac.uk> Date: Thu Oct 8 20:52:56 2009 +0100 Added the c interface for as_decision() and as_solution(). --- interfaces/C/ppl_c_header.h | 26 +++++++++++++------ interfaces/C/ppl_c_implementation_common.cc | 15 +++++++++++ .../C/ppl_c_implementation_common.inlines.hh | 4 +++ 3 files changed, 37 insertions(+), 8 deletions(-) diff --git a/interfaces/C/ppl_c_header.h b/interfaces/C/ppl_c_header.h index 4dd294b..d187ba6 100644 --- a/interfaces/C/ppl_c_header.h +++ b/interfaces/C/ppl_c_header.h @@ -695,6 +695,8 @@ PPL_TYPE_DECLARATION(MIP_Problem) */ PPL_TYPE_DECLARATION(PIP_Problem) PPL_TYPE_DECLARATION(PIP_Tree_Node) +PPL_TYPE_DECLARATION(PIP_Decision_Node) +PPL_TYPE_DECLARATION(PIP_Solution_Node) #undef PPL_DECLARE_PRINT_FUNCTIONS @@ -2319,11 +2321,6 @@ extern int PPL_MIP_PROBLEM_CONTROL_PARAMETER_PRICING_STEEPEST_EDGE_FLOAT; extern int PPL_PIP_PROBLEM_STATUS_UNFEASIBLE; /*! \relates ppl_PIP_Problem_tag \brief - Code of the "unbounded PIP problem" status. -*/ -extern int PPL_PIP_PROBLEM_STATUS_UNBOUNDED; - -/*! \relates ppl_PIP_Problem_tag \brief Code of the "optimized PIP problem" status. */ extern int PPL_PIP_PROBLEM_STATUS_OPTIMIZED; @@ -2785,9 +2782,6 @@ ppl_PIP_Problem_is_satisfiable PPL_PROTO((ppl_const_PIP_Problem_t pip)); \return <CODE>PPL_PIP_PROBLEM_STATUS_UNFEASIBLE</CODE> if the PIP problem is not satisfiable; - <CODE>PPL_PIP_PROBLEM_STATUS_UNBOUNDED</CODE> if the PIP problem - is satisfiable but there is no finite bound to the value of - the objective function; <CODE>PPL_PIP_PROBLEM_STATUS_OPTIMIZED</CODE> if the PIP problem admits an optimal solution. */ @@ -2900,6 +2894,22 @@ int ppl_PIP_Problem_set_control_parameter PPL_PROTO((ppl_PIP_Problem_t pip, int value)); +/*! \relates ppl_PIP_Problem_tag \brief + Returns \p this if \p *this is a solution node, 0 otherwise. +*/ +int +ppl_PIP_Problem_as_solution +PPL_PROTO((ppl_const_PIP_Tree_Node_t spip_tree, + ppl_const_PIP_Solution_Node_t* dpip_tree)); + +/*! \relates ppl_PIP_Problem_tag \brief + Returns \p this if \p *this is a decision node, 0 otherwise. +*/ +int +ppl_PIP_Problem_as_decision +PPL_PROTO((ppl_const_PIP_Tree_Node_t spip_tree, + ppl_const_PIP_Decision_Node_t* dpip_tree)); + /*@}*/ /* Querying/Setting Control Parameters */ PPL_DECLARE_AND_DOCUMENT_IO_FUNCTIONS(MIP_Problem) diff --git a/interfaces/C/ppl_c_implementation_common.cc b/interfaces/C/ppl_c_implementation_common.cc index 73a1816..b7da61c 100644 --- a/interfaces/C/ppl_c_implementation_common.cc +++ b/interfaces/C/ppl_c_implementation_common.cc @@ -2237,6 +2237,21 @@ ppl_PIP_Problem_OK(ppl_const_PIP_Problem_t pip) try { } CATCH_ALL +int +ppl_PIP_Problem_as_solution(ppl_const_PIP_Tree_Node_t spip_tree, + ppl_const_PIP_Solution_Node_t* dpip_tree) try { + *dpip_tree = to_const(to_const(spip_tree)->as_solution()); + return 0; +} +CATCH_ALL + +int +ppl_PIP_Problem_as_decision(ppl_const_PIP_Tree_Node_t spip_tree, + ppl_const_PIP_Decision_Node_t* dpip_tree) try { + *dpip_tree = to_const(to_const(spip_tree)->as_decision()); + return 0; +} +CATCH_ALL int ppl_io_print_variable(ppl_dimension_type var) try { diff --git a/interfaces/C/ppl_c_implementation_common.inlines.hh b/interfaces/C/ppl_c_implementation_common.inlines.hh index 2065879..178be80 100644 --- a/interfaces/C/ppl_c_implementation_common.inlines.hh +++ b/interfaces/C/ppl_c_implementation_common.inlines.hh @@ -81,6 +81,10 @@ DECLARE_CONVERSIONS(PIP_Problem, PIP_Problem) DECLARE_CONVERSIONS(PIP_Tree_Node, PIP_Tree_Node) +DECLARE_CONVERSIONS(PIP_Decision_Node, PIP_Decision_Node) + +DECLARE_CONVERSIONS(PIP_Solution_Node, PIP_Solution_Node) + inline Relation_Symbol relation_symbol(enum ppl_enum_Constraint_Type t) { switch (t) {

1 0

[GIT] ppl/ppl(pip): Fixed memory managment issue in copy constructor of PIP_Problem.
by François Galea 09 Oct '09

09 Oct '09

Module: ppl/ppl Branch: pip Commit: a4c21dff11473d99be2152f65e1d09a7a0319527 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a4c21dff1147… Author: François Galea <francois.galea(a)uvsq.fr> Date: Fri Oct 9 13:08:37 2009 +0200 Fixed memory managment issue in copy constructor of PIP_Problem. --- src/PIP_Problem.cc | 7 +++---- src/PIP_Tree.cc | 31 +++++++++++++++++++++++++++++++ src/PIP_Tree.defs.hh | 12 ++++++++++++ tests/PIP_Problem/pipproblem1.cc | 10 ++++++---- 4 files changed, 52 insertions(+), 8 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 494d7f9..f2fb1c3 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -53,16 +53,15 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y) : external_space_dim(y.external_space_dim), internal_space_dim(y.internal_space_dim), status(y.status), - // FIXME: this causes sharing of the solution tree, - // possibly later resulting in memory corruption (double free). - current_solution(y.current_solution), + current_solution(0), initialized(y.initialized), input_cs(y.input_cs), first_pending_constraint(y.first_pending_constraint), parameters(y.parameters), initial_context(y.initial_context) { + if (y.current_solution != 0) + current_solution = y.current_solution->clone(); PPL_ASSERT(OK()); - // FIXME: must also copy the solution tree } PPL::PIP_Problem::~PIP_Problem() { diff --git a/src/PIP_Tree.cc b/src/PIP_Tree.cc index b4c208e..f52221b 100644 --- a/src/PIP_Tree.cc +++ b/src/PIP_Tree.cc @@ -210,6 +210,16 @@ PIP_Decision_Node::PIP_Decision_Node(PIP_Tree_Node* fcp, false_child(fcp) { } +PIP_Decision_Node ::PIP_Decision_Node(const PIP_Decision_Node& x) + : PIP_Tree_Node(x), + true_child(0), + false_child(0) { + if (x.true_child != 0) + true_child = x.true_child->clone(); + if (x.false_child != 0) + false_child = x.false_child->clone(); +} + const PIP_Solution_Node* PIP_Tree_Node::as_solution() const { return 0; @@ -511,6 +521,27 @@ PIP_Tree_Node::ascii_load(std::istream& s) { return true; } +PIP_Tree_Node* +PIP_Tree_Node::clone() const { + const PIP_Solution_Node* as_s = as_solution(); + if (as_s != 0) + return as_s->clone(); + const PIP_Decision_Node* as_d = as_decision(); + if (as_d != 0) + return as_d->clone(); + return 0; +} + +PIP_Solution_Node* +PIP_Solution_Node::clone() const { + return new PIP_Solution_Node(*this); +} + +PIP_Decision_Node* +PIP_Decision_Node::clone() const { + return new PIP_Decision_Node(*this); +} + void PIP_Solution_Node::Tableau::ascii_dump(std::ostream& st) const { st << "denominator " << denominator << "\n"; diff --git a/src/PIP_Tree.defs.hh b/src/PIP_Tree.defs.hh index e4a7e8b..4141818 100644 --- a/src/PIP_Tree.defs.hh +++ b/src/PIP_Tree.defs.hh @@ -120,6 +120,9 @@ public: void ascii_dump(std::ostream& s) const; bool ascii_load(std::istream& s); + //! Returns a pointer to a dynamically-allocated copy of \p *this. + PIP_Tree_Node* clone() const; + protected: //! Default constructor. PIP_Tree_Node(); @@ -228,6 +231,9 @@ public: void ascii_dump(std::ostream& s) const; bool ascii_load(std::istream& s); + //! Returns a pointer to a dynamically-allocated copy of \p *this. + PIP_Solution_Node* clone() const; + bool OK() const; private: @@ -415,6 +421,9 @@ public: //! Returns a pointer to the \p v (true or false) branch of \p *this. PIP_Tree_Node* child_node(bool v); + //! Returns a pointer to a dynamically-allocated copy of \p *this. + PIP_Decision_Node* clone() const; + bool OK() const; private: @@ -446,6 +455,9 @@ private: PIP_Decision_Node(PIP_Tree_Node* fcp, PIP_Tree_Node* tcp); protected: + //! Copy constructor. + PIP_Decision_Node(const PIP_Decision_Node &x); + /*! \brief Populates the parametric simplex tableau using external data, if necessary diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index 394a127..191727c 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -189,11 +189,14 @@ test04() { cs.space_dimension()); } - // Copy constructor is buggy. + // Copy constructor is no longer buggy. { PIP_Problem pip_copy = pip; // Here we call the destructor of pip_copy - // and we also destroy the (shared) solution tree of pip. + // and we also destroy the (copied) solution tree of pip_copy. + const PIP_Tree solution = pip_copy.solution(); + display_solution(solution, params, Variables_Set(i, j), + cs.space_dimension()); } return ok; @@ -205,6 +208,5 @@ BEGIN_MAIN DO_TEST(test01); DO_TEST(test02); DO_TEST(test03); - // Uncomment this to get a segmentation fault. - // DO_TEST(test04); + DO_TEST(test04); END_MAIN

1 0

[GIT] ppl/ppl(pip): Added call to the solver to check problem satisfiability.
by François Galea 09 Oct '09

09 Oct '09

Module: ppl/ppl Branch: pip Commit: 3aedf16a94add5e6e493936b77aa6bee869074d5 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3aedf16a94ad… Author: François Galea <francois.galea(a)uvsq.fr> Date: Fri Oct 9 13:07:15 2009 +0200 Added call to the solver to check problem satisfiability. --- src/PIP_Problem.cc | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index 350f065..494d7f9 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -419,5 +419,7 @@ PPL::PIP_Problem::add_constraints(const Constraint_System &cs) { bool PPL::PIP_Problem::is_satisfiable() const { + if (status == PARTIALLY_SATISFIABLE) + solve(); return status == OPTIMIZED; }

1 0

[GIT] ppl/ppl(pip): Added implementations for PIP_Problem swap and operator = methods.
by Enea Zaffanella 08 Oct '09

08 Oct '09

Module: ppl/ppl Branch: pip Commit: d5889e252f39916812471f4bf2da15d624accf00 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d5889e252f39… Author: Enea Zaffanella <zaffanella(a)cs.unipr.it> Date: Thu Oct 8 20:41:16 2009 +0200 Added implementations for PIP_Problem swap and operator= methods. Added a few consistency checks in method OK(). Pointed out a resource management bug in copy constructor that can result in memory corruption. Added test04() to pipproblem1.cc (currently commented out) showing that a segmentation fault can be obtained when copying a PIP_Problem object having a non-null solution tree. --- src/PIP_Problem.cc | 54 ++++++++++++++++++++++++++++++++++++- src/PIP_Problem.defs.hh | 2 +- src/PIP_Problem.inlines.hh | 20 ++++++++++++++ tests/PIP_Problem/pipproblem1.cc | 36 +++++++++++++++++++++++++ 4 files changed, 109 insertions(+), 3 deletions(-) diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index ffb093e..350f065 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -53,6 +53,8 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y) : external_space_dim(y.external_space_dim), internal_space_dim(y.internal_space_dim), status(y.status), + // FIXME: this causes sharing of the solution tree, + // possibly later resulting in memory corruption (double free). current_solution(y.current_solution), initialized(y.initialized), input_cs(y.input_cs), @@ -60,7 +62,7 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y) parameters(y.parameters), initial_context(y.initial_context) { PPL_ASSERT(OK()); - //FIXME: must also copy the solution tree + // FIXME: must also copy the solution tree } PPL::PIP_Problem::~PIP_Problem() { @@ -164,7 +166,55 @@ PPL::PIP_Problem::optimizing_solution() const { bool PPL::PIP_Problem::OK() const { - //FIXME +#ifndef NDEBUG + using std::endl; + using std::cerr; +#endif + + if (external_space_dim < internal_space_dim) { +#ifndef NDEBUG + cerr << "The internal space dimension of the PIP_Problem is " + << "greater than its external space dimension." + << endl; + ascii_dump(cerr); +#endif + return false; + } + + // Constraint system should be OK. + const dimension_type input_cs_num_rows = input_cs.size(); + for (dimension_type i = input_cs_num_rows; i-- > 0; ) + if (!input_cs[i].OK()) + return false; + + // Constraint system should contain no strict inequalities. + for (dimension_type i = input_cs_num_rows; i-- > 0; ) { + if (input_cs[i].is_strict_inequality()) { +#ifndef NDEBUG + cerr << "The feasible region of the PIP_Problem is defined by " + << "a constraint system containing strict inequalities." + << endl; + ascii_dump(cerr); +#endif + return false; + } + if (input_cs[i].space_dimension() > external_space_dim) { +#ifndef NDEBUG + cerr << "The space dimension of the PIP_Problem is smaller than " + << "the space dimension of one of its constraints." + << endl; + ascii_dump(cerr); +#endif + return false; + } + } + + if (!parameters.OK()) + return false; + if (!initial_context.OK()) + return false; + + // All checks passed. return true; } diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index beb291b..0096879 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -307,7 +307,7 @@ private: Status status; //! The current solution decision tree - PIP_Tree_Node *current_solution; + PIP_Tree_Node* current_solution; /*! \brief A Boolean encoding whether or not internal data structures have diff --git a/src/PIP_Problem.inlines.hh b/src/PIP_Problem.inlines.hh index 44cbc94..61fe0a8 100644 --- a/src/PIP_Problem.inlines.hh +++ b/src/PIP_Problem.inlines.hh @@ -50,6 +50,26 @@ PIP_Problem::parameter_space_dimensions() const { return parameters; } +inline void +PIP_Problem::swap(PIP_Problem& y) { + std::swap(external_space_dim, y.external_space_dim); + std::swap(internal_space_dim, y.internal_space_dim); + std::swap(status, y.status); + std::swap(current_solution, y.current_solution); + std::swap(initialized, y.initialized); + std::swap(input_cs, y.input_cs); + std::swap(first_pending_constraint, y.first_pending_constraint); + std::swap(parameters, y.parameters); + std::swap(initial_context, y.initial_context); +} + +inline PIP_Problem& +PIP_Problem::operator=(const PIP_Problem& y) { + PIP_Problem tmp(y); + swap(tmp); + return *this; +} + } // namespace Parma_Polyhedra_Library namespace std { diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index bcd76f8..394a127 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -165,10 +165,46 @@ test03() { return ok; } +bool +test04() { + Variable i(0); + Variable j(1); + Variable k(2); + Variable m(3); + Variable n(4); + Variables_Set params(k, n); + + Constraint_System cs; + cs.insert(i <= m); + cs.insert(j <= n); + cs.insert(2*i+j <= 2*m+n-k); + cs.insert(2*i+j >= 2*m+n-k); + + PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + display_solution(solution, params, Variables_Set(i, j), + cs.space_dimension()); + } + + // Copy constructor is buggy. + { + PIP_Problem pip_copy = pip; + // Here we call the destructor of pip_copy + // and we also destroy the (shared) solution tree of pip. + } + + return ok; +} + } // namespace BEGIN_MAIN DO_TEST(test01); DO_TEST(test02); DO_TEST(test03); + // Uncomment this to get a segmentation fault. + // DO_TEST(test04); END_MAIN

1 0