[PPL-devel] Feasibility of Octagons in PPL

[Roberto Bagnara]

On 06/17/11 19:42, Ramakrishna Upadrasta wrote:
> 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?

Hmmm... can you please rephrase the question?
I am not sure I understand what you mean.
Cheers,

   Roberto

-- 
Prof. Roberto Bagnara
Applied Formal Methods Laboratory
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it