# azove

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

Anything in here will be replaced on browsers that support the canvas element

## References in zbMATH (referenced in 6 articles , 2 standard articles )

Showing results 1 to 6 of 6.
Sorted by year (citations)