IPO is a software library for certain problems in polyhedral combinatorics such as computing the affine hull, checking adjacency, or computing facets. In contrast to other tools, it only requires the polyhedra to be given implicitly by means of so-called optimization oracles.
In mathematical optimization, it is common to encode certain combinatorial objects (e.g., routes, schedules, decisions) as points in the Euclidean space and consider their convex hulls, which are usually polyhedra. Using this approach, properties concerning the facial structures of these polyhedra become of central interest. In general, classical enumeration-based algorithms investigating such properties turn out to be impractical already for small dimensions, e.g., n=20.
On the other hand, maximizing linear objective functions over these polyhedra (though most often NP-hard) can be done very efficiently for moderate sizes (say n=100), e.g., by mixed-integer programming solvers. IPO uses such optimization oracles and (partially) solves some of the problems mentioned above. For this it utilizes the LP solver SoPlex, in particular its ability to compute solutions in exact arithmetic.
Given an optimization oracle defining a polyhedron P, IPO can...
IPO's requirements for an optimization oracle are very simple:
IPO is implemented in C++ and uses exact arithmetic. It depends on the LP solver SoPlex. In order to implement an optimization oracle, there are some base classes from which one must inherit:
For mixed-integer programs, several oracles are already implemented:
IPO comes with a tool that use SCIP as an oracle. It can handle all polyhedra that SCIP understands, e.g., mixed-integer hulls of ZIMPL models. Here are some sample invocations:
ipo–dimension: Computes the affine hull.
–facets:Uses the objective function present in the instance to computes facets.
1000: Additionally usese 1000 randomly samples objective functions for facet generation..
'(x1=1)': Computes the smallest face that contains the unit vector with x1=1.
IPO is an open source project. You are free to use it in your commercial or non-commercial applications under very permissive license terms.
Any publication of results to which using IPO contributed must cite this project.
The project is maintained by Matthias Walter.
Pull from the git repository. Note that IPO is not available as in a packaged form (i.e., a tar.gz archive) since it is still under heavy development. This will change once it reaches a more stable state.
After cloning, please follow the instructions in the INSTALL file.