Merging Quality Estimation for Binary Decision Diagrams with Binary Classifiers

摘要

Relaxed binary decision diagrams (BDDs) are used in combinatorial optimization as a compact representation of a relaxed solution space. They are directed acyclic multigraphs which are derived from the state space of a recursive dynamic programming formulation of the considered optimization problem. The compactness of a relaxed BDD is achieved by superimposing states, which corresponds to merging BDD nodes in the classical layer-wise top-down BDD construction. Selecting which nodes to merge crucially determines the quality of the resulting BDD and is the task of a merging heuristic, for which the minimum longest path value (minLP) heuristic has turned out to be highly effective for a number of problems. This heuristic sorts the nodes in a layer by decreasing current longest path value and merges the necessary number of worst ranked nodes into one. There are, however, also other merging heuristics available and usually it is not easy to decide which one is more promising to use in which situation. In this work we propose a prediction mechanism to evaluate a set of different merging mechanisms at each layer during the construction of a relaxed BDD, in order to always select and apply the most promising heuristic. This prediction is implemented by either a perfect or by a k-layers lookahead construction of the BDD, gathering feature vectors for two competing merging heuristics which are then fed into a binary classifier. Models based on statistical tests and a feed-forward neural network are considered for the classifier. We study this approach for the maximum weighted independent set problem and in conjunction with a parameterized merging heuristic that takes also the similarity between states into account. We train and validate the binary classifiers on random graphs and finally test on weighted DIMACS instances. Results indicate that relaxed BDDs can be obtained whose upper bounds are on average up to ≈16% better than those of BDDs constructed with the sole use of minLP.