[Bill Casselman's home page]

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.


  • Vašek Chvátal. Linear programming, W. H. Freeman, 1983.