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

by: Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham

Principles and Practice of Constraint Programming - CP 2002 (2002), pp. 91-100.

View FullText article

Reviews [Write a review of this article]

There are no reviews of this article

Notes for this article

bsilverthorn has 1 private note и ещё 0 public notes for this article. If you are bsilverthorn then you can log in to see the private note.

Find related articles from these CiteULike users

bsilverthorn

Find related articles with these CiteULike tags

algorithm_behavior, empirical_hardness

Abstract

We propose a new approach for understanding the algorithm-specific empirical hardness of $$ \mathcalN\mathcalP $$ -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.

@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}, 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} }

RIS record

TY - CHAP ID - citeulike:2705087 L3 - citeulike-article-id:2705087 TI - Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions JF - Principles and Practice of Constraint Programming - CP 2002 SP - 91 EP - 100 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. 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 -

RIS BibTeX