2002 | OriginalPaper | Buchkapitel
Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions
verfasst von : Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham
Erschienen in: Principles and Practice of Constraint Programming - CP 2002
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose a new approach for understanding the algorithm-specific empirical hardness of -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.