Chair: Daniel Kuhn, EPFL, Switzerland
Robust Vehicle Routing
Wolfram Wiesemann (firstname.lastname@example.org), Chrysanthos Gounaris (email@example.com), Christodoulos Floudas (firstname.lastname@example.org )
We study the robust capacitated vehicle routing problem (robust CVRP), which asks for the minimum cost delivery of a product to geographically dispersed customers using capacity-constrained vehicles. Contrary to the deterministic CVRP, which postulates that the customer demands for the product are deterministic and known, the robust CVRP models the customer demands as random variables, and it determines a minimum cost delivery plan that is feasible for all anticipated demand realizations. We show that the robust CVRP can be modelled as a two-stage robust optimization problem that has an equivalent reformulation as a mixed-integer linear program (MILP). We generalize the classical rounded capacity inequalities to the robust setting and illustrate how they expedite the solution of the MILP in a branch-and-cut framework. We also discuss how the robust CVRP relates to the chance-constrained CVRP, which allows a controlled degree of supply shortfall to decrease delivery costs.
Keywords: Robust optimization, vehicle routing, integer programming
Data-driven learning in dynamic pricing using adaptive optimization
Phebe Vayanos (email@example.com), Dimitris Bertsimas (firstname.lastname@example.org)
We consider the pricing problem faced by a retailer endowed with a finite inventory of a single product offered over a finite planning horizon in an environment where customers are price-sensitive. The parameters of the product demand curve, which maps prices to nominal demand rates, are fixed but initially unknown to the seller who only has at his disposal a history of sales data. We propose an adaptive optimization approach to setting prices that captures the ability of the seller to exploit information gained as a byproduct of pricing in his quest to maximize revenues. We embrace the robust optimization approach to uncertainty modeling and encode the beliefs of the retailer about the demand function parameters in terms of an uncertainty set. We define this set as the set of all parameters that are compatible with the model and unfalsified by the data. We capture the ability of the retailer to explore the characteristics of customer behavior by allowing the uncertainty set to depend on the pricing decisions. We model his capacity to exploit the information dynamically acquired by letting the pricing decisions adapt to the history of observations. The resulting adaptive problem with decision-dependent uncertainty set does not allow for a direct solution. We propose an approximation scheme inspired from techniques that are commonly used in modern robust optimization. In particular, we obtain a conservative approximation in the form of mixed-binary conic optimization problem that is practically tractable following a reduction of the information and decision spaces. The performance of our approach is evaluated using numerical computation. Variants and extensions of the basic model that incorporate multiple products and inventory decisions are suggested, illustrating the versatility of the proposed method.
Keywords: Tactical dynamic pricing, exploration-exploitation, adjustable robust optimization
Robust Growth-Optimal Portfolios
Napat Rujeerapaiboon (email@example.com), Daniel Kuhn (firstname.lastname@example.org), Wolfram Wiesemann (email@example.com)
The growth-optimal portfolio is designed to have maximum expected log return over the next rebalancing period. Thus, it can be computed with relative ease by solving a static optimization problem. The growth-optimal portfolio has sparked fascination among finance professionals and researchers because it can be shown to outperform any other portfolio with probability 1 in the long run. In the short run, however, it is notoriously volatile. Moreover, its computation requires precise knowledge of the asset return distribution, which is not directly observable but must be inferred from sparse data. By using methods from distributionally robust optimization, we design fixed-mix strategies that offer similar performance guarantees as the growth-optimal portfolio but for a finite investment horizon and for a whole family of distributions that share the same first and second-order moments. We demonstrate that the resulting robust growth-optimal portfolios can be computed efficiently by solving a tractable conic program whose size is independent of the length of the investment horizon. Simulated and empirical backtests show that the robust growth-optimal portfolios are superior to the classical growth-optimal portfolio across most realistic investment horizons and for an overwhelming majority of contaminated return distributions.
Keywords: Portfolio optimization, Distributionally robust optimization, Convex optimization