FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
A Direct Encoding for NNC Polyhedra

Authors: Anna Becchi and Enea Zaffanella

Paper Information

Title:A Direct Encoding for NNC Polyhedra
Authors:Anna Becchi and Enea Zaffanella
Proceedings:CAV All Papers
Editors: Georg Weissenbacher, Hana Chockler and Igor Konnov
Keywords:convex polyhedra, Double Description method, strict inequalities, conversion algorithm
Abstract:

ABSTRACT. We present an alternative Double Description representation for the domain of NNC (not necessarily closed) polyhedra, together with the corresponding Chernikova-like conversion procedure. The representation uses no slack variable at all and provides a solution to a few technical issues caused by the encoding of an NNC polyhedron as a closed polyhedron in a higher dimension space. A preliminary experimental evaluation shows that the new conversion algorithm is able to achieve significant efficiency improvements.

Pages:18
Talk:Jul 14 15:15 (Session 98A: Polyhedra)
Paper: