-------- Original Message -------- Subject: RE: Horrible bug? [Was: Re: Compiling PPL under Cygwin?] Date: Tue, 23 Mar 2004 14:26:12 -0500 From: Goran Frehse gfrehse@andrew.cmu.edu To: 'Roberto Bagnara' bagnara@cs.unipr.it

Dear Roberto,

I had a feeling that you might be interested in the bug, but it only occurred in the process of one specific example after many thousands of iterations. I was not able to isolate the source, and creating the same polyhedron by adding the constraints one by one resulted in the correct empty polyhedron. Once I'm past my current workload, I'll be happy to include your test and see if I can find any strange things happening.

I minimized the polyhedron using "mypoly.minimized_constraints()". Afterwards "mypoly" would be the proper solution. This I found strange, since minimized_constraints() is declared "const", so shouldn't it leave mypoly unchanged?

Is there any reason against using the minimizing versions? Like I said, it speeded things up for me by about 50%, as far as I can remember, even though the polyhedra mostly were only generated once, checked for intersection, and then forgotten. The speedup should be even greater when the polyhedra are used several times for computations.

Best wishes, Goran

-----Original Message----- From: Roberto Bagnara [mailto:bagnara@cs.unipr.it] Sent: 23 March 2004 14:04 To: Goran Frehse Cc: The Parma Polyhedra Library developers' list Subject: Horrible bug? [Was: Re: Compiling PPL under Cygwin?]

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