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.

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