On threshold BDDs and the optimal variable ordering problem Many combinatorial optimization problems can be formulated as $0/1$ integer programs ($0/1$ IPs). The investigation of the structure of these problems raises the following tasks: count or enumerate the feasible solutions and find an optimal solution according to a given linear objective function. All these tasks can be accomplished using binary decision diagrams (BDDs), a very popular and effective datastructure in computational logics and hardware verification. par We present a novel approach for these tasks which consists of an $output-sensitive$ algorithm for building a BDD for a linear constraint (a so-called threshold BDD) and a parallel AND operation on threshold BDDs. In particular our algorithm is capable of solving knapsack problems, subset sum problems and multidimensional knapsack problems. par BDDs are represented as a directed acyclic graph. The size of a BDD is the number of nodes of its graph. It heavily depends on the chosen variable ordering. Finding the optimal variable ordering is an NP-hard problem. We derive a $0/1$ IP for finding an optimal variable ordering of a threshold BDD. This $0/1$ IP formulation provides the basis for the computation of the variable ordering spectrum of a threshold function. par We introduce our new tool azove 2.0 as an enhancement to azove 1.1 which is a tool for counting and enumerating $0/1$ points. Computational results on benchmarks from the literature show the strength of our new method.
Keywords for this software
References in zbMATH (referenced in 11 articles , 2 standard articles )
Showing results 1 to 11 of 11.
- Assarf, Benjamin; Gawrilow, Ewgenij; Herr, Katrin; Joswig, Michael; Lorenz, Benjamin; Paffenholz, Andreas; Rehn, Thomas: Computing convex hulls and counting integer points with polymake (2017)
- Bergman, David; Cire, Andre Augusto: On finding the optimal BDD relaxation (2017)
- Toth, Csaba D. (ed.); Goodman, Jacob E. (ed.); O’Rourke, Joseph (ed.): Handbook of discrete and computational geometry (2017)
- Bergman, David; Cire, Andre A.: Theoretical insights and algorithmic tools for decision diagram-based optimization (2016)
- Molinero, Xavier; Riquelme, Fabián; Serna, Maria: Forms of representation for simple games: sizes, conversions and equivalences (2015)
- Berghammer, Rudolf; Bolus, Stefan: On the use of binary decision diagrams for solving problems on simple games (2012)
- Bolus, Stefan: Power indices of simple games and vector-weighted majority games by means of binary decision diagrams (2011)
- Bollig, Beate: On the OBDD complexity of threshold functions and the variable ordering problem (extended abstract) (2009)
- Bollig, Beate: On the size of (generalized) OBDDs for threshold functions (2009)
- Behle, Markus: On threshold BDDs and the optimal variable ordering problem (2008)
- Behle, Markus: On threshold BDDs and the optimal variable ordering problem (2007)