Name
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 portfolio approach to selecting the best ordering among a set of alternatives. We consider several different portfolio mechanisms: a static uniform time-sharing portfolio, an offline predictive model of the single best algorithm using classifiers, a low-knowledge algorithm selection, 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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/s10601-021-09325-6 | Constraints |
Keywords | DocType | Volume |
Decision diagrams, Graph coloring, Variable ordering | Journal | 27 |
Issue | ISSN | Citations |
1 | 1383-7133 | 0 |
PageRank | References | Authors |
0.34 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anthony Karahalios | 1 | 0 | 0.34 |
| Willem Jan Van Hoeve | 2 | 517 | 39.54 |