Komei Fukuda
Institute for Operations Research and
Institute of Theoretical Computer Science
ETH Zurich,
Zurich, Switzerland
fukuda@ifor.math.ethz.ch
Date: April 23, 2008
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 
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.
Given a rational matrix
,
two vectors
,
, a linear programming
problem (LP) is to find a vector 
maximizing 
subject to
and 
.
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 
.
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.
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.
A (convex) polyhedron 
in
is a set of form
for some matrix
and some vector
.
The system is called an H-representation of .
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.
of two polytopes and 
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].
Given a finite set of points in
, the software
TOPCOM [16] can generates all regular triangulations
of . 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.
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
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.
Given a polytope
, generating or counting all integer (lattice)
points in is a classical problem in mathematics. It is also
closely related to solving integer programming which is to
find a lattice point in 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].
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.
