Search

Optimization has been one of the most fundamental and extensive contributions of management science/operations research, with an enormous number of contributions and subfields developed by many researchers and practitioners. When the journal Management Science launched in 1954, little was known about optimization, including some results in nonlinear optimization and the simplex method and duality developed for linear programming. However, linear programming computations were limited to problems with at most 101 linear constraints. Then some early contributions by seminal researchers began to develop foundations for the field. I will review a few of these early contributions, focusing on the traveling sales problem and integer programming, decomposition, and column generation. I will summarize some research and applied contributions since then, including the enormous development of computations. I will focus on linear and integer programs with some material on combinatorial optimization. This paper was accepted by David Simchi-Levi, Special Section of Management Science: 65th Anniversary.

We study the problem of computing data-driven personalized reserve prices in eager second price auctions without having any assumption on valuation distributions. Here, the input is a data set that contains the submitted bids of n buyers in a set of auctions, and the problem is to return personalized reserve prices r that maximize the revenue earned on these auctions by running eager second price auctions with reserve r. For this problem, which is known to be NP complete, we present a novel linear program (LP) formulation and a rounding procedure, which achieves a 0.684 approximation. This improves over the [Formula: see text]-approximation algorithm from Roughgarden and Wang. We show that our analysis is tight for this rounding procedure. We also bound the integrality gap of the LP, which shows that it is impossible to design an algorithm that yields an approximation factor larger than 0.828 with respect to this LP. This paper was accepted by Chung Piaw Teo, Management Science Special Section on Data-Driven Prescriptive Analytics.

A stochastic bound is a portfolio that stochastically dominates all alternatives in a reference portfolio set instead of a single alternative portfolio. An approximate bound is a portfolio that comes as close as possible to this ideal. To identify and analyze exact or approximate bounds, feasible approaches to numerical optimization and statistical inference are developed based on linear programming and subsampling. The use of reference sets and stochastic bounds is shown to improve investment performance in representative applications to enhanced benchmarking using equity industry rotation and equity index options combinations. This paper was accepted by Kay Giesecke, finance.

Optimization applications often depend on a huge number of uncertain parameters. In many contexts, however, the amount of relevant data per parameter is small, and hence, we may only have imprecise estimates. We term this setting—in which the number of uncertainties is large but all estimates have low precision—the small-data, large-scale regime. We formalize a model for this new regime, focusing on optimization problems with uncertain linear objectives. We show that common data-driven methods, such as sample average approximation, data-driven robust optimization, and certain regularized policies, may perform poorly in this new setting. We then propose a novel framework for selecting a data-driven policy from a given policy class. As with the aforementioned data-driven methods, our new policy enjoys provably good performance in the large-sample regime. Unlike these methods, we show that in the small-data, large-scale regime, our data-driven policy performs comparably to an oracle best-in-class policy under some mild conditions. We strengthen this result for linear optimization problems and two natural policy classes, the first inspired by the empirical Bayes literature and the second by regularization techniques. For both classes, the suboptimality gap between our proposed policy and the oracle policy decays exponentially fast in the number of uncertain parameters even for a fixed amount of data. Thus, these policies retain the strong large-sample performance of traditional methods and additionally enjoy provably strong performance in the small-data, large-scale regime. Numerical experiments confirm the significant benefits of our methods. This paper was accepted by Yinyu Ye, optimization.