401-3908-09L  Polyhedral Computation

SemesterSpring Semester 2016
LecturersK. Fukuda
Periodicitynon-recurring course
Language of instructionEnglish


AbstractPolyhedral computation deals with various computational problems associated with convex polyhedra in general dimension. Typical problems include the representation conversion problem (between halfspace and generator representations), the polytope volume computation, the construction of hyperplane arrangements and zonotopes, the Minkowski addition of convex polytopes.
Objective
ContentIn this lecture, we study basic and advanced techniques for polyhedral computation in general dimension. We review some classical results on convexity and convex polyhedra such as polyhedral duality, Euler's relation, shellability, McMullen's upper bound theorem, the Minkowski-Weyl theorem, face counting formulas for arrangements, Shannon's theorem on simplicial cells. Our main goal is to investigate fundamental problems in polyhedral computation from both the complexity theory and the viewpoint of algorithmic design. Optimization methods, in particular, linear programming algorithms, will be used as essential building blocks of advanced algorithms in polyhedral computation. Various research problems, both theoretical and algorithmic, in polyhedral computation will be presented.

We also study applications of polyhedral computation in combinatorial optimization, integer programming, game theory, parametric linear and quadratic programming.

Teaching assistant: May Szedlák
Lecture notesLecture Notes and Introduction Materials:
Link

Exercises:
Link
Prerequisites / NoticeThis course assumes the basic knowledge of linear programming, which is taught in courses such as "Mathematical Optimization" (401-3901-00L) and "Introduction to Optimization" (401-2903-00L). / Solving all exercise problems is recommended for a student to be ready for the exam.