Investigating Polyhedra by Oracles; Dr. Matthias Walter (RWTH Aachen)

ABSTRACT: The software IPO is presented which investigates a polyhedron P given by means of an optimization oracle, e.g., a mixed-integer hull and a MIP solver. It detects all equations, can check adjacency of vertices, and compute some facets valid for P in exact arithmetic. The facets are produced in such a way that they are helpful in optimizing a given objective function, using target cuts introduced by Buchheim, Liers, and Oswald in 2008. In contrast to usual convex-hull algorithms which produce the entire description, but run out of resources for small dimensions already, IPO can handle much larger dimensions.