Information Technology Reference
In-Depth Information
3.5 Scheduling problem
In (Kadioglu et al., 2011) the main idea is taken from an algorithm selector called Boolean
Satisfiability (SAT) based on nearest neighbor classifier. On one hand, authors presented
two extensions to it; one of them is based on the concept of distance-based weighting, where
they assign larger weights to instances that are closer to the test instance. The second
extension, is based on clustering-based adaptive neighborhood size, where authors adapt
the size of the neighborhood based on the properties of the given test instance. These two
extensions show moderate but consistent performance improvements to the algorithm
selection using Nearest-Neighbor Classification (Malitsky et al., 2011). On the other hand,
authors developed a new hybrid portfolio that combines algorithm selection and algorithm
scheduling, in static and dynamic ways. For static schedules the problem can be formulated
as an integer program, more precisely, as a resource constrained set covering problem,
where the goal is to select a number of solver-runtime pairs that together “cover” (i.e., solve)
as many training instances as possible. Regarding dynamic schedules, the column
generation approach works fast enough when yielding potentially sub-optimal but usually
high quality solutions. This allows us to embed the idea of dynamic schedules in the
previously developed nearest-neighbor approach, which selects optimal neighborhood sizes
by random sub-sampling validation. With SAT as the testbed, experimentation
demonstrated that author's approach can handle highly diverse benchmarks, in particular a
mix of random, crafted, and industrial SAT instances, even when deliberately removed
entire families of instances from the training set. As a conclusion, authors presented a
heuristic method for computing solver schedules efficiently, which O'Mahony (O'Mahony
et al., 2008) identified as an open problem. In addition, they showed that a completely new
way of solver scheduling consisting of a combination of static schedules and solver selection
is able to achieve significantly better results than plain algorithm selection.
3.6 Traveling salesman problem
In (Kanda et al., 2011), the work is focused in the selection of optimization algorithms for
solving TSP instances; this paper proposes a meta-learning approach to recommend
optimization algorithms for new TSP instances. Each instance is described by meta-features
of the TSP that influences the efficiency of the optimization algorithms. When more than one
algorithm reaches the best solution, the multi-label classification problem is addressed
applying three steps: 1) decomposition of multi-label instances into several single-label
instances, 2) elimination of multi-label instances, and 3) binary representation, in order to
transform multi-label instances into several binary classification problems. Features were
represented as a graph. The success of this meta-learning approach depended on the correct
identification of the meta-features that best relate the main aspects of a problem to the
performances of the used algorithms. Finally the authors claimed that it is necessary to
define and expand the set of metafeatures, which are important to characterize datasets in
order to improve the performance of the selection models.
3.7 Satisfiability problem
In (Xu et al., 2009) is described an algorithm for constructing per-instance algorithm
portfolios for SAT. It has been widely observed that there is no single “dominant” SAT
solver; instead, different solvers perform best on different instances. SATzilla is an
