[PPL-devel] a newbie question

[Roberto Bagnara]

Jie Ouyang wrote:
> Sorry for this newbie question. I have a simple program as following
> 
> :-ensure_loaded('ppl_sicstus.pl').
> main :-
>         ppl_initialize,
>         A='$VAR'(0),
>         B='$VAR'(1),
>         C='$VAR'(2),
>         ppl_new_Polyhedron_from_constraints(nnc,[A=0,B=C],H1),
>         ppl_new_Polyhedron_from_constraints(nnc,[A=1,B=C-1],H2),
>         ppl_Polyhedron_poly_hull_assign_and_minimize(H2,H1),
>         ppl_Polyhedron_get_constraints(H2,Cs),
>         write(Cs),
>         ppl_finalize.
> 
> The output is [-1*B+1*C>=0,1*B+ -1*C>= -1,1*A+1*B+ -1*C=0]. Although the
> first two constraints are equivalent to A>=0 and A<=1, I am wondering if
> there is a way to get the answer in the form [1*A>=0, -1*A>=-1, 1*A+1*B+
> -1*C=0] instead of the previous one. 
> 
> cheers,
> 
> Jie Ouyang

Dear Jie,

if your question is "does the PPL provide methods to transform systems
of constraints/generators into equivalent systems that I find pleasant?",
then the answer is "no, you can only obtain a minimized system, if you want".
The reason is that there is no universal notion of "pleasant".  For example,
if you try using the clp(Q) module of SICStus, you will obtain yet another
equivalent system of constraints:

| ?- {-1*B+1*C>=0,1*B+ -1*C>= -1,1*A+1*B+ -1*C=0}.
{A= -(B)+C},
{B-C=<0},
{B-C>= -1} ?
yes
| ?-

You will also have noticed that, in the PPL's Prolog interface,
we generate the term -1*B+1*C >= 0 instead of -B+C >= 0.  The
reason we refrain from performing this simple "embellishment"
is that we would simply make the user's life a bit more difficult,.
Since the user will have to write the code manipulating these
constraints anyway (whether to print them or not), it is better
to leave the unit coefficients there rather then removing them
forcing the user to deal with special cases.

If, instead, you are looking for systems of constraints/generators
possessing a well-defined set of properties, then you can of course
program the transformation algorithm using the PPL.  If what you have
in mind is something of truly general use, we might consider adding
support for it in the library itself but, generally speaking, this
kind of things tend to belong to user code.  An exception is constituted
by canonical or almost canonical forms, since they have interesting
applications (even though they also come with non-negligible drawbacks).
An example is given by orthogonal forms: your system of constraint can
be expressed in orthogonal form as

   A + B - C = 0, 2*A - B + C >= 0, -2*A + B - C >= -3.

This has the property that, besides being minimal, all the hyperplanes
defining the inequalities are orthogonal to the hyperplanes defining
the equalities.  This form is unlikely to be pleasant to the user's eyes,
but it is useful for some applications.  We plan to add support for it
in a future release (the code is already there: we simply have to agree
on the right interface).
All the best,

     Roberto

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it