Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions

By Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham. 2002

213 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Marketing

How researchers see this paper

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

In Artificial Intelligence

In Management Science and Operations Research

In Marketing

Citations in the corpus

Taking the Human Out of the Loop: A Review of Bayesian Optimization (2016, methodology): “With only K arms, we can fully describe the function f with a parameter w ∈ (0 , 1) K so that f w ( a ) := w a .”
ParamILS: An Automatic Algorithm Configuration Framework (2014, background): “For approaches that try to choose the best algorithm on a per-instance basis, see (Leyton-Brown et al., 2002; Carchrae and Beck, 2005; Gebruers et al., 2005; Gagliolo and Schmidhuber, 2006; Xu et al., 2008).”
Bayesian Optimization with an Empirical Hardness Model for approximate Nearest Neighbour Search (2014, methodology): “We also propose a novel procedure to speed up the optimization process: by learning an extended Empirical Hardness Model (EHM) [11] offline, we obtain a proxy to the target function, whose evaluation can be bypassed depending on the quality of the EHM.”
SATzilla: Portfolio-based Algorithm Selection for SAT (2008, methodology): “this paper, we use the same ridge regression method that has previously proven to be very successful in predicting runtime on uniform random k-SAT, on structured SAT instances, and on combinatorial auction winner determination problems (Nudelman et al., 2004a; Hutter et al., 2006; Leyton-Brown et al”
Identifying Key Algorithm Parameters and Instance Features Using Forward Selection (2013, methodology): “to determine the importance of instance features [17], which is originally due to [31]: we simply drop one input from S at a time and measure the increase in predictive RMSE.”
Run the GAMUT: a comprehensive approach to evaluating game-theoretic algorithms (2004, unknown): “when problem size is held constant [9].”
Automated configuration of algorithms for solving hard computational problems (2009, background): “Transformations that have been suggested in the literature include log transformations (Jones et al., 1998; Williams et al., 2000; Huang et al., 2006; Leyton-Brown et al., 2002), negative inverse transformations (Jones et al.”
Automated Algorithm Selection: Survey and Perspectives (2018, methodology): “…2003 and SAT ZILLA 2007 lies in the regression models used for the main algorithm selection phase: While the former used empirical hardness models (Leyton-Brown et al., 2002) based on ridge regression (see, e.g., Bishop, 2006), the latter employed hierarchical hardness models (Xu et al., 2007),…”
Sequential Model-Based Optimization for General Algorithm Configuration (2011, background): “These general MIP features have been introduced in [11] as a generalization of features for the combinatorial winner determination problem in [32].”
Algorithm Selection for Combinatorial Search Problems: A Survey (2012, background): “The organisation of this paper follows the main criteria below.”
Boosting as a Metaphor for Algorithm Design (2003, methodology): “Our previous work [7] demonstrates that statistical regres sion can be used to learn surprisingly accurate models of an algorithm’s runtime.”
Algorithm runtime prediction: Methods & evaluation (2012, methodology): “…predictive performance in most scenarios we studied, this is the method that has been used most frequently in the past for building EPMs [26,45, 75,76,90,50,115 Ridge regression works as follows Let X and y be as deﬁned above, let I p be the p × p identity matrix, and let (cid:7) be a small…”