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