Dan Andrei Iancu - Stanford University

[Pages:213]Adaptive Robust Optimization with Applications in Inventory and Revenue Management

by

Dan Andrei Iancu

B.S., Yale University (2004) S.M., Harvard University (2006) Submitted to the Sloan School of Management in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Operations Research

at the MASSACHUSETTS INSTITUTE OF TECHNOLOGY

September 2010 c Massachusetts Institute of Technology 2010. All rights reserved.

Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sloan School of Management June 8, 2010

Certified by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Dimitris Bertsimas

Boeing Leaders for Global Operations Professor Thesis Supervisor

Certified by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pablo A. Parrilo Professor

Thesis Supervisor Accepted by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Patrick Jaillet Co-director, Operations Research Center

2

Adaptive Robust Optimization with Applications in

Inventory and Revenue Management

by

Dan Andrei Iancu

Submitted to the Sloan School of Management on June 8, 2010, in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Operations Research

Abstract

In this thesis, we examine a recent paradigm for solving dynamic optimization problems under uncertainty, whereby one considers decisions that depend directly on the sequence of observed disturbances. The resulting policies, called recourse decision rules, originated in Stochastic Programming, and have been widely adopted in recent works in Robust Control and Robust Optimization; the specific subclass of affine policies has been found to be tractable and to deliver excellent empirical performance in several relevant models and applications.

In the first chapter of the thesis, using ideas from polyhedral geometry, we prove that disturbance-affine policies are optimal in the context of a one-dimensional, constrained dynamical system. Our approach leads to policies that can be computed by solving a single linear program, and which bear an interesting decomposition property, which we explore in connection with a classical inventory management problem. The result also underscores a fundamental distinction between robust and stochastic models for dynamic optimization, with the former resulting in qualitatively simpler problems than the latter.

In the second chapter, we introduce a hierarchy of polynomial policies that are also directly parameterized in the observed uncertainties, and that can be efficiently computed using semidefinite optimization methods. The hierarchy is asymptotically optimal and guaranteed to improve over affine policies for a large class of relevant problems. To test our framework, we consider two problem instances arising in inventory management, for which we find that quadratic policies considerably improve over affine ones, while cubic policies essentially close the optimality gap.

In the final chapter, we examine the problem of dynamically pricing inventories in multiple items, in order to maximize revenues. For a linear demand function, we propose a distributionally robust uncertainty model, argue how it can be constructed from limited historical data, and show how pricing policies depending on the observed model misspecifications can be computed by solving second-order conic or semidefinite optimization problems. We calibrate and test our model using both synthetic data, as well as real data from a large US retailer. Extensive Monte-Carlo simulations show

3

that adaptive robust policies considerably improve over open-loop formulations, and are competitive with popular heuristics in the literature. Thesis Supervisor: Dimitris Bertsimas Title: Boeing Leaders for Global Operations Professor Thesis Supervisor: Pablo A. Parrilo Title: Professor

4

Acknowledgments

My deepest gratitude goes to my two advisers and mentors, Dimitris Bertsimas and Pablo Parrilo. It is hard to imagine this thesis without their insightful questions, shrewd suggestions, and perpetual patience and words of encouragement in tough times. Thank you, Dimitris and Pablo, for being a beacon of energy and inspiration, for guiding my steps well beyond the academic life, and for believing in me! I owe both of you a debt of gratitude larger than I can express here.

I was also extremely fortunate to have Georgia Perakis and Retsef Levi as my two other committee members. Apart from providing me with invaluable research feedback, they have been a continuous source of support and advice. Thank you, Georgia, for allowing me to be your teaching assistant (twice!), and for making the job-search process infinitely more tolerable with your incredible kindness and warm thoughts! Thank you, Retsef, for teaching me everything I know about inventory management, and for your candid comments about research and academia in general.

I am also indebted to Rama Ramakrishnan for his support in obtaining the data set used in the last chapter of the dissertation, and for sharing his extensive industry experience and insights.

My academic life was also shaped by numerous wonderful teachers - in particular, I would like to acknowledge Aharon Ben-Tal and Andreas Schulz, for lecturing three of the best classes in optimization that I have every taken, and Paul Flondor, Ana Ni?ta, Liliana Mihaila, and Mihaela Popa, for nurturing my early interests in mathematics and physics.

During my four years at MIT, the Operations Research Center has undoubtedly been a "home away from home". The co-directors - Cindy Barnhart and Dimitris Bertsimas - have been great managers, considerate and mindful of all issues pertaining to student life, while the administrative staff - Paulette Mosley, Laura Rose and Andrew Carvalho - have always made sure the center runs smoothly, and the students have everything they need to focus on work. However, by far, the best thing about the ORC has been the wonderful group of colleagues and friends, with whom I have

