next_inactive up previous

Exact Algorithms and Software in Optimization and Polyhedral Computation

Komei Fukuda
Institute for Operations Research and
Institute of Theoretical Computer Science
ETH Zurich, Zurich, Switzerland

Date: April 23, 2008



In this tutorial, we present a new field of research on implementing exact algorithms in optimization and polyhedral computation in exact (arbitrary precision) arithmetic. Such algorithms including those to solve linear programming and convex hull problems have been implemented mostly with floating-point arithmetic. This new field of developing ``exact software'' in optimization and polyhedral computation is now at the second stage where new mathematical tools relying on optimization and polyhedral codes are being developed that have not been implemented before. This tutorial is not meant to cover all important developments but to look at some interesting facets.


Most existing computer codes for solving optimization problems such as linear and quadratic programming work with floating-point arithmetic and thus do not guarantee the correctness of output. Those codes typically read input with imprecise numbers and output approximate solutions that are usually satisfactory for users who are not expecting mathematical correctness. Clearly these imprecise codes are not very useful for proving mathematical claims or for solving problems even approximately which have very large and small numbers in their input data. Another disadvantage of imprecise codes is that even if such codes might be correct almost always, say at the failure rate of $ 0.0001 \%$ for your problem instances, it might not be suitable for a computation that requires the solution of a large number of optimization problems without any single failure. There are many such computations arising from computational geometry and algebra.

One natural way to implement exact algorithms mathematically correctly is to use exact (arbitrary precision) arithmetic such as rational exact arithmetic. Fortunately many efficient exact arithmetic libraries are now available [1,2,3,4]. This tutorial is not meant to cover all important developments but to look at some interesting facets along this direction.


Linear Programming

Given a rational matrix $ A \in {\mathbb{Q}}^{m\times d}$, two vectors $ b \in {\mathbb{Q}}^{m}$, $ c \in {\mathbb{Q}}^{d}$, a linear programming problem (LP) is to find a vector $ x$ maximizing $ c^T x$ subject to $ A x \le b$ and $ x\ge 0$. The simplex method is a practically efficient method to solve LPs which is easily implementable with exact arithmetic. There are several exact implementations of the simplex method, e.g. [11,6,8,15]. These implementations run with exact arithmetic and are extremely reliable. EXLP [15] is a standalone code and can exploit the sparsity of input matrix $ A$. On the other hand, CDDLIB, LRSLIB and CGAL's solver[11,6,8] are all callable libraries but do not take advantage of the sparsity.

Quadratic Programming

If one replaces the linear objective function $ c^T x$ of the LP with a concave quadratic function, one obtains a convex quadratic programming problem (QP). Perhaps, [8] is a unique exact library to solve (dense) convex QPs.

Polyhedral Computation

A (convex) polyhedron $ P$ in $ {\mathbb{R}}^d$ is a set of form $ P(A, b):=\{ x\in {\mathbb{R}}^d: A x \le b\}$ for some matrix $ A \in {\mathbb{Q}}^{m\times d}$ and some vector $ b \in {\mathbb{Q}}^{m}$. The system $ A x \le b$ is called an H-representation of $ P$. A bounded polyhedron is called polytope. Every polyhedron has another representation, namely, the set of all extreme points (vertices) and extreme rays, known as a V-representation.

Representation Conversion

The representation conversion for a polyhedron is to find the second representation from a given (H or V)-representation. In fact, the two conversions are computationally equivalent. Two codes [11,6] implementing two totally different algorithms have been used extensively, and for example, a polyhedral-manipulation system POLYMAKE [13] includes them as core engines. There are many other exact implementations available, see [10].

Minkowski Sums

The Minkowski sum $ P+Q$ of two polytopes $ P$ and $ Q$ is a very useful operation in mathematics. An exact implementation MINKSUM [18] of the algorithm [9] relies on the exact LP solver in CDDLIB [11].


Regular Triangulations

Given a finite set $ P$ of points in $ {\mathbb{R}}^d$, the software TOPCOM [16] can generates all regular triangulations of $ P$. Checking whether a given triangulation is regular or not can be formulated as an LP. TOPCOM calls the exact LP solver in CDDLIB [11] for this purpose.

Gröbner fans

An algorithm to compute the Gröbner fan of a polynomial ideal was recently proposed in [12], and an exact implementation is available [14]. Figure 1 is a graphical output of a Gröbner fan as a cut section of the positive orthant in $ {\mathbb{R}}^3$ by a hyperlane. Like [18], the code calls the exact LP solver in CDDLIB [11] many times in order to remove redundant inequalities from a highly redundant linear inequality system.

Figure: The Gröbner Fan of $ \langle a^5+b^3+c^2-1, a^2+b^2+c-1, a^6+b^5+c^3-1\rangle$

Enumeration of Lattice Points

Given a polytope $ P\in {\mathbb{R}}^d$, generating or counting all integer (lattice) points in $ P$ is a classical problem in mathematics. It is also closely related to solving integer programming which is to find a lattice point in $ P$ maximizing a linear objective function. There are a couple of implementations of Barvinok's algorithm available [17,7]. Both rely on exact algebraic and polyhedral computation codes such as 4ti2 [5] and CDDLIB [11].

Future Perspective

The recent developments of exact implementations, typically in the form of callable libraries, of optimization and polyhedral computation algorithms have contributed to the computing environment of mathematicians and scientists. In particular, we are seeing a totally new set of mathematical tools built on such libraries. It is expected that new exact tools and libraries will find users beyond the scientific community, because in application domains such as control theory and mechanical engineering, numerical instability caused by imprecision might result in meaningless computation.


CGAL, Computational Geometry Algorithms Library.

The CORE library.

GMP, GNU's library for arbitrary precision arithmetic.

PARI/GP, a c-library for fast computation in number theory.

4ti2 team.
4ti2--a software package for algebraic, geometric and combinatorial problems on linear spaces.
Available at

D. Avis.
lrs Homepage.

J. de Loera, D. Haws, R. Hemmecke, P. Huggins, J. Tauzer, and R. Yoshida.
University of California, Davis, 2005.

K. Fischer, B. Gärtner, S. Schönherr, and F. Wessendorp.
CGAL's linear and quadratic programming solver, 2007.

K. Fukuda.
From the zonotope construction to the Minkowski addition of convex polytopes.
Journal of Symbolic Computation, 38(4):1261-1272, 2004.

K. Fukuda.
Polyhedral computation FAQ, 2004.

K. Fukuda.
cdd, cddplus and cddlib homepage, 2007.

K. Fukuda, A. Jensen, and R. Thomas.
Computing Gröbner fans.
Mathematics of Computation, 76:2189-2212, 2007.

E. Gawrilow and M. Joswig.
polymake: a framework for analyzing convex polytopes.
In G. Kalai and G. M. Ziegler, editors, Polytopes -- Combinatorics and Computation, pages 43-74. Birkhäuser, 2000.

A. Jensen.
Gfan version 0.3: A user's manual, 2007.

M. Kiyomi.
EXLP, an exact linear programming solver.

J. Rambau.
TOPCOM, a package for computing Triangulations of point configurations and oriented matroids.

S. Verdoolaege.
Barvinok: a library for counting the number of integer points in parametric and non-parametric polytopes, version 0.26, 2008.

C. Weibel.
Minksum version 1.4.
Mathematics Institute, EPF Lausanne, 2006.

About this document ...

Exact Algorithms and Software in Optimization and Polyhedral Computation

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 issac08-fukuda

The translation was initiated by Komei Fukuda on 2008-04-23

next_inactive up previous
Komei Fukuda 2008-04-23