ISAC - Instance-Specific Algorithm Configuration

By Serdar Kadioğlu, Yuri Malitsky, Meinolf Sellmann, Kevin Tierney. 2010

285 citations recorded by the source corpus.

We present a new method for instance-specific algorithm configuration (ISAC). It is based on the integration of the algorithm configuration system GGA and the recently proposed stochastic offline programming paradigm. ISAC is provided a solver with categorical, ordinal, and/or continuous parameters, a training benchmark set of input instances for that solver, and an algorithm that computes a feature vector that characterizes any given instance. ISAC then provides high quality parameter settings for any new input instance. Experiments on a variety of different constrained optimization and constraint satisfaction solvers show that automatic algorithm configuration vastly outperforms manual tuning. Moreover, we show that instance-specific tuning frequently leads to significant speed-ups over instance-oblivious configurations.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

Citations in the corpus

Optimal Decision Trees for the Algorithm Selection Problem: Integer Programming Based Approaches (2019, methodology): “An intermediate approach was proposed by Kadioglu et al. (2010): initially the instance set is divided into clusters and then the parameter settings search begin.”
Automated Algorithm Selection: Survey and Perspectives (2018, methodology): “Notably, Kadioglu et al. (2010) proposed a PIAC approach based on a combination of clustering and a standard, per-set algorithm conﬁgurator and reported promising results on several set covering, mixed integer programming and propositional satisﬁability algorithms.”
Hydra-MIP : Automated Algorithm Configuration and Selection for Mixed Integer Programming (2011, methodology): “Specifically, for ISAC(new) we used the six configurations found by GGA in [17].”
Instance-Specific Algorithm Configuration (2014, methodology): “The next configuration[53] built off the first attempt, streamlining each part of the ISAC procedure.”
Algorithm runtime prediction: Methods & evaluation (2012, background): “Such predictions can be used to make a per-instance decision about which of a set of given parameter configurations will perform best on a previously unseen test instance, for example in algorithm selection [104,119,116,67].”
Alors: An algorithm recommender system (2017, background): “…2003; Epstein et al., 2006; Samulowitz and Memisevic, 2007; Xu et al., 2008),(O´Mahony et al., 2008; Hutter et al., 2009; Pulina and Tacchella, 2010; Kadioglu et al., 2010; Xu et al., 2012a; Malitsky et al., 2013; Malitsky and O´ Sullivan, 2014; Lindauer et al., 2015), meta-learning and…”
Efficient Parameter Importance Analysis via Ablation with Surrogates (2017, methodology): “Furthermore, when applied to heterogeneous instance sets, ablation could be combined with ISAC (Kadioglu et al. 2010).”
Algorithm Selection for Combinatorial Search Problems: A Survey (2012, methodology): “They are used in practice in the Algorithm Selection systems Hydra and ISAC, respectively.”
Efficient Benchmarking of Algorithm Configuration Procedures via Model-Based Surrogates (2017, methodology): “Thus, feature extractors are available for many problems, including mixed integer programming (MIP; Leyton-Brown et al 2009; Kadioglu et al 2010; Xu et al 2011; Hutter et al 2014b), propositional satisfiability (SAT; Nudelman et al 2004; Xu et al 2008; Hutter et al 2014b), answer set programming…”