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.