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;Enea Zaffanella. - 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

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.
Efficient Constraint/Generator Removal from Double Description of Polyhedra / Gianluca Amato;Francesca Scozzari;Enea Zaffanella. - 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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11381/2755505
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact