Efficient Constraint/Generator Removal from Double Description of Polyhedra

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.