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

@incollection{citeulike:2705087, abstract = {We propose a new approach for understanding the algorithm-specific empirical hardness of \$\$ \mathcal{N}\mathcal{P} \$\$ -Hard problems. In this work we focus on the empirical hardness of the winner determination problem—an optimization problem arising in combinatorial auctions—when solved by ILOG's CPLEX software. We consider nine widely-used problem distributions and sample randomly from a continuum of parameter settings for each distribution. We identify a large number of distribution-nonspecific features of data instances and use statistical regression techniques to learn, evaluate and interpret a function from these features to the predicted hardness of an instance.}, author = {Leyton-Brown, Kevin and Nudelman, Eugene and Shoham, Yoav}, citeulike-article-id = {2705087}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/3-540-46135-3_37}, doi = {10.1007/3-540-46135-3_37}, journal = {Principles and Practice of Constraint Programming - CP 2002}, keywords = {algorithm\_behavior, empirical\_hardness}, pages = {91--100}, posted-at = {2008-04-23 03:19:11}, priority = {0}, title = {Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions}, url = {http://dx.doi.org/10.1007/3-540-46135-3_37}, year = {2002} }

TY - CHAP ID - citeulike:2705087 L3 - citeulike-article-id:2705087 N2 - We propose a new approach for understanding the algorithm-specific empirical hardness of $$ \mathcal{N}\mathcal{P} $$ -Hard problems. In this work we focus on the empirical hardness of the winner determination problem—an optimization problem arising in combinatorial auctions—when solved by ILOG’s CPLEX software. We consider nine widely-used problem distributions and sample randomly from a continuum of parameter settings for each distribution. We identify a large number of distribution-nonspecific features of data instances and use statistical regression techniques to learn, evaluate and interpret a function from these features to the predicted hardness of an instance. JF - Principles and Practice of Constraint Programming - CP 2002 EP - 100 TI - Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions SP - 91 KW - algorithm_behavior KW - empirical_hardness AU - Leyton-Brown, Kevin AU - Nudelman, Eugene AU - Shoham, Yoav PY - 2002/// UR - http://dx.doi.org/10.1007/3-540-46135-3_37 ER -