[PPL-devel] Horrible bug? [Was: Re: Compiling PPL under Cygwin?]

[Roberto Bagnara]

Goran Frehse wrote:
> There is one comment on the PPL I have (I'm sorry it's not more
> detailed):
> In a long series of computations I obtained a polyhedron (4 dimensions)
> with both constraints A<D and A>=D. Unfortunately it wasn't possible to
> trace how exactly the polyhedron was created, but it was simply by
> intersections with other polyhedra and adding constraints.
> When minimizing this polyhedron, the proper solution (empty) was
> returned, but the worrying part was this: The emptiness test returned
> false on the original!
> I fixed the problem by using the minimizing versions of all operators.
> Since this also gave me an increase in speed, I've been using these ever
> since.
> 
> I know this is a very vage description, but maybe it helps somehow.

Dear Goran,

from what you say, you have witnessed a spectacular bug somewhere: maybe
in the PPL, maybe in the compiler you are using... who knows.
However, we would be very, very grateful if you could try to reproduce
it or help us to reproduce it.  If it is a bug in the library, it is a
serious one we would definitely like to fix.

You say "When minimizing this polyhedron, the proper solution (empty)
was returned";  how did you force minimization of the polyhedron?

When this possible ambiguity is resolved, I think the problem may be
attacked by

1) going back to the non-minimizing versions of the operators, and
2) using something like the function below instead of the usual
    emptiness test method:

bool my_emptiness_test(const NNC_Polyhedron& ph) {
   bool empty = ph.is_empty();
   if (!empty) {
     NNC_Polyhedron qh = ph;
     // Force minimization: is it that way that you forced minimization?
     (void) qh.generators();
     if (qh.is_empty()) {
       std::cerr << "Emptiness test failure!" << std::endl;
       ph.ascii_dump(std::cerr);
     }
   }
   return empty;
}

Please let us know if there is something we can do to help you reproduce
this bug.  If your code is available we may even try ourselves in case
you are too busy to do it.
Thanks a lot anyway,

      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