Variable Ordering for Decision Diagrams: A Portfolio Approach
Published in Constraints 2022, 2022
Recommended citation: Karahalios and van-Hoeve (2022). "Variable Ordering for Decision Diagrams." Constraints 2022. https://link.springer.com/article/10.1007/s10601-021-09325-6
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.