Exact algorithms and software in optimization and polyhedral computation

ABSTRACT

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.

REFERENCES

• 1: Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.
• 2: The CORE library. http://cs.nyu.edu/exact/.
• 3: GMP, GNU's library for arbitrary precision arithmetic. http://gmplib.org/.
• 4: PARI/GP, a c-library for fast computation in number theory. http://pari.math.u-bordeaux.fr/.
• 5: 4ti2 team. 4ti2--a software package for algebraic, geometric and combinatorial problems on linear spaces. Available at www.4ti2.de.
• 6: D. Avis. lrs Homepage. http://cgm.cs.mcgill.ca/~avis/C/lrs.html
• 7: J. de Loera, D. Haws, R. Hemmecke, P. Huggins, J. Tauzer, and R. Yoshida. LattE. University of California, Davis, 2005. http://www.math.ucdavis.edu/~latte/
• 8: K. Fischer, B. Gärtner, S. Schönherr, and F. Wessendorp. Cgal's linear and quadratic programming solver, 2007. http://www.cgal.org/Pkg/QPSolver
• 9: K. Fukuda. From the zonotope construction to the Minkowski addition of convex polytopes. Journal of Symbolic Computation, 38(4):1261--1272, 2004.
• 10: K. Fukuda. Polyhedral computation FAQ, 2004. http://www.ifor.math.ethz.ch/~fukuda/fukuda.html.
• 11: K. Fukuda. cdd, cddplus and cddlib homepage, 2007. http://www.ifor.math.ethz.ch/~fukuda/cdd_home/.
• 12: K. Fukuda, A. Jensen, and R. Thomas. Computing Gröbner fans. Mathematics of Computation, 76:2189--2212, 2007.
• 13: 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. http://www.math.tu-berlin.de/diskregeom/.
• 14: A. Jensen. Gfan version 0.3: A user's manual, 2007. http://www.math.tu-berlin.de/~jensen/software/gfan/gfan.html.
• 15: M. Kiyomi. Exlp, an exact linear programming solver. http://members.jcom.home.ne.jp/masashi777/exlp.html.
• 16: J. Rambau. TOPCOM, a package for computing Triangulations of point configurations and oriented matroids. http://www.rambau.wm.uni-bayreuth.de/.
• 17: S. Verdoolaege. Barvinok: a library for counting the number of integer points in parametric and non-parametric polytopes, version 0.26, 2008. http://www.kotnet.org/~skimo/barvinok/
• 18: C. Weibel. Minksum version 1.4. Mathematics Institute, EPF Lausanne, 2006. http://roso.epfl.ch/cw/poly/public.php.

INDEX TERMS

General Terms:
Algorithms, Reliability, Theory

Keywords:
algorithms, convex geometry, exact implementation, optimization, polytopes