5

shared many hours of work and fun, alike - Thibault Leguen, Diana Michalek, Martin Quinteros, Jason Acimovic, Jonathan Kluberg, Adrian Becker, Alex Rikun, Gareth Williams, David Goldberg, and Andy Sun. I was also lucky to forge strong friendships with Ilan and Ruben Lobel, Premal Shah, Margr?et Bjarnad?ottir, Doug Fearing, Th?eo Weber, Parikshit Shah and Amir-Ali Ahmadi. A special debt of gratitude is due to my two best friends and colleagues in the ORC, Nikos Trichakis and Kostas Bimpikis - thank you both for being a great support in dire times, and joyful company in good times!

Life in the Cambridge and Boston area would certainly have been radically different, had it not been for the Romanian students at Harvard and MIT. Throughout the six years that we have spent together, they have become some of my closest and dearest friends, and simply mentioning their names does not do justice for all the wonderful moments we spent together. Thank you, Emma Voinescu, Cristi Jitianu, Emanuel Stoica, Florin Moro?san, Florin Constantin, S?tefan Horne?t, Alex Salcianu, Daniel Nedelcu and Cristi Boboila!

Last, but most certainly not least, I would like to thank my parents, my grandparents, and my girlfriend, Laura. Their tireless and unconditional love, support, and encouragement has kept me going through the toughest of times, and I owe them more than I could ever express here. To them I dedicate this thesis.

6

Contents

1 Introduction

17

2 Optimality of Disturbance-Affine Policies

27

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.1.1 Notation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.2 Dynamic Programming Solution. . . . . . . . . . . . . . . . . . . . . 33

2.3 Optimality of Affine Policies in the History of Disturbances. . . . . . 35

2.4 Proof of Main Theorem. . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.4.1 Induction Hypothesis. . . . . . . . . . . . . . . . . . . . . . . 39

2.4.2 Construction of the Affine Control Law. . . . . . . . . . . . . 50

2.4.3 Construction of the Affine State Cost. . . . . . . . . . . . . . 59

2.4.4 Proof of Main Theorem. . . . . . . . . . . . . . . . . . . . . . 72

2.4.5 Counterexamples for potential extensions. . . . . . . . . . . . 73

2.5 An application in inventory management. . . . . . . . . . . . . . . . . 76

2.5.1 Capacity Commitment and Negotiation. . . . . . . . . . . . . 78

3 A Hierarchy of Near-Optimal Polynomial Policies in the Distur-

bances

81

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

3.1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

3.3 Polynomial Policies and Convex Reformulations Using Sums-Of-Squares 91

3.3.1 Reformulating the Constraints . . . . . . . . . . . . . . . . . . 92

7

3.3.2 Reformulating the Objective . . . . . . . . . . . . . . . . . . . 94 3.3.3 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.4 Other Methodologies for Computing Decision Rules or Exact Values . 100 3.4.1 Affine and Quadratic Policies for -Ellipsoidal Uncertainty Sets 101 3.4.2 Determining the Optimal Value for Polytopic Uncertainties . . 104 3.5 Examples from Inventory Management . . . . . . . . . . . . . . . . . 107 3.5.1 Single Echelon with Cumulative Order Constraints . . . . . . 107 3.5.2 Serial Supply Chain . . . . . . . . . . . . . . . . . . . . . . . . 109 3.6 Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3.6.1 First Example . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 3.6.2 Second Example . . . . . . . . . . . . . . . . . . . . . . . . . 112

4 Polynomial Policies for Multi-Item Dynamic Pricing

117

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

4.1.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

4.2 Model Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

4.2.1 Demand Model . . . . . . . . . . . . . . . . . . . . . . . . . . 121

4.2.2 Model Uncertainties and Preferences Over Uncertain Outcomes 125

4.2.3 Complete Formulation . . . . . . . . . . . . . . . . . . . . . . 126

4.3 Polynomial Policies and Tractable Robust Reformulations . . . . . . . 128

4.3.1 Reformulating the Objective . . . . . . . . . . . . . . . . . . . 130

4.3.2 Other Methods for Solving the Problem . . . . . . . . . . . . 136

4.4 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

4.4.1 Multiplicative Disturbances . . . . . . . . . . . . . . . . . . . 139

4.4.2 Exponential (or Log-Linear) Demand Model with Multiplica-

tive Noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

4.5 Calibrating the Models from Real Data . . . . . . . . . . . . . . . . . 145

4.5.1 Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

4.5.2 Demand Model Estimation and Calibration . . . . . . . . . . 149

4.5.3 Estimating the Model for the Uncertainties . . . . . . . . . . . 152

8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download