Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:0/1 vertex and facet enumeration with BDDs
Speaker:Markus Behle
coming from:Max-Planck-Institut für Informatik - D 1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, SWS
We use this to send out email in the morning.
Level:AG Audience
Language:-- Not specified --
Date, Time and Location
Date:Tuesday, 19 December 2006
Duration:20 Minutes
Building:E1 4
In polyhedral studies of 0/1 polytopes two prominent problems exist.

One is the vertex enumeration problem: Given a system of inequalities, enumerate its feasible 0/1 points.
Another one is the convex hull problem: Given a set of 0/1 points in dimension d, enumerate the facets of the corresponding polytope.
We developed two new approaches for both problems. The novelty of our algorithms is the incorporation of binary decision diagrams (BDDs).

In this talk I will only concentrate on the vertex enumeration problem. Our new tool "azove" will be introduced, which is currently the fastest software for counting and enumerating 0/1 points in a polytope.

Name(s):Markus Behle
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Markus Behle, 12/06/2006 11:44 AM
  • Markus Behle, 12/06/2006 11:43 AM -- Created document.