Auction optimization using regression trees and linear models as integer programs

By Sicco Verwer, Yingqian Zhang, Qing Chuan Ye. 2014

63 citations recorded by the source corpus.

Abstract In a sequential auction with multiple bidding agents, the problem of determining the ordering of the items to sell in order to maximize the expected revenue is highly challenging. The challenge is largely 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 regression 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.

Subfields: Artificial Intelligence, Management Science and Operations Research

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

Citations in the corpus

Learning Optimal Classification Trees Using a Binary Linear Program Formulation (2019, methodology): “This power has led to interesting new approaches for learning models and rules, see e.g., (Bessiere, Hebrard, and OSullivan 2009; De Raedt, Guns, and Nijssen 2010; Narodytska et al. 2018; Verwer, Zhang, and Ye 2017).”
Optimal randomized classification trees (2021, methodology): “This is the approach followed in recent papers such as [46, 47, 48, 49], which consider mixed-integer formulations.”
Optimization Models for Machine Learning: A Survey (2019, unknown): “More generally, splits that span multiple variables can also be considered at each node as presented in [37, 205, 206].”
Learning Decision Trees with Flexible Constraints and Objectives Using Integer Optimization (2017, methodology): “In contrast to earlier decision tree encodings (e.g. [ 1], [4], [16]), we therefore encode the leaf every data row ends up in using a binary instead of a unary encoding, i.e., using k variables instead of 2 k .”
Constructing classification trees using column generation (2018, methodology): “In recent years, constructing decision trees by using mathematical programming techniques, especially Integer Optimization, became a hot topic among researchers (see Menickelly et al. (2016), Verwer et al. (2017), Bertsimas and Dunn (2017), Verwer and Zhang (2017), and Dash et al. (2018)).”
A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees (2020, methodology): “For solving S1O and OCT-H, we use the decision tree trained using CART as a warm start solution for CPLEX, as in [Bertsimas and Dunn, 2017, Verwer et al., 2017].”
Sparsity in Optimal Randomized Classification Trees (2020, unknown): “trees would find it difficult, such as preferences on the classification performance in some class where misclassifying is more damaging [6, 37, 38], or controlling the number of predictor variables used along the tree (local and global sparsity).”
Column generation based heuristic for learning classification trees (2020, background): “[36], Bertsimas and Dunn [3], Verwer and Zhang [35], and Dash et al.”