Feasibility of Octagons in PPL
Hello All,
I would like to know if there is any feasibility test developed specifically of octagons in PPL. I am looking for a solution to the following problem: given a set of octagonal constraints, determine if the system is empty or not.
If so, what are its details (method followed, complexity etc.)?
Thanks Ramakrishna
On 06/17/11 18:03, Ramakrishna Upadrasta wrote:
Hello All,
Hi Ramakrishna.
I would like to know if there is any feasibility test developed specifically of octagons in PPL. I am looking for a solution to the following problem: given a set of octagonal constraints, determine if the system is empty or not.
http://www.cs.unipr.it/ppl/Documentation/user/ppl-user-0.11.2-html/classParm...
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. Cheers,
Roberto
Hi Roberto,
Thanks a lot for the quick reply. I have another question:
2011/6/17 Roberto Bagnara bagnara@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
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 Bagnarabagnara@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
participants (2)
-
Ramakrishna Upadrasta -
Roberto Bagnara