This is Enea.

Home

Personal Info

Research

Papers

Teaching

About

Efficient Constraint/Generator Removal from Double Description of Polyhedra (NSAD'14)

[Page last updated on "August 15, 2017, 11:59:48".]

Gianluca Amato, Francesca Scozzari and Enea Zaffanella

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.


Available: ScienceDirect, BibTeX entry.
© Enea Zaffanella
enea.zaffanella@unipr.it

| Home | Personal Info | Research | Papers | Teaching | About