'Optimization & Applications' (see information & program)
Feb 18 - May 27, 2013
|Lecturer||Prof. Komei Fukuda||Time||
V: Tu 15–17
U: Tu 17–18
|Place||HG E 1.1|
Polyhedral 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.
In 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.
This course assumes the basic knowledge of linear programming, which is taught in courses such as "Introduction to Optimization" (401-2903-00L) and "Mathematical Optimization" (401-3901-00L), formerly known as "Optimization Techniques".
Solving at least 50% of exercise problems is required for a student to qualify for the exam. In order (for both a masters and doctorate student) to obtain credits, one has to pass the oral exam during an ordinary exam period. The duration is thirty minutes.
will be available on this page during the course
|21.02.2012||Introduction to Polyhedral Computation||Chapters_1-4||No exercises||References|
|28.02.2012||Integers, Linear Equations and Complexity|
|06.03.2012||Linear Inequalities, Convexity and Polyhedra|
|20.03.2012||Linear Inequalities, Convexity and Polyhedra|
|27.03.2012||Linear Inequalities, Convexity and Polyhedra|
|03.04.2012||Duality of Polyhedra||Chapters 5-12|
|10.04.2012||Easter holidays. No class|
|17.04.2012||Line Shellings and Euler's Relation|
|24.04.2012||Basic Computations with Polyhedra|
|01.05.2012||Labour Day. No class|
McMullen's Upper Bound Theorem
Polyhedral Representation Conversion
Hyperplane Arrengements and Points Configurations
Minkowski Additions of Polytopes
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.