IPO - Investigating Polyhedra by Oracles

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...

- compute the
**affine hull**of*P*in the sense that it returns*(d+1)*many affinely independent points in*P*and*(n-d)*many linearly independent equations valid for*P*, where*d*is*P*'s dimension. See AffineHull for details. - compute a
**facet-defining inequality**that is**violated**by a given point.

See Separation for details. - compute
**facets that are "helpful"**when maximizing a specified objective vector*c*. More precisely, it iteratively solves LPs whose inequalities correspond to some of*P*'s facets, until the current optimum is in*P*. As long as this is not the case, the procedure returns violated facet-defining inequalities and adds them to the LP. **check**whether two given vertices of*P*are**adjacent**.

See SmallestFace for details.- compute the
**smallest face**of*P***containing a given point**by means of an inequality defining this face.

See SmallestFace for details. **check**whether a given point is a**vertex**of*P*.

See SmallestFace for details.

IPO's requirements for an optimization oracle are very simple:

- Essentially, for a given objective vector, it only has to return a point in
*P*of maximum objective value. - If the maximum is not attained, it must return an unbounded direction proving this. Of course, if
*P*is empty, it must claim "infeasible". - There exist several ways to speed up certain algorithms, e.g., by returning additional solutions, implementing another heuristic oracle that is faster but does not guarantee optimality, etc.

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:

- OracleBase: The most general base class.
- FaceOracleBase: Inherit from this class if your oracle is not capable of optimizing over a face of
*P*explicitly.

For mixed-integer programs, several oracles are already implemented:

- SCIPOracle: This oracle is built from a SCIP instance which is used for optimization. It inherits from MIPOracle which cares about the correct handling of the floating-point solutions returned by SCIP. !
- ExternalOracle: This oracle uses an external program using a defined interface.

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.`ipo`

`–facets:`

Uses the objective function present in the instance to computes facets.`ipo`

`–facets`

`–random`

`1000`

: Additionally usese 1000 randomly samples objective functions for facet generation..`ipo`

`–smallest-face`

`–point`

`'`

(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.

@MISC{Walter16,

author = {Walter, Matthias},

title = {\emph{IPO -- Investigating Polyhedra by Oracles}, \\ \url{http://polyhedra-oracles.bitbucket.org/}},

year = {2016},

}

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.

Generated by 1.8.11