[PPL-devel] Feasibility of Octagons in PPL

[Ramakrishna Upadrasta]

Hi Roberto,

Thanks a lot for the quick reply. I have another question:



2011/6/17 Roberto Bagnara <bagnara at cs.unipr.it>:
>
>> If so, what are its details (method followed, complexity etc.)?
>
> It is basically a transitive closure, cubic in the worst case in the
> number of dimensions of the octagonal shape.


Suppose I have a 5000 variable system which is relatively sparse.
Standard LP solvers can perhaps solve the system in reasonably fast
time. Doesn't computing closure on the system mean that the system
becomes quite dense and large, making it quite difficult to solve,
even if calculating the closure means that the feasibility comes
almost for free?


Regards
Ramakrishna