Tutorial for a Course

These page comprises some demos given at a course on Discrete Optimization at TU Darmstadt, Summer 2007. Some things are more closely related to optimization than others.

This page is under construction: It will grow until the end of the term.

First Steps

This is the first demo whose purpose is to show the principal behavior of polymake.

The following commands produce a 3-dimensional cube (whose vertices have (+/-1)-coordinates). It is visualized, and some combinatorial properties are computed. Having the output sections numbered makes the implicit numbering scheme explicit.

> cube c3.poly 3 > polymake c3.poly VERTICES FACETS VERTICES 1 -1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 -1 1 1 1 1 1 1 FACETS 1 1 0 0 1 -1 0 0 1 0 1 0 1 0 -1 0 1 0 0 1 1 0 0 -1 > polymake c3.poly VISUAL > polymake c3.poly 'numbered(VERTICES)' 'numbered(FACETS)' 'numbered(VERTICES_IN_FACETS)' numbered(VERTICES) 0:1 -1 -1 -1 1:1 1 -1 -1 2:1 -1 1 -1 3:1 1 1 -1 4:1 -1 -1 1 5:1 1 -1 1 6:1 -1 1 1 7:1 1 1 1 numbered(FACETS) 0:1 1 0 0 1:1 -1 0 0 2:1 0 1 0 3:1 0 -1 0 4:1 0 0 1 5:1 0 0 -1 numbered(VERTICES_IN_FACETS) 0:{0 2 4 6} 1:{1 3 5 7} 2:{0 1 4 5} 3:{2 3 6 7} 4:{0 1 2 3} 5:{4 5 6 7} > polymake c3.poly F_VECTOR SIMPLE SIMPLICIAL CUBICAL F_VECTOR 8 12 6 SIMPLE 1 SIMPLICIAL 0 CUBICAL 1

Zonotopes

Zonotopes are Minkowski sums of line segments (or, equivalently, affine projections of a regular cube). The section ZONOTOPE_INPUT_VECTORS serves as an input section to define a zonotope. For the sake of the compatibility with other polymake functions each line is a vector in homogeneous coordinates (this time always starting with a non-zero entry).

For instance a file z.poly containing the lines

ZONOTOPE_INPUT_VECTORS 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 1

defines the polytope [0,e1]+[0,e2]+[0,e3]+[0,e1+e2+e3].

How does a random zonotope look alike? Well here is one version. We start with the (convex hull of) random points on the unit sphere. And then we write a short script, say z_script, which takes the VERTICES of the random polytope and take them as ZONOTOPE_INPUT_VECTORS for a new polytope which is then visualized.

> rand_sphere rand_3_15.poly 3 15 > polymake --script z_script rand_3_15.poly
convex hull of 15 random points random zonotope from 15 line segments

The picture to the right is what we obtain if we apply JavaView's function Method->Effect->Unfold Geometry ... to our zonotope.

There is also a postscript version for better visibility.
mailto: lastname at mathematik.tu-darmstadt.de
Last modified: Tue May 8 18:57:54 CEST 2007