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

Oracles

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

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:

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

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:

About

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.

After cloning, please follow the instructions in the INSTALL file.