Compact representations of all members of an independence system

详细信息    查看全文

• 作者：Utz-Uwe Haus ; Carla Michini
• 关键词：Compact representations ; Boolean optimization ; Enumeration ; Stable sets ; Discrete relaxations ; Decision diagrams
• 刊名：Annals of Mathematics and Artificial Intelligence
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：79
• 期：1-3
• 页码：145-162
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence (incl. Robotics); Mathematics, general; Computer Science, general; Complex Systems;
• 出版者：Springer International Publishing
• ISSN：1573-7470
• 卷排序：79

文摘

It is well known that (reduced, ordered) binary decision diagrams (BDDs) can sometimes be compact representations of the full solution set of Boolean optimization problems. Recently they have been suggested to be useful as discrete relaxations in integer and constraint programming (Hoda et al. 2010). We show that for every independence system there exists a top-down (i.e., single-pass) construction rule for the BDD. Furthermore, for packing and covering problems on n variables whose bandwidth is bounded by \(\mathcal {O}(\log n)\) the maximum width of the BDD is bounded by \(\mathcal {O}(n)\). We also characterize minimal widths of BDDs representing the set of all solutions to a stable set problem for various basic classes of graphs. Besides implicitly enumerating or counting all solutions and optimizing a class of nonlinear objective functions that includes separable functions, the results can be applied for effective evaluation of generating functions.