Rigorous Systems Research Group (RSRG) Seminar

Binary Decision Diagrams (BDDs) are well-studied data structures for compactly representing and manipulating binary functions.  Historically, BDDs have been primarily used in formal logic and circuit design. However, more recently it was observed that decision diagrams can be used to represent families of combinatorial objects via the indicator function for such families, and thus that this data structure can be used to perform combinatorial optimization.  In this talk, we discuss a number of recent applications of decision diagrams to optimization problems, which demonstrate order-of-magnitude computational improvements over competing methods.