Auction optimization using regression trees and linear models as integer programs
From MaRDI portal
Publication:511796
DOI10.1016/J.ARTINT.2015.05.004zbMATH Open1404.68122arXiv1401.1061OpenAlexW1557734215MaRDI QIDQ511796FDOQ511796
Sicco Verwer, Qing Chuan Ye, Yingqian Zhang
Publication date: 22 February 2017
Published in: Artificial Intelligence (Search for Journal in Brave)
Abstract: In a sequential auction with multiple bidding agents, it is highly challenging to determine the ordering of the items to sell in order to maximize the revenue due to the fact that the autonomy and private information of the agents heavily influence the outcome of the auction. The main contribution of this paper is two-fold. First, we demonstrate how to apply machine learning techniques to solve the optimal ordering problem in sequential auctions. We learn regression models from historical auctions, which are subsequently used to predict the expected value of orderings for new auctions. Given the learned models, we propose two types of optimization methods: a black-box best-first search approach, and a novel white-box approach that maps learned models to integer linear programs (ILP) which can then be solved by any ILP-solver. Although the studied auction design problem is hard, our proposed optimization methods obtain good orderings with high revenues. Our second main contribution is the insight that the internal structure of regression models can be efficiently evaluated inside an ILP solver for optimization purposes. To this end, we provide efficient encodings of regression trees and linear regression models as ILP constraints. This new way of using learned models for optimization is promising. As the experimental results show, it significantly outperforms the black-box best-first search in nearly all settings.
Full work available at URL: https://arxiv.org/abs/1401.1061
Recommendations
Learning and adaptive systems in artificial intelligence (68T05) Auctions, bargaining, bidding and selling, and other market models (91B26) Integer programming (90C10)
Cites Work
- Efficient global optimization of expensive black-box functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Pattern recognition and machine learning.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Supervised classification and mathematical optimization
- Budget-constrained sequential auctions with incomplete information
- The Importance of Ordering in Sequential Auctions
- Bilinear separation of two sets in \(n\)-space
- Title not available (Why is that?)
- A mixed-integer programming approach to multi-class data classification problem
- Using bid data for the management of sequential, multi-unit, online auctions with uniformly distributed bidder valuations
- Derivative-free optimization: a review of algorithms and comparison of software implementations
- Synergies between operations research and data mining: the emerging use of multi-objective approaches
- Title not available (Why is that?)
- Title not available (Why is that?)
- Exact DFA Identification Using SAT Solvers
- Synergies of operations research and data mining
- Multiple-object auctions with budget constrained bidders
- Survey of modeling and optimization strategies to solve high-dimensional design problems with computationally-expensive black-box functions
- Structured learning with constrained conditional models
- Optimization and analysis aid via data-mining for simulated production systems
- Surrogate-Based Methods
- A Smart Market for Industrial Procurement with Capacity Constraints
- Title not available (Why is that?)
- Discovering dispatching rules using data mining
Cited In (12)
- Mathematical optimization in classification and regression trees
- Injecting domain knowledge in neural networks: a controlled experiment on a constrained problem
- Classifier-based constraint acquisition
- Optimal randomized classification trees
- On optimal regression trees to detect critical intervals for multivariate functional data
- Learning decision trees with flexible constraints and objectives using integer optimization
- Column generation based heuristic for learning classification trees
- Sparsity in optimal randomized classification trees
- Optimization problems for machine learning: a survey
- Data driven design for online industrial auctions
- Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded
- Black-box combinatorial optimization using models with integer-valued minima
Uses Software
This page was built for publication: Auction optimization using regression trees and linear models as integer programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511796)
