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

[Roberto Bagnara]

-------- 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 at andrew.cmu.edu>
To: 'Roberto Bagnara' <bagnara at 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 at 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

-- 
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



-- 
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