IPO - Investigating Polyhedra by Oracles

# Description

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.

# Motivation

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.

# Functionality

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.

# Oracles

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.

# Technical Details

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.

# Command Line Tool

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.

# Getting it to work

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.