Relaxed decision diagrams have recently been successfully applied within a range of solution methodologies for discrete optimization, including constraint programming, integer linear programming, integer nonlinear programming, and combinatorial optimization. The variable ordering is often of crucial importance for their effectiveness. For example, Bergman et al. [1, 2] demonstrate that a variable ordering that yields a small exact diagram typically also provides stronger dual bounds from the relaxed diagram. When decision diagrams are built from a single top-to-bottom compilation, dynamic variable orderings can be very effective. For example, a recent work by Cappart et al. [3J deploys deep reinforcement learning to dynamically select the next variable during compilation. Dynamic variable orderings are less applicable, however, to compilation via iterative refinement, in which case the ordering must be specified in advance. In this work, we consider variable ordering strategies for the latter case. Oftentimes there is no single variable ordering strategy that dominates all others for a given set of problem instances. Selecting the best ordering, or more generally the best algorithm, from a set of alternatives is a well-studied problem in artificial intelligence, in the context of algorithm portfolios. There are several ways to construct an algorithm portfolio: using static or dynamic features, formulating predictive models at the algorithm or portfolio level, predicting one algorithm to run per instance or creating a schedule of algorithms to run, using a fixed portfolio or updating it online [4]. We consider several different portfolio mechanisms: an offline predictive 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 consider the graph coloring problem, for which a decision diagram approach was recently introduced [5, 6]. It uses an iterative refinement procedure much like Benders decomposition or lazy-clause generation, by repeatedly refining conflicts in the diagram until the solution is conflict free. Our experimental results show that predictive methods using classification models or exploration phases can lead to more instances solved optimally. However, these methods may lead to delayed optimality results on problem instances that are easy to solve. Another insight is that a mixed portfolio can outperform a clairvoyant selection of the best individual ordering for each instance, by yielding a solution with a unique best upper bound from one ordering and a unique best lower bound from a different ordering.
展开▼
