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