Tobias Grosser wrote:
@Roberto: Can you give us some hints, what is really expensive and what should we avoid when constructing polyhedrons in the PPL?
You should take into account that many algorithms are exponential in the space dimension, both in space and in time. Additionally, there is no upper bound to the number of constraints and generators a polyhedron can have: so, if your application tends to build complex polyhedra (even if the space dimension is small) you may have problems. On top of all this, the dimensions of the coefficients involved plays a (usually minor) role.
To summarize, do not use general polyhedra without:
1) making sure your application does not generate polyhedra with high dimension or that are very complex in terms of the number of constraints or generators; and/or
2) guard all polyhedra computation with complexity watchdogs.
In our own work, we use a combination of 1 and 2.
Concerning 2) now the PPL can exploit the deterministic timeout facilities offered by the PWL (Parma Watchdog Library, distributed along with the PPL). I will write about that in a few hours. Cheers,
Roberto