[PPL-devel] integer versus rational solutions

[Roberto Bagnara]

Konrad Trifunovic wrote:
> indeed, when changed to C_Polyhedron this example was solved quickly.
> It made me think that changing all the polyhedrons to C_Polyhedron would
> solve the problems, unfortunately I have found some other examples that take
> a long time, even when being expressed as C_Polyhedrons. Stay tuned, I will send
> an examples.

Hi All.

I propose we start from the very beginning.

The first thing I would like to do is to solve the communication problem.
There must be a communication problem because it is only by chance that
I discovered gcc-graphite at googlegroups.com and that, on it, people
was discussing about problems they have with the PPL.  The same happened
already at least a couple of times on the gcc mailing lists: people had
troubles using the PPL and they did not mail ppl-devel at cs.unipr.it.
However, we made it very clear that we have a 100% determination to support
all our users, GCC and Graphite in particular.  So, please, do talk with
us as soon as what appears to be a problem shows up.  Even better: please
let us know in advance what you plan to do with the PPL and how.  Believe
me: we can help.

Now, the complexity problems.  I am not sure I understand what you are trying
to accomplish, but it seems to me that you call for the solution of (pure or
mixed) integer programming problems.  As integer programming is NP-complete
(and very tough also in practical terms), there is no way you can obtain
efficiency _unless_ the problems you are trying to solve have a peculiar
structure and you use algorithms that are able to exploit it.  Concerning
the PPL, MIP problems are solved using a textbook implementation of
branch-and-bound, which, in turn, uses a textbook implementation of primal
simplex.  Branch-and-bound is not even guaranteed to terminate and can
generate zillions of subproblems.  So the only sensible way to use it is
by either:

a) ensuring the problem is small enough and solvable by branch-and-bound;
    and/or

b) guarding the computation with a time threshold and a memory threshold
    (the PPL provides support for both).

A possibility to obtain a better performance would be to use the PPL/GLPK
interface.  This is already available in the `simplex' branch of the main
PPL Git repository.  The reason we do not merge this with `master' is that
until now we failed to convince the GLPK people to move the bignum simplex
interface to the installed glpk.h: that interface is currently only available
by using an header file that is not installed.  Note that this would not
substantially transform your problem: you will have to set time/memory
threshold anyway.
All the best,

    Roberto

P.S. Concerning point (b) above, we are installing in the main Git repository
      mechanisms to impose (deterministic) limits to the computation performed
      by expensive PPL computation (including those that take place in MIP_Problem).

P.S. I have checked that the issue I mentioned witth respect to GLPK is still
      present in the latest version (4.38).  There was also another issue with it,
      but I have no time right now to check if this is still present: even
      in the bignum simplex solver, GLPK was making unsafe approximations
      in order to keep the coefficients small.  Perhaps this is no longer
      the case.

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