Abstract
The computation of all integral points in Minkowski (or vector) sums of convex lattice polytopes of arbitrary dimension appears as a subproblem in algebraic variable elimination, parallel compiler code optimization, polyhedral combinatorics and multivariate polynomial multiplication. We use an existing approach that avoids the costly construction of the Minkowski sum by an incremental process of solving Linear Programming (LP) problems. Our main contribution is to exploit the similarities between LP problems in the tree of LP instances, using duality theory and the two-phase simplex algorithm. Our public domain implementation improves substantially upon the performance of the above mentioned approach and is faster than porta on certain input families; besides, the latter requires a description of the Minkowski sum which has high complexity. Memory consumption limits commercial or free software packages implementing multivariate polynomial multiplication, whereas ours can solve all examined data, namely of dimension up to 9, using less than 2.7 MB (before actually outputting the points) for instances yielding more than 3 million points.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amarasinghe, S.P.: Parallelizing Compiler Techniques Based on Linear Inequalities. Ph.D. thesis, Computer Systems Lab., Stanford University (1997)
Christof, T., Loebel, A., Stoer, M.: PORTA 1.3.2. Univ. of Heidelberg and ZIB Berlin PORTA (1999), http://www.iwr.uni-heidelberg.de/groups/comopt/software/
Christof, T., Reinelt, G.: Combinatorial Optimization and Small Polytopes. Top (Spanish Statistical and Operations Research Society) 4, 1–64 (1996)
Chvátal, V.: Linear Programming. W.H. Freeman & Co, New York (1983)
Clauss, P.: Counting Solutions to Linear and Nonlinear Constraints Through Ehrart Polynomials: Applications to Analyze and Transform Scientific Programs. In: Intern. Conf. Supercomp, pp. 278–285 (1996)
The Computational Algebra Group. Magma 2.8. University of Sydney, Australia, http://magma.maths.usyd.edu.au/magma/
Cox, D., Little, J., O’Shea, D.: Using Algebraic Geometry. Graduate Texts in Mathematics, vol. 185. Springer, New York (1998)
Dickenstein, A., Emiris, I.Z.: Multihomogeneous Resultant Formulae by Means of Complexes. J. Symb. Computation 36(3-4), 317–342 (2003)
Emiris, I.Z., Zervoudakis, K.: Successive Linear Programs for Computing all Integral Points in a Minkowski Sum, http://www.di.uoa.gr/~quasi/EmiZer.pdf
Emiris, I.Z.: Enumerating a subset of the integer points inside a Minkowski sum. Comp. Geom.: Theory & Appl., Spec. Issue 22(1–3), 143–166 (2002)
Emiris, I.Z., Canny, J.F.: Efficient incremental algorithms for the sparse resultant and the mixed volume. J. Symbolic Computation 20(2), 117–149 (1995)
Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants, Resultants and Multidimensional Determinants, Birkhäuser, Boston (1994)
GNU Project, SciFace Software GmbH. GLPK 3.2.3, GNU LInear Programming Kit, http://www.gnu.org/software/glpk
Gritzmann, P., Klee, V.: Computational convexity. In: Goodman, J.E., O’Rourke, J. (eds.) The Handbook of Discrete and Computational Geometry, pp. 491–516. CRC Press, Boca Raton (1997)
Gritzmann, P., Sturmfels, B.: Minkowski addition of polytopes: Computational complexity and applications to Groebner bases. SIAM J. Disc. Math. 6(2), 246–269 (1993)
Konrad-Zuse-Zentrum für Informationstechnik, Berlin. SoPlex 1.2.1, Sequential Object-oriented simPLEX class library, http://www.zib.de/Optimization/Software/Soplex
Lewis, R.: Fermat, A Computer Algebra System for Polynomial and Matrix Computation. Fordham University, New York, http://www.bway.net/~lewis
Mourrain, B.: Symbolic Numeric Applications, INRIA Sophia-Antipolis (2002), http://www-sop.inria.fr/galaad/synaps/
ILOG S.A. Planner 3.3, Reference Manual (2001)
PolyLib, A library of polyhedral functions (2002), http://icps.u-strasbg.fr/polylibs
Schrijver, A.: Theory of Linear and Integer Programming. J. Wiley & Sons, Chichester (1982)
Sturmfels, B., Zelevinsky, A.: Multigraded Resultants of Sylvester Type. J. of Algebra 163(1), 115–127 (1994)
Whaley, R.C., Patitet, A., Dongarra, J.J.: Automated empirical optimization of software and the ATLAS project, http://netlib.uow.edu.au/atlas/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Emiris, I.Z., Zervoudakis, K. (2005). Successive Linear Programs for Computing All Integral Points in a Minkowski Sum. In: Bozanis, P., Houstis, E.N. (eds) Advances in Informatics. PCI 2005. Lecture Notes in Computer Science, vol 3746. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11573036_9
Download citation
DOI: https://doi.org/10.1007/11573036_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29673-7
Online ISBN: 978-3-540-32091-3
eBook Packages: Computer ScienceComputer Science (R0)