Some Python programs for dealing with polytopes
At the moment, there is just one basic program listed here,
but I hope to add several more eventually. These are nor meant to
perform tasks on an industrails cale, but just to
allow one to explore small cases easily. They are therefore in Python,
which is easy to read and write.
-
The basic program LP.py.
This holds a single class LP_Dictionary. The name
is based on Chvátal's terminology. There are two
initializations. One is from a matrix assembled from a
sequence of inequalities. It finds first an independent
subset of these affine functions as a coordinate system,
and then finds a vertex frame on the region defined
by the inequalities. The other alternative has as arguments
the full data structure of a vertex frame:
matrix of affine functions F, transformation matrix R,
array basis of the index in F of coordinate functions,
array others of the other affine functions,
and an arrayindex, one item for each
affine function, specifying for each coordinate variable
what column in F it corresponds to,a nd None for the others.
At the only moment, all that can be done with this is
to find the dimension of the region, the vertex of the region on
which a given linear function takes a maximum value,
and (slightly faster) just the maximum value itself.
-
A few other simple programs demonstrating how
the routines in LP.py can be used.
References
-
Vašek Chvátal.
Linear programming,
W. H. Freeman, 1983.
|