We present an algorithm for the removal of constraints (resp., generators) from a convex polyhedron represented in the Double Description framework. Instead of recomputing the dual representation from scratch, the new algorithm tries to better exploit the information available in the Double Description pair, so as to capitalize on the computational work already done. A preliminary experimental evaluation shows that significant efficiency improvements can be obtained. In particular, a combined algorithm can be defined that dynamically selects whether or not to apply the new algorithm, based on suitable profitability heuristics.
Efficient Constraint/Generator Removal from Double Description of Polyhedra / Gianluca, Amato; Francesca, Scozzari; Zaffanella, Enea. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - 307:(2014), pp. 3-15. (Intervento presentato al convegno Numerical and Symbolic Abstract Domains tenutosi a Munich, Germany nel 10/09/2014) [10.1016/j.entcs.2014.08.002].
Efficient Constraint/Generator Removal from Double Description of Polyhedra
ZAFFANELLA, Enea
2014-01-01
Abstract
We present an algorithm for the removal of constraints (resp., generators) from a convex polyhedron represented in the Double Description framework. Instead of recomputing the dual representation from scratch, the new algorithm tries to better exploit the information available in the Double Description pair, so as to capitalize on the computational work already done. A preliminary experimental evaluation shows that significant efficiency improvements can be obtained. In particular, a combined algorithm can be defined that dynamically selects whether or not to apply the new algorithm, based on suitable profitability heuristics.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
