A convex cone is
polyhedral if it is a finite
intersection of halfspaces. A convex cone is
finitely
generated if it is the set of all nonnegative linear
combinations of a finite set of vectors. The fundamental
theorem for cones states that a convex cone is polyhedral if
and only if it is finitely generated.
FourierMotzkin is a Macaulay2 implementation of
the Double Description Method (of Fourier, Dines and Motzkin)
for converting between these two basic representations for
convex cones. For polytopes, this allows one to convert
between the convex hull of a finite point set and the bounded
intersection of halfspaces.
Here are some examples illustrating some uses of this
package.
This package is intended for use with relatively small
polyhedra. For larger polyhedra, please consider
cdd,
lrs or
qhull; also see
polymake.
For an introduction to polyhedra and Fourier-Motzkin
elimination, we recommend Chapter 2 in
Gunter
M. Zielger's Lectures on Polytopes, Graduate
Texts in Mathematics 152, Springer-Verlag, New York, 1995.
For historical comments, see Section 12.2 in
Alexander
Schrijver's Theory of Linear and Integer
Programming Wiley-Interscience Series in Discrete
Mathematics, John Wiley and Sons, Chichester, 1986.