Variable Ordering for Decision Diagrams: A Portfolio Approach

Published in CPAIOR 2021, 2021

Recommended citation: Karahalios and van-Hoeve (2021). "Variable Ordering for Decision Diagrams." CPAIOR 2021. https://www.andrew.cmu.edu/user/vanhoeve/papers/DD_Portfolio_CPAIOR2021.pdf

Abstract. Relaxed decision diagrams have been successfully applied to solve combinatorial optimization problems, but their performance is known to strongly depend on the variable ordering. We propose a port- folio approach to selecting the best ordering among a set of alternatives. We consider several different portfolio mechanisms: an offline predic- tive model of the single best algorithm using classifiers, an online low- knowledge algorithm selection, a static uniform time-sharing portfolio, and a dynamic online time allocator. As a case study, we compare and contrast their performance on the graph coloring problem. We find that on this problem domain, the dynamic online time allocator provides the best overall performance.

#Download paper here