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