[PPL-devel] integer versus rational solutions

[Roberto Bagnara]

Michael Claßen wrote:
> On Mon, Jul 13, 2009 at 1:11 PM, Tobias
> Grosser<grosser at fim.uni-passau.de> wrote:
> 
>> If I got your comments right, you warned that adding large constants
>> like MAX_INT might be bad for compile time performance. That is
>> something I did not understand and as adding the constraint to the
>> context improves the code generated by CLooG, I would like to keep
>> adding these constraints as long as compile time allows.
> 
> from my experience, large constants can influence the complexity of
> many algorithms (e.g. Fourier-Motzkin) in the polytope model, because
> of the simple fact that at some points, the algorithm has to compute
> the lowest common denominator (LCD) of entries in matrices. Now, if
> you combine that with the fact that sometimes you have expressions
> like "constant-1" or "constant+1", those LCDs can get extremely big,
> which makes the usage of GMP almost unavoidable and slows down
> computation a lot. It also might increase memory usage too.
> 
> Also, larger constants create more cases where inequalities are not
> redundant, whereas small constants like 0, 1, 2 often create cases
> that can be simply ignored because they are already expressed by other
> inequalities.
> 
> I hope I haven't missed the point here, but this is just how I have
> experienced the problem so far when working with FM and other
> algorithms on polytopes containing large constants (as they often
> result from using our tiling technique in LooPo).
> 
> If anyone has any approach to how to deal with this specific problem,
> I would be very interested to hear about it!

Is approximation acceptable in your application?  There are techniques
to compute an upward approximation of a given polyhedron (i.e., a
polyhedron containing the given one) so as to limit the number of
bits of the coefficients.

The idea, due to Goran Frehse, is the following: for each constraint
do:

0) start, e.g., with

      109*x + 121*y <= 100;

1) truncate homogeneous coefficients to, e.g.,
    3 bits, obtaining

        6*x +   6*y <= ?;

2) solve an LP problem to push out the plane, obtaining:

        6*x +   6*y <= 600/109;

3) approximate the inhomogeneous coefficient to next integer,
    obtaining

        6*x +   6*y <= 6.

So the cost is one LP problem per constraint.  Whether
it is worthwhile or not depends on the application.

With Goran we have a plan to implement this and other techniques
in the PPL.  If this may be useful to you, we may increase the
priority of the job.
Cheers,

    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