ICMS 2016 Session: Polyhedral Methods in Geometry and Optimization
ICMS 2016: Home, Sessions
Aim and Scope
Polyhedra occur in many contexts in geometry and optimization. For example, convex polyhedra occur in optimization
as the feasible regions of linear programs. Moreover, integer linear programming is the same as linear
programming over the convex hull of the lattice points in a polyhedron. In algebraic geometry and its
applications, piecewise-linear shapes occur in the guise of polyhedral fans. Examples include secondary and
Gröbner fans. This session wants to bring together people working on algorithms and software dealing with any of
Specific topics include, but are not restricted to, the following:
- convex hull computations
- (mixed integer) linear programming
- explicit methods for triangulating point configurations
- computations in toric or tropical geometry
- parallelization of polyhedral computations
- polyhedral methods in algebraic statistics
- algorithms exploiting symmetry in any of the above
Tropical dimension bounds for monomial-free ideals
Tropical computations in polymake
Multiobjective integer linear programming by tropical convexity
Toric geometry in polymake
qskeleton: parallel polyhedral computing software based on the double description method and Fourier-Motzkin elimination
Sage flavored LattE integrale
Linear programming using line and zonotope intersection
- qskeleton: parallel polyhedral computing software based on the double description method and Fourier-Motzkin elimination
We present open-source polyhedral computing software qskeleton.
It implements the Fourier-Motzkin
elimination (FME) method for variable elimination and a variation of the double
description method (DDM) for computing a dual representation of convex
polyhedra. The software is an ideological descendant of N.Yu. Zolotykh’s
skeleton package and aims to combine its advancements with other approaches,
such as using some ideas of the Quickhull algorithm in the DDM or combining the
graph test of skeleton with other accelerating data structures for adjacency
testing in DDM / Chernikov rules in FME.
Parallel computing is an important direction of development of qskeleton. It
supports shared-memory OpenMP parallelism. We are currently developing a version
for Intel Xeon Phi coprocessors, which offer 60 cores on shared memory and serve
as a promising alternative to GPUs in terms of accelerators with easier
programming. Our first results show a modest (up to 1.5 x) advantage of Xeon Phi
over an 8-core CPU. However, there is a potential to improve the performance on
Xeon Phi by efficiently utilizing vector (SIMD) instructions. We will present
evaluation of suitability of the DDM and FME for Xeon Phi coprocessors and our
experience of porting and optimizing the code.
- The subdivision of large simplicial cones in Normaliz
Normaliz is an open-source software for computations in rational cones and affine monoids. The two main
computational goals are (1) the Hilbert Basis, a minimal generating system of the monoid of lattice points of a given
cone; (2) the Hilbert (or Ehrhart) series, the generating function of the degree wise lattice point enumerator. Normaliz
offers a rich variety of input types for cones and lattices. It can be accessed from several computer algebra systems,
and provides a C++ class library for use in other software.
The primal algorithm of Normaliz is based on triangulations. The complexity of
the algorithm is determined by the combinatorial complexity of the triangulation
and the arithmetical complexity of the resulting simplicial cones, measured by
the determinant of the generating matrix. Normaliz can cope with very large
triangulations due to its pyramid decomposition algorithm, but large
determinants are a severe problem, despite of the parallelized computation of a
single large simplicial cone.
An often successful way out is the (iterated) subdivision of large simplicial
cones by stellar subdivisions into simplicial subcones whose determinant sum is
significantly smaller than the original determinant. At present Normaliz offers
two methods for finding good subdividing vectors. The first approach uses
techniques from integer programming. For this purpose we access the integer
programming solver from SCIP. The second approach approximates the critical
simplicial cone from the outside by a cone with smaller generators and tries to
find good subdividing vectors among the lattice points of the approximating cone.
- Multiobjective integer linear programming by tropical convexity
In multiobjective linear programming, we aim to generate the polyhedral
frontier of all Pareto optimal solutions in objective space. This can
be done using Benson's outer approximation algorithm, which interleaves
scalarisations (single-objective linear programs) with the classical
double description method.
The generalisation to integer linear programming is significantly more
complex, due to the loss of convexity - the frontier of Pareto optimal
solutions no longer has a polyhedral description. Here we show how to
overcome this using the notion of tropical convexity: the Pareto optimal
frontier can be described in terms of tropical polyhedra, and can be
generated using an analogous algorithm based on interleaving integer
scalarisations with a tropical double description method. As a
corollary, we show that for d objective functions and n Pareto optimal
points, we can enumerate these Pareto optimal points using at most
- Sage flavored LattE integrale
I will present the latest developments in our code LattE integrale,
computer software dedicated to the problems of counting lattice points
and integration inside convex polytopes, and its connection to the
computer algebra system Sage (by W. Stein and many contributors).
- Linear programming using line and zonotope intersection
We study linear programming with box constraints on all variables (in addition to other linear
constraints). Following research of Fujishige et al., we consider this problem as finding an intersection between a line
and a specially constructed zonotope. This approach allows us to explore a variety of real-time optimization algorithms,
where we do not need to rely on the solution of linear equations. This may be of interest for embedded optimization,
e.g. in model predictive control. We consider parallelization of line-zonotope approach using multiple projections of
line points on the zonotope via first-order methods (such as Frank-Wolfe), as well as finding the intersection using
off-line construction of the zonotope in low-dimensional problems.
- Tropical computations in polymake
In this talk I'll showcase some of the features of polymake that deal with tropical things. Most of these are
brand new features of the recent polymake release 3.0. Examples include: Tropical arithmetic (Min or Max - it's your
choice!), tropical convex hull computations, tropical polynomials and tropical hypersurfaces. I will also present my
own extension "a-tint", which mostly deals with tropical intersection theory (but has a much wider range of features
than that) and which has recently been included as a bundled extension in polymake.
- Symmetry Handling in Binary Programs via Polyhedral Methods
Symmetry in binary programs (BP) is known to have a negative influence
on the performance of branch-and-bound procedures. We present two
types of such symmetries which are described in the literature, and we
discuss how symmetries in BPs can be detected.
To speed up the solution process of branch-and-bound solvers, one can try to cut off symmetric solutions by
additional cutting planes. Therefore, we describe a standard approach which defines a fundamental domain of
the action of the symmetry group by inequalities with exponential coefficients. Since the exponential
coefficients may lead to numerical instabilities, we consider symmetry breaking polytopes (symretopes) which
are the convex hull of all binary vectors contained in the fundamental domain. To obtain a tractable integer
programming (IP) formulation for symretopes, we concentrate on knapsack polytopes which are induced by a
single fundamental domain inequality, so-called symresacks. Since the optimization problem over symresacks
and the separation problem of minimal cover inequalities for symresacks can be solved in quadratic time,
this yields a tractable IP-formulation for symretopes with ternary coefficients if the size of the symmetry
group is polynomial in the dimension. Afterwards, we present numerical results of the implementation of this
IP-formulation in SCIP which show the potential effectiveness of this approach.
- Tropical dimension bounds for monomial-free ideals
Gröbner bases techniques have become a staple in computational
algebraic geometry. However, while Gröbner bases computations are
becoming faster and faster, there will always be problems that are
beyond the scope of existing possibilities.
In this talk, I will discuss methods in tropical geometry which
Hampton and Jensen used to obtain dimensional bounds for monomial-free
polynomial ideals. These polyhedral techniques succeeded where Gröbner
bases computations were infeasible and yielded ground-breaking results
in the 4- and 5-body problem of celestial mechanics.
The basic idea is very straight-forward, given a set of generators of
a polynomial ideal. First, compute their tropical prevariety to obtain
an lower and upper bound on the dimension of the tropical variety,
which coincides with the dimension of the ideal. Then, in a second
step, rule out cones of the tropical prevariety to improve the upper
I will present some optimized algorithms for computing these tropical
dimension bounds and showcase their implementation in the computer
algebra system Singular on the aforementioned examples. I will also
briefly recall known ways for exploiting parallelization and symmetry
in these kinds of algorithms.
- Investigating Polyhedra by Oracles
The software framework IPO (Investigating Polyhedra by Oracles) is presented which allows to analyze
polyhedra that are given only implicitly by an optimization oracle. The motivation comes from polyhedral combinatorics,
where the oracle can easily be provided by a mixed-integer-programming solver. IPO detects a full system of equations
and some facets of the implicitly given polyhedron with exact arithmetic. The facets are produced in such a way that
they are helpful in optimizing a given objective function. This is in contrast to usual convex-hull algorithms which
produce the entire description of a polyhedron, but run out of resources for small dimensions already. Thus, IPO can
typically handle larger dimensions.
In the talk we will briefly discuss how IPO actually works, followed
by a demonstration of its capabilities. For this we consider short
computational studies, namely dimension analysis of MIPLIB 2.0,
facet-detection for matching polytopes with one quadratic objective
term and adjacency statistics for TSP polytopes.
IPO is available at http://polyhedra-oracles.bitbucket.org/.
- Toric geometry in polymake
Toric geometry gives a combinatorial interpretation for objects from algebraic geometry with action of an
algebraic torus. For example, toric varieties correspond to fans and torus invariant divisors correspond to formal
linear combinations of the rays of this fan. Doing research in toric geometry one can arrive at problems from algebraic
geometry that do not yet have a combinatorial equivalent. The interface of polymake to Singular allows one to proceed in
order to find the correct interpretation.
This talk will give an overview over the application "fulton" of
polymake for toric geometry, as well as the Singular interface. We will
give a concrete example of how this helped solve a problem from toric