Computations with polyhedra

The following sections are included:

• Extreme rays and minimal generators in convex cones

• Minimal generators of a polyhedral cone

• The double description method

  • Converting from half space to vertex representation

  • Converting from vertex to half space representation

  • Computing the convex hull

• Linear programming and the simplex algorithm

  • Two examples of linear programs

  • The simplex algorithm in a special case

  • The simplex algorithm for polyhedra in general form

  • The simplicial hack

  • The computational miracle of the simplex tableau

  • Computing a vertex in a polyhedron

• Exercises