.
Procurement Strategies of a Commodity with a Spot Market by Mustafa G ok cen G oksel A Dissertation Submitted to the Graduate School of Sciences and Engineering in Partial Ful llment of the Requirements for the Degree of Master of Science in Industrial Engineering August 11, 2017 Procurement Strategies of a Commodity with a Spot Market Ko c University Graduate School of Sciences and Engineering This is to certify that I have examined this copy of a master's thesis by Mustafa G ok cen G oksel and have found that it is complete and satisfactory in all respects, and that any and all revisions required by the nal examining committee have been made. Committee Members: Prof. Fikri Karaesmen Prof. G urhan K ok Asst. Prof. Bora C ekyay Date: Dedicated to my late grandfather. iii ABSTRACT We investigated the single period procurement policy of a commodity which is traded in a spot market. The presence of a spot market di erentiates the problem de nition from the classical single period inventory models, and requires di erent solution strategies. We have proposed two datadriven linear programs to nd the optimal procurement strategies for two di erent objectives: (i) expected pro t maxi mization (riskneutral), (ii) minimization of CVaR (riskaverse). Our proposed solu tion approaches use historical demand and price data as well as the historical data of exogenous variables which are assumed to be correlated with demand and/or price. We have conducted a simulation to ensure the validity of the models. According to the simulation results, the riskneutral case is able to yield nearoptimal solutions for all price processes and all pricedemand dependence cases. The riskaverse model is able to outperform the riskneutral one in terms of CVaR risk measure for certain cases of price processes and pricedemand dependence cases. The presence of the exogenous variables improved the performance of both programs. iv OZETC E Spot piyasas bulunan emtialar n tek d onemlik sat n alma politikalar n inceledik. Spot piyasas n n varl g , problem tan m n di ger tek d onemlik envanter modellerinden ay rmaktad r ve bu sebeple daha farkl c oz um stratejileri gerektirir. Beklenen kar mak simizasyonu (riske n otr) ve CVaR minimizasyonu (riskten ka c nan) olmak uzere iki farkl amaca y onelik optimal sat n alma stratejilerini belirlemek ad na iki veri g ud uml u do grusal program oneriyoruz. Onerdi gimiz c oz um yakla s m , ge cmi s talep ve yat verilerini, ayr ca talep ve yat ile aralar nda bir korelasyon oldu gu varsay lan ge cmi s d ssal de gi sken verilerini de kullanmaktadr. Modellerin ge cerlili ginden emin olmak i cin bir sim ulasyon ger cekle stirdik. Sim ulasyon sonu clar na g ore, riske n otr durum, t um yat s ure clerinde ve yat ve talebin birbirine ba gl oldu gu durumlarda optimale yak n c oz umler uretebilmektedir. Riskten ka c nan model ise belirli yat s ure clerinde ve yat ve talebin birbirine ba gl oldu gu durumlarda CVaR risk ol c umlerinde riske n otr durumdan daha iyi performans g ostermi stir. Ayr ca, d ssal de gi skenlerin varl g programlar n performans n y ukseltmi stir. v ACKNOWLEDGMENTS First and foremost, I would like to express my sincere gratitude to my thesis advisor Prof. Fikri Karaesmen for his guidance and support in the last two years. He has guided me through the process of writing my thesis and provided valuable advice whenever I needed it. This being said, I am most grateful for his sincere attitude and unwavering positive mood. Additionally, I would like to thank my committee members Prof. G urhan K ok and, Asst. Prof. Bora C ekyay for their interest in my work. I would like to acknowledge all faculty members of Ko c University for their involve ment in my learning process both during my undergraduate and graduate studies. And last but not least, I would like to thank my family and friends for their unconditional support and endless patience. vi TABLE OF CONTENTS List of Tables ix List of Figures xvii Nomenclature xix Chapter 1: Introduction 1 Chapter 2: Literature Review and Background 5 2.1 Conditional ValueatRisk . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Newsvendor Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Newsvendor Problem with Risk Consideration . . . . . . . . . 9 2.2.2 Newsvendor Problem with PriceDemand Dependence . . . . . 11 2.3 DataDriven Optimization . . . . . . . . . . . . . . . . . . . . . . . . 13 Chapter 3: Singleperiod Procurement Policy via DataDriven LP 18 3.1 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Maximization of Expected Pro t . . . . . . . . . . . . . . . . . . . . 20 3.2.1 Theoretical Solution for No Feature Case . . . . . . . . . . . . 20 3.2.2 [Ban and Rudin, 2014], DataDriven Linear Programming Ap proach for the Newsvendor Problem . . . . . . . . . . . . . . 22 3.2.3 Mathematical Model for Maximization of Expected Pro t . . 23 3.3 Minimization of CVaR . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.1 Price Process Settings . . . . . . . . . . . . . . . . . . . . . . 32 vii 3.4.2 Demand Settings . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4.3 Feature Set Settings . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.4 Parameters Array Selection . . . . . . . . . . . . . . . . . . . 39 3.4.5 Run Con guration . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4.6 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.5 Simulation Results of Expected Pro t Maximization . . . . . . . . . . 43 3.5.1 Insample Performance . . . . . . . . . . . . . . . . . . . . . . 44 3.5.2 Analysis of Theoretical Expected Pro t . . . . . . . . . . . . . 45 3.5.3 Outsample Performance for No Feature Cases . . . . . . . . . 46 3.5.4 Outsample Performance when the Features are Available . . . 52 3.5.5 Dispersion of the Simulation Results . . . . . . . . . . . . . . 54 3.6 Simulation Results of CVaR Minimization . . . . . . . . . . . . . . . 58 3.6.1 Insample Performance . . . . . . . . . . . . . . . . . . . . . . 59 3.6.2 Outsample Performance . . . . . . . . . . . . . . . . . . . . . 59 3.6.3 Dispersion of the Simulation Results . . . . . . . . . . . . . . 63 Chapter 4: Conclusion 66 Appendix A: Appendix A 67 Appendix B: Appendix B 82 Appendix C: Appendix C 91 Bibliography 130 viii LIST OF TABLES 3.1 Coe cient sets of Pt = k+"t + 1Ptô€€€1 + 2Ptô€€€2 + 1"tô€€€1 with resulting V art(Pt), and V ar(Pt). Note that, all of them are stationary processes with p = 100. The rst row is the is the i.i.d. case where V art(Pt) = V ar(Pt) = 25. V art(Pt) of P1P10 are the same with the i.i.d. case. 34 3.2 Coe cient sets of Dt = a ô€€€ bPt + t with resulting V art(Dt) and Corrt(Dt; Pt). Note that, there are 5 di erent demand scenario and all have the same expected value which is d = 1000. . . . . . . . . . 37 3.3 Coe cient Set of f(1) t . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4 Coe cient Set of binary feature f(2) t . Since the explicit solution of PfDt > Djf(2) t = 1g does not exist, the corresponding probabilities are calculated via simulation. . . . . . . . . . . . . . . . . . . . . . . 40 3.5 Parameters array con guration . . . . . . . . . . . . . . . . . . . . . 41 3.6 Expected Value of the theoretical benchmark. (1500015500: Very Low, 1550016000: Low, 1600016500: Moderate, 1650017000: High, 17000: Very High) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.7 Variance of the theoretical benchmark. (0500: Very Low, 5001000: Low, 10001500: Moderate, 15002000: High, 2500: Very High) . . . 47 3.8 E ect of the price process and the demand model on the performance of EPLP with respect to the theoretical benchmark. (Percentage de viation from the theoretical benchmark, a more detailed table can be found in Appendix A A.3) . . . . . . . . . . . . . . . . . . . . . . . . 48 ix 3.9 Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h1 = [1] (SAA). (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) 50 3.10 Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h2 = [1; Ptô€€€1]. (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) 50 3.11 Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h3 = [1; Ptô€€€1; Ptô€€€2]. (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.00 10.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.12 Best Performing parameters arrays for di erent price processes and di erent demand models (1: h1 = [1], 2: h2 = [1; Ptô€€€1], 3: h3 = [1; Ptô€€€1; Ptô€€€2]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.13 Minimum and maximum percentage gain acquired in outsample mean pro t with respect to the theoretical benchmark of no feature cases, for di erent feature availability cases. (f(1): Scalar Feature, f(2): Binary Feature ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.14 Coe cient of Variation (CV = ) of outsample theoretical mean prof its for all pricedemand scenarios . . . . . . . . . . . . . . . . . . . . 55 3.15 The percentage of the mean values of the di erence between outsample results of theoretical benchmark and EPLP in each simulation run to the theoretical benchmark for all scenarios when no features available. 57 x 3.16 The percentage of the standard deviations of the di erence between outsample results of theoretical benchmark and EPLP in each sim ulation run to the theoretical benchmark for all scenarios when no features available. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.17 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (no feature cases). . . . . . . . . . . . . . . . . . . . . 60 3.18 The best performing parameters arrays for di erent price processes and di erent demand models for CVaR Minimization (1: h1 = [1], 2: h2 = [1; Ptô€€€1], 3: h3 = [1; Ptô€€€1; Ptô€€€2]) . . . . . . . . . . . . . . . . . . 61 3.19 Percentage gain acquired by the CVARLP with respect to EPLP in terms of outsample CVaR for di erent feature availability cases (IID Price, h+ Demand) (f(1): Scalar Feature, f(2): Binary Feature ) . . . 62 3.20 The percentage of the di erence between standard deviations of out sample CVaR values of CVARLP and THEP for di erent scenarios to the theoretical outsample means (no feature cases). . . . . . . . . 63 A.1 Sample Mean Pro t (Demand is i.i.d, no features) . . . . . . . . . . 68 A.2 Outsample Mean Pro t (no features, all correlated demand cases) . 70 A.3 Percentage di erence of outsample means of Theoretical benchmark and datadriven LPs. Percentage Difference = ô€€€100Theoreticalô€€€LP Result Theoretical .(no features, all demand cases, for 3 parameters array con guration h1 = [1]; h2 = [1; Ptô€€€1]; h3 = [1; Ptô€€€1; Ptô€€€2]). Bold numbers indicates the parameters array with the best performance . . . . . . . . . . . . 71 A.4 Outsample mean pro t when a scalar feature (f(1)) is available. (low/high correlated scalar feature, all demand cases, price processes IID, P1, P2, P3, P4 and P5, and 3 parameters array con gurations, h1 = [1; f(1)], h2 = [1; f(1); Ptô€€€1], and h3 = [1; f(1); Ptô€€€1; Ptô€€€2]) . . . . . . . . . . . . 73 xi A.5 (Cont. of Table A.4) Outsample mean pro t when a scalar feature (f(1)) is available. (low/high correlated scalar feature, all demand cases, price processes P6, P7, P8, P9, P10, and 3 parameters array con gurations, h1 = [1; f(1)], h2 = [1; f(1); Ptô€€€1], and h3 = [1; f(1); Ptô€€€1; Ptô€€€2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 A.6 Outsample mean pro t when a binary feature (f(2)) is available. (low/high correlated scalar feature, all demand cases, price processes IID, P1, P2, P3, P4 and P5), and parameters array con gurations h1 = [1; f(2)], h2 = [1; f(2); Ptô€€€1], and h3 = [1; f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . 76 A.7 (Cont. of Table A.6) Outsample mean pro t when a binary feature (f(2)) is available. (low/high correlated scalar feature, all demand cases, price processes P6, P7, P8, P9, P10), and parameters array con gurations h1 = [1; f(2)], h2 = [1; f(2); Ptô€€€1], and h3 = [1; f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 A.8 Outsample mean pro t when multiple features (f(1) and f(2) = high) are available. (low/high correlated scalar feature, all demand cases, price processes IID, P1, P2, P3, P4, P5), and parameters array con g urations h1 = [1; f(1); f(2)], h2 = [1; f(1); f(2); Ptô€€€1], and h3 = [1; f(1); f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 A.9 (Cont. of Table A.8) Outsample mean pro t when multiple features (f(1) and f(2) = high) are available. (low/high correlated scalar fea ture, all demand cases, price processes P6, P7, P8, P9, P10), and parameters array con gurations h1 = [1; f(1); f(2)], h2 = [1; f(1); f(2); Ptô€€€1], and h3 = [1; f(1); f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . 79 xii A.10 Outsample mean pro t when multiple features (f(1) and f(2) = low) are available. (low/high correlated scalar feature, all demand cases, price processes IID, P1, P2, P3, P4, P5), and parameters array con g urations h1 = [1; f(1); f(2)], h2 = [1; f(1); f(2); Ptô€€€1], and h3 = [1; f(1); f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 A.11 (Cont. of Table A.10) Outsample mean pro t when multiple features (f(1) and f(2) = low) are available. (low/high correlated scalar feature, all demand cases, price processes P6, P7, P8, P9, P10), and parameters array con gurations h1 = [1; f(1); f(2)], h2 = [1; f(1); f(2); Ptô€€€1], and h3 = [1; f(1); f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . . . . . . . 81 B.1 Dispersion of simulation results for i.i.d. Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 82 B.2 Dispersion of simulation results for l+ Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 83 B.3 Dispersion of simulation results for lô€€€ Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 84 xiii B.4 Dispersion of simulation results for h+ Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 85 B.5 Dispersion of simulation results for hô€€€ Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 86 B.6 Dispersion of simulation results with features for scenario: IID Demand IID Price case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 B.7 Dispersion of simulation results with features for scenario: lô€€€ Demand  P1 Price case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 B.8 Dispersion of simulation results with features for scenario: h+ Demand  P7 Price case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 C.1 i.i.d. Demand  i.i.d. Price insample/outsample CVaR results of CVaR Minimization LP and Expected Pro t Maximization LP . . . . 92 C.2 Mean CVaR no feature IIDP5 . . . . . . . . . . . . . . . . . . . . . . 93 C.3 Mean CVaR no feature P6P10 . . . . . . . . . . . . . . . . . . . . . 94 C.4 Mean CVaR f1 high IIDP1 . . . . . . . . . . . . . . . . . . . . . . . 95 C.5 Mean CVaR f1 high P6P10 . . . . . . . . . . . . . . . . . . . . . . . 96 C.6 Mean CVaR f1 low IIDP5 . . . . . . . . . . . . . . . . . . . . . . . . 97 C.7 Mean CVaR f1 low P6P10 . . . . . . . . . . . . . . . . . . . . . . . . 98 C.8 Mean CVaR f2 high IIDP5 . . . . . . . . . . . . . . . . . . . . . . . 99 C.9 Mean CVaR f2 high P6P10 . . . . . . . . . . . . . . . . . . . . . . . 100 C.10 Mean CVaR f2 low IIDP5 . . . . . . . . . . . . . . . . . . . . . . . . 101 xiv C.11 Mean CVaR f2 low P6P10 . . . . . . . . . . . . . . . . . . . . . . . . 102 C.12 Mean CVaR f1 high f2 high IIDP5 . . . . . . . . . . . . . . . . . . . 103 C.13 Mean CVaR f1 high f2 high P6P10 . . . . . . . . . . . . . . . . . . . 104 C.14 Mean CVaR f1 high f2 low IIDP5 . . . . . . . . . . . . . . . . . . . . 105 C.15 Mean CVaR f1 high f2 low P6P10 . . . . . . . . . . . . . . . . . . . 106 C.16 Mean CVaR f1 low f2 high IIDP5 . . . . . . . . . . . . . . . . . . . . 107 C.17 Mean CVaR f1 low f2 high P6P10 . . . . . . . . . . . . . . . . . . . 108 C.18 Mean CVaR f1 low f2 low IIDP5 . . . . . . . . . . . . . . . . . . . . 109 C.19 Mean CVaR f1 low f2 low P6P10 . . . . . . . . . . . . . . . . . . . . 110 C.20 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = low). . . . . . . . . . . . . . . . . . . . . . . . . 111 C.21 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = high). . . . . . . . . . . . . . . . . . . . . . . . 111 C.22 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(2) = low). . . . . . . . . . . . . . . . . . . . . . . . . 112 C.23 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(2) = high). . . . . . . . . . . . . . . . . . . . . . . . 112 C.24 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = high, f(2) = high). . . . . . . . . . . . . . . . . 113 C.25 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = high, f(2) = low). . . . . . . . . . . . . . . . . . 113 xv C.26 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = low, f(2) = high). . . . . . . . . . . . . . . . . . 114 C.27 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = low, f(2) = low). . . . . . . . . . . . . . . . . . 114 C.28 Dispersion of simulation results of CVaR for hô€€€ Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 C.29 Dispersion of simulation results of CVaR for lô€€€ Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 C.30 Dispersion of simulation results of CVaR for i:i:d: Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 C.31 Dispersion of simulation results of CVaR for l+ Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 C.32 Dispersion of simulation results of CVaR for h+ Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 xvi LIST OF FIGURES 3.1 Simulation setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 A 100period sample path of normally distributed (mean: 100, vari ance: 25) i.i.d. price (case 1). x axis is the price and y axis is the periods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 100period sample paths of prices processes case P1 to case 10 (upper left is case P1, bottom right corner is case P10). x axis is the price and y axis is the periods. . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Distributions of CVaR values of CVARLP (Blue or Light) and TH EP (Red or Dark) for IID Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . 64 C.1 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P1 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 120 C.2 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P2 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 121 C.3 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P3 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 122 C.4 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P4 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 123 xvii C.5 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P5 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 124 C.6 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P6 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 125 C.7 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P7 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 126 C.8 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P8 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 127 C.9 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P9 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 128 C.10 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P10 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 129 xviii NOMENCLATURE Xt the random variable X at period t FX the cumulative distribution function a random variable X Fô€€€1 X inverse of the cumulative distribution function a random variable X E[Xt] expected value of the random variable Xt Et[Xt] expected value of the random variable Xt, given that all the infor mation until time t is known. V ar(Xt) variance of the random variable Xt V art(Xt) variance of the random variable Xt, given that all the information until time t is known. Corr(Xt; Yt) correlation function of the random variables Xt and Yt Corrt(Xt; Yt) correlation function of the random variables Xt and Yt, given that all the information until time t is known. (:) Pro t function (:) Loss function f(i) t a data point of feature f(i), at time t h the parameters array (i) ith element of the parameters array, the coe cient of feature f(i). P expected value of the random variable E[P]). u penalty cost per item if the demand is satis ed from the spot market o penalty cost per item if the excess inventory is sold to the spot market xix CVaR Conditional ValueatRisk VaR ValueatRisk ARMA Autoregressive Moving Average Model EPLP the datadriven linear program with expected pro t maximization in the simulation model CVARLP the datadriven linear program with CVaR minimization in the sim ulation model THEP the theoretical benchmark of the expected pro t maximization in the simulation model xx Chapter 1 INTRODUCTION Procurement decisions of commodities are essential managerial decisions in most sectors, and due to di erent problem settings, the types of procurement decisions vary. This dissertation focuses on the procurement decisions of the single period in ventory models which are widely studied in Operations Research literature. Di erent from the classical single period inventory model, we focus on the procurement policies of commodities which have a spot market. The presence of the spot market entails several modi cations to the classical model. The selling price of the commodity is determined by the market price which is volatile. In addition, all the excess inven tories can be liquidated in the spot market by paying a penalty costs per unit item. Similarly, any unsatis ed demand can be met by the spot market. Although this problem de nition covers many commodities, it would be most suitable for electricity procurement, since the electricity can be traded in realtime via its spot market. The presence of a spot market changes the dynamics of the procurement problem in several ways. While it provides an immediate trade opportunity which causes high service levels, the volatility of the price increases the complexity of the procurement problem. Therefore, using solution methods derived for the constant price settings may not address the characteristics of the problem and the solutions might be sensitive to the price uctuations and may yield risky outcomes. Although there are certain so lution methodologies that are speci cally modeled for the volatile price environments, most of the solution methodologies in the existing literature require probability distri bution functions of the demand, and/or the price, and even the underlying stochastic model of the price process if the problem is de ned in a multiperiod environment, 2 Chapter 1: Introduction to be known. However, in practice these distributions are unknown and need to be estimated from previous data, or by any other technique. The methods which do not require the estimation of such distributions but use the historical data directly are called datadriven optimization. Datadriven optimization is a well studied topic in Operations Research literature, yet it became more popular in recent years because of the availability of abundant data in almost every sector. [Ban and Rudin, 2014] proposed a datadriven linear pro gramming approach to solve the classical Newsvendor Problem that uses the historical demand data as well as the data of exogenous variables (features) that are assumed to describe demand information. Their aim is to exploit the information provided by the exogenous variables to improve the maximum expected pro t yielded. We have modi ed the method provided by [Ban and Rudin, 2014] to solve the single period procurement problem of commodity with a spot market with expected pro t maxi mization objective (riskneutral), instead of the classical newsvendor formulation. In addition to historical data of demand and the exogenous variables, our model uses historical price information to develop a procurement policy with respect to the under lying price process of the spot market. We showed that the solution approach is able to generate optimal strategies for single period procurement problems of commodities which have a spot market. Another di culty in nding optimal procurement policies for commodities which are traded in a spot market is the pricedemand dependence. Since both demand and price are uncertain, they can possibly be correlated. The simulation results showed that our riskneutral model is capable of not only exploiting the information provided by the exogenous variables, but also nding optimal procurement policies in the presence of the pricedemand dependence. In addition to the riskneutral case, we have proposed a new solution approach for the riskaverse decision makers. Although nding theoretical results might be straightforward for the expected pro t maximization case, this is not true for the riskaverse case. The existing literature does not have a closed form solution that Chapter 1: Introduction 3 covers our problem de nition, when the risk aversion is applied via minimization of Conditional ValueatRisk measure (CVaR is explained in detail in Chapter 2). We have proposed a datadriven linear model which uses the Conditional ValueatRisk measure to implement riskaverse objective. Our model uses historical demand and price data as well as the exogenous variables to produce a riskaverse procurement policy. We showed that the approach is successful for certain price processes and pricedemand dependence levels. In order to test the performance of the proposed solution approaches we have constructed a simulation model. The simulation model generates stationary price processes with di erent characteristics in order to test the performance of the ap proaches under di erent cases. We also tested the e ect of pricedemand dependence, which would be important in case of commodities with spot market, by generating several additive demand model to generate di erent correlation levels between the price and the demand. We have generated synthetic features (exogenous variables) that are correlated with demand and tested di erent correlation levels and di erent functional forms. The simulation results showed that the expected pro t maximization case is able to generate nearoptimal policies for outsample tests for all price processes and dif ferent pricedemand dependence levels, for no feature cases. Although we do not have a theoretical benchmark for the cases when exogenous variables are available, the datadriven approach with features was able to outperform the no feature cases, and therefore we conclude that the datadriven approach is able to exploit the information provided by the features. The simulation results of the riskaverse case showed that the performance of the datadriven approach depends on the variance of the price process and the correlation level between the price and the demand. Although the datadriven approach is able make notable improvements for some cases, it is not able make improvements in terms of riskaversion with respect to the expected pro t maximization objective. Therefore, while the datadriven approach for the risk aversion case works well for certain cases, 4 Chapter 1: Introduction the approach may not be applicable for all cases. The structure of this document is as follows: In Chapter 2, problem de nition and the review of the related literature is presented. We also provided background information for the related concepts. Chapter 3 is on the datadriven linear program ming approach for solving the single period problem under two di erent objectives: expected pro t maximization, and the CVaR minimization (riskaverse). First the solution methods are introduced, then the simulation model is explained, and nally the simulation results are discussed. Detailed simulation results can be found in Ap pendix A, B and C. Finally, Chapter 4 is the conclusion part where the summary of the dissertation, as well as the key ndings and future research directions are presented. Chapter 2 LITERATURE REVIEW AND BACKGROUND In this chapter the problem de nition and solution strategies are introduced to position the contribution made to the existing literature. After a brief problem def inition, we present the preliminary information which is needed to understand the model and solution approaches. Then, the literature that is comparable to this work is reviewed. Problem De nition: Our problem is to nd the optimal procurement strategy of a commodity which is traded in a spot market. The retail price of the commodity changes over the discrete time intervals (periods) and it is determined by the spot market which evolves ran domly. The decision maker is assumed not to have an impact on the market prices, and s/he needs to satisfy an uncertain demand in each period. The decision maker cannot carry inventory, i.e. s/he always starts all periods with zero inventory. If the realized demand for the commodity happens to be greater than the total procurement quantity for that period, the shortage amount is satis ed from the spot market im mediately. However, a penalty cost u TL incurs per item purchased from the market. The analogous case, excess inventory, has the same condition. If the realized demand happens to be smaller than the total procurement for that period, the excess amount is sold to the spot market with a penalty cost of o TL per item. The mathematical relationship of the selling price and demand is modeled di erently for each chapter. In the following section (Section 2.1), we present a detailed de nition of the Con ditional Valueatrisk (CVaR), as well as its properties which make it more favorable than its alternatives. Section 2.2 will cover the existing literature on risksensitive decision making for the newsvendor problem, particularly via the CVaR risk measure, 6 Chapter 2: Literature Review and Background and the newsvendor problem in PriceDemand dependent environment. Section 2.3 introduces the existing literature on datadriven optimization and its applications on the newsvendor problem, and discusses the extensions to the problem de nitions such as the features a ecting the demand, and the newsvendor problems with meanCVaR objective function. 2.1 Conditional ValueatRisk Conditional ValueatRisk (CVaR), also known as expected shortfall, is a widely ac cepted risk measure and studied in the Operations Research literature extensively because of its intuitive de nition and convenient mathematical properties. CVaR of a random variable is the expectation of the values less than (1ô€€€ ) percentile of the random variable, i.e. CVaR equals to average of the smallest 100 % of the values of the corresponding random variable. [Rockafellar and Uryasev, 2000] rst proposed the formal de nition of CVaR and came up with the mathematical properties which made CVaR more preferable to alternative downside risk measures. Using the nota tion provided by [Rockafellar and Uryasev, 2000], f(x; y) is the loss function where x 2 Rn is the decision vector and y 2 Rm is the random vector with probability den sity function p(y). The probability of loss which does not exceed a given threshold is de ned as (x; ). (x; ) = Z f(x;y) p(y)dy We assume that (x; ) is continuous. A formal CVaR de nition and its mathematical properties for general loss distributions, without requiring a continuity assumption on the distribution function, can be found in [Rockafellar and Uryasev, 2002]. Let (x) be ValueatRisk with level ( VaR), and (x) be the Conditional ValueatRisk with level ( CVaR). (x) = minf 2 R : (x; ) g (x) = 1 1 ô€€€ Z f(x;y) (x) f(x; y)p(y)dy Chapter 2: Literature Review and Background 7 This representation requires calculation of (x), to calculate the (x). [Rockafellar and Uryasev, 2000] showed crucial mathematical properties can be found via the function F (x; ) which is de ned as; F (x; ) = + 1 1 ô€€€ Z y2Rm [f(x; y)) ô€€€ ]+p(y)dy [Rockafellar and Uryasev, 2000] proved that if F (x; ) is convex and continuously di erentiable in , the following expression holds. (x) = min 2R F (x; ) This expression indicates that the CVaR of a loss function can be calculated without calculation of the VaR of the function. Since it only requires to calculate an integral, numerical methods can be used to compute the CVaR value. [Rockafellar and Uryasev, 2000] also proved that minimization CVaR ( (x)) can be achieved by minimizing F (x; ) over x and . This theorem provides a handy optimization technique since F (x; ) can be minimized, to nd optimal  CVaR, otherwise direct minimization CVaR requires nding VaR rst which is not necessarily convex. Furthermore, since the integral can be approximated by a nite sum, in stochastic programming, CVaR can be modeled via linear equations which is not the case in VaR. Another advantage of using CVaR over VaR is its being a "Coherent Risk Mea sure". A risk measure is called coherent, if it satis es the following properties: mono tonicity, subadditivity, homogeneity, and translational invariance. The de nition is proposed in [Artzner et al., 1999], it de nes the properties a risk measure should have. CVaR satis es all the properties, while VaR fails to satisfy one of the proper ties (subadditivity). A detailed review on the coherence of CVaR, its advantages over VaR and its mathematical properties can be found in [Acerbi and Tasche, 2002a], [Acerbi and Tasche, 2002b], and [Tasche, 2002]. Since CVaR considers the expectation under a certain threshold, it is sensitive to the long tails. Therefore it is a more useful risk measure than its competing 8 Chapter 2: Literature Review and Background risk measures such as Value at Risk (VaR) to capture worst case scenarios with relatively high losses with respect to the mean of the distribution. A more for mal and general proposition stating the relation between VaR and CVaR can be found in [Bertsimas et al., 2004]. They examined the mathematical properties of CVaR and its relation with other risk measures such as VaR and standard deviation. [Bertsimas et al., 2004] also showed that meanshortfall optimization can be mod eled as a linear optimization model whereas the classical mean variance optimization method proposed by [Markowitz, 1952] for portfolio selection can only be modeled as quadratic problem. For continuous distributions, [Krokhmal et al., 2002] showed minimizing negative expected return (i.e. maximizing expected return) with a CVaR constraint yields the same e ciency frontier with minimizing CVaR with a constraint on expected return. Therefore, a stochastic optimization problem having a risk constraint can be modeled as a linear model by using CVaR as a risk measure. 2.2 Newsvendor Problem The Newsvendor Problem is a wellknown and researched problem in Operations Research. The problem is to nd the order quantity which maximizes expected pro t when there is an uncertain demand. If the realized demand happens to be greater than the order quantity, there is shortage penalty (s TL) for per unit excess demand. If the realized demand happens to be smaller than the order quantity, the excess inventory can be sold to salvage value (r TL). The unit selling price of item is p TL, and purchase cost of per item is c TL. The solution of the problem is straightforward and balances costs occurring in excess and shortage cases. The pro t function (q;D) is, (q;D) = (p ô€€€ c)D ô€€€ (p + s ô€€€ c)(D ô€€€ q)+ ô€€€ (c ô€€€ r)(q ô€€€ D)+ where q is the order quantity, and D is the random variable that represents the demand. FD denotes the cumulative distribution function of demand and optimal Chapter 2: Literature Review and Background 9 order quantity (q ) which maximizes the expected value of the pro t function is, q = Fô€€€1 D u u + o where u = p + s ô€€€ c is the underage cost, and o = c ô€€€ r is the overage cost. In our problem de nition, when the decision maker is restricted to make a decision to satisfy the demand of a single period, the resulting problem has a newsvendor problem representation. For the single period case, the cost of a unit of product is c TL, the retail price of the item, equivalently the market price during the selling period is P TL, and random demand realized in the selling period is D units. FD is the cumulative distribution function of the random demand D, and P is the expected retail price during the selling period. The single period pro t function of the decision maker is (q; P;D) = (P ô€€€ c)q ô€€€ u(D ô€€€ q)+ ô€€€ o(q ô€€€ D)+ Using the relation q = D ô€€€(D ô€€€q)+ ô€€€(q ô€€€D)+, the problem is equivalent to the classical newsvendor problem (q; P;D) = (P ô€€€ c)D ô€€€ (P ô€€€ c + u)(D ô€€€ q)+ ô€€€ (ô€€€P + c + o)(q ô€€€ D)+ with the corresponding underage cost u = P ô€€€c+ u, and overage cost o = ô€€€P +c+ o. Therefore, our problem is a version of the newsvendor problem where price is uncertain and the underage and overage costs are functions of this random price. 2.2.1 Newsvendor Problem with Risk Consideration Risk sensitive decision making in single period problems has been a popular topic. There is a number of di erent approaches to represent the risk in stochastic models. One of these approaches is to use utility theory which focuses on the optimization of the utility functions, since a utility function is the representation of one's risk pro le by de nition. Another method of modeling risk sensitivity is to use risk measures. Although there are plenty of di erent risk measures, I will focus on the literature on the CVaR, since it is the risk measure that I used in my model. 10 Chapter 2: Literature Review and Background [Ahmed et al., 2007] analyzed a newsvendor problem with a coherent risk measure minimization objective. They have both investigated single and multiperiod prob lems. In the single period case, they found that the structure of the optimal solution is similar to the original expected cost minimization problem. In addition to their solution framework for general coherent risk measures, for a special condition they provided a speci c solution for CVaR risk measure. [Gotoh and Takano, 2007] proposed a closed form solution to the single period problem with CVaR minimization objective. Using theorems proposed by [Rockafellar and Uryasev, 2000], F (q; ) function being the objective to be mini mized, F (q; ) = + 1 1 ô€€€ Z 2Rm [f(q; ) ô€€€ ]+p( )d where f(q; ) is the loss function associated with the newsvendor problem. [Gotoh and Takano, 2007] found optimal solutions for two di erent loss functions de ned from the newsvendor problem. For f(q; ) = ô€€€ (q; ), i.e. negative pro t or net loss, the optimal solution (q ; ) which minimizes F (q; ) is, q = o + v o + u Fô€€€1 D u(1 ô€€€ ) o + u + u ô€€€ v o + u Fô€€€1 D o + u) o + u = o(u ô€€€ v) o + u Fô€€€1 D o + u o + u + u ô€€€ v o + u Fô€€€1 D u(1 ô€€€ ) o + u where v = uô€€€s. Note that when there is no penalty cost (s = 0), the optimal solution has a much simpler form which is, q = Fô€€€1 D u o + u (1 ô€€€ ) = ô€€€uq [Chen et al., 2014] modeled the single period newsvendor model with CVaR as a satis cing measure which is used to ensure that the expected pro t reaches to a target with a given con dence level ( of CVaR). Since their model does not have shortage penalty, [Chen et al., 2014] have reached the same optimal solution with the Chapter 2: Literature Review and Background 11 no shortage penalty cost case of [Gotoh and Takano, 2007] which is intuitive because minimizing negative pro t and maximizing positive pro t are identical. To nd the optimal they implemented a binary search on . Finally, [Chen et al., 2014] have showed that mathematical characteristics of the solution are the same with the Cer tainty Equivalent formulation which is the utility function approach to model the risk. [Jammernegg and Kischka, 2007] used a meanCVaR approach to model risk  sensitive behavior of the decision maker. The objective function of their model is the convex combinations of CVaR and the expected pro t. According to the weights of these components, the problem can be turned into the original newsvendor problem to CVaR minimization problem. Therefore their model can grasp a wider spectrum of risk preferences. [Xu and Li, 2010] also worked on the same problem setting and they reached the same result with [Gotoh and Takano, 2007] for the CVaR minimization case, and a similar result with [Jammernegg and Kischka, 2007] for meanCVaR ob jective. However, the model of [Xu and Li, 2010] also includes the shortage penalty. [Choi and Ruszczy nSki, 2008] proved a broader result which establishes that any risk averse newsvendor problem with general law invariant coherent measure of risk, has an equivalent meanrisk objective representation, i.e. meanCVaR objective. [Xinsheng et al., 2015] approach to the riskaverse newsvendor problem from a di erent perspective. [Xinsheng et al., 2015] use a function called legacy loss rather than the pro t function, which only takes into account the cost parts of the original pro t function. [Xinsheng et al., 2015] found closed form solutions for minimization of expected legacy loss function, minimization of CVaR of legacy loss function and, minimization of their convex combinations (similar to the meanCVaR approach). 2.2.2 Newsvendor Problem with PriceDemand Dependence Although there are several papers on the newsvendor problem having pricedemand dependence, all of the papers cited above assume the price and demand are inde pendent, moreover none of them assumes that the price is a random variable. Price 12 Chapter 2: Literature Review and Background demand dependence is usually used to model the newsvendor problems with pric ing options. [Petruzzi and Dada, 1999] investigated a special version of the problem where the demand distribution is a function of the price and their model suggests that the decision maker can control not only the stock levels but also the selling price. [Petruzzi and Dada, 1999] have found the optimal strategy of choosing selling price and stock levels for maximizing expected pro t under given conditions for both linear and multiplicative demandprice dependence. [Agrawal and Seshadri, 2000] took a step further and considered the riskaverse de cision makers, too. Similar to [Petruzzi and Dada, 1999], the decision maker should decide on the price and the order quantity, and the demand depends on the price. Nevertheless their objective is to maximize a utility function rather than the pro t maximization. For the risk neutral utility functions, which is identical to pro t max imization, [Agrawal and Seshadri, 2000] found slightly di erent results with respect to [Petruzzi and Dada, 1999], because of di erences in problem de nitions. For the risk averse case, [Agrawal and Seshadri, 2000] reported how optimal decisions change with respect to the risk neutral case. Although their work encapsulates both risk aversion and pricedemand dependence for single period inventory models, there are two major factors which di erentiate my work from theirs. First, they have used util ity functions to measure risk rather than a risk measure, particularly CVaR. Second, they had control over the price, which my model does not cover. The model proposed by [Chen et al., 2009] covers both the CVaR criterion and pricedemand dependence. They modeled the demand as a function of price and a random variable (D(p) = d(p;X)). If the demand function satis es certain mathemat ical properties whose details can be found in their paper, for a xed price and general demand distributions, they found similar results to the independent price case. The optimal order quantity as a function of price is q (p) = Fô€€€1 ô€€€ p; u o+u(1 ô€€€ ) where F(p; x) is the c.d.f. of d(p;X) (note that, there is no shortage penalty cost). They also investigated the cases which price is also a decision variable. [Chen et al., 2009] showed that, for both multiplicative and additive cases of demand a unique optimal Chapter 2: Literature Review and Background 13 price exists; in addition to that, for the additive case it is less than the riskneutral optimal price. [Xu, 2010] studied a very similar problem, the only di erence is that, the excess demand can be satis ed via emergency procurement which inhibits the lost sale case. The results are signi cantly similar to [Chen et al., 2009], except for the small deviations due to the lack of lost sales. While its problem de nition is similar to the problem proposed, [Chen et al., 2009] fails to respond the modi cations on newsvendor problem where price is a random variable and underage and overage costs are the functions of price. The other major di erence of their model is the role of price in their problem. Since they have sug gested pricedemand dependence in order to observe the e ect of the pricing decisions and price is a decision variable in their model. Therefore, the solution provided by [Chen et al., 2009] does not cover the problem proposed. For a more broad and detailed review of literature and recent publications on newsvendor problem, please refer to [Qin et al., 2011]. 2.3 DataDriven Optimization Di erent optimization approaches have been used in order to nd the optimal order quantities in single period inventory problems (the Newsvendor Problem) under dif ferent objectives. Even though we assume that the demand distributions are known and apply the probability laws to nd the optimal levels, in real life the demand distributions are not known and they should be estimated from historical demand data. The classical approach rst estimates the demand probability distribution and its parameters based on the historical data, then performs optimization based on the estimated parameters. There are several alternatives to this classical separated estimation and optimiza tion approach. [Liyanage and Shanthikumar, 2005] proposed operational statistics which combines the estimation of distribution parameters and optimization to solve inventory models. [Akcay et al., 2011] showed the e ect of length of historical de mand data and several other factors on the accuracy of the optimization in the 14 Chapter 2: Literature Review and Background separated parameter estimation and optimization case, and they showed optimal or dering levels considering the uncertainty caused by the estimation of the demand parameters. These approaches are called parametric approaches, since they still es timate the distribution parameters. However there are nonparametric approaches where the optimization model does not require the estimation of a parametric dis tribution function. More information can be found in [Godfrey and Powell, 2001], [Huh and Rusmevichientong, 2009] , and [Huh et al., 2011] about di erent nonparametric approaches used to solve inventory problems. Datadriven optimization is another nonparametric approach which does not re quire to estimate the distributions of the random variables but uses historical ob servations directly in the mathematical models. In this section, we will focus on the datadriven optimization methods where the demand distribution is unknown but the historical demand data is available. [Kleywegt et al., 2002] proposed a method called Sample Average Approximation (SAA) to solve stochastic optimization problems via Monte Carlo simulation approach. The method can be summarized as follows; sup pose that the minimum value of the expectation of a function g(q;D) is r , where q is a real valued decision vector and de ned in nite set Q, and D is a random variable. r can be found by the following expression: r = min q Q E[g(q;D)] If a set containing n realizations of the random variable D (i.i.d. random samples, d = [d1; :::dn]) is available , the SAA of r is ~ r and it is de ned as; ~ r = min q Q 1 n Xn i=1 g(q; di) [Kleywegt et al., 2002] showed that ~ r converges to r as n increases. [Kleywegt et al., 2002] were able to report the bounds on the number of samples required to achieve a speci c performance level. [Shapiro, 2003] investigated the sta tistical properties of the results of the algorithm. [Levi et al., 2007] applied Sample Average Approximation to the newsvendor problem, and found the bounds of number Chapter 2: Literature Review and Background 15 of samples required to have a close performance to the case where the demand distri bution is known. Later, the bound was signi cantly improved by [Levi et al., 2015]. [Ban and Rudin, 2014] used datadriven optimization techniques to nd optimal order quantity of a newsvendor problem, where the demand distribution is unknown but the historical demand data is known prior. Contrary to others, their work also considers the extra information available which might help to describe the demand distribution. [Ban and Rudin, 2014] assume that for each period there is a feature vector f which can describe the demand information with the following relation D = g(f) + . The demand can be represented as Taylor Series Expansion of g. In other words, there exists a multivariate polynomials of feature vector which describes the demand. The feature vector f is known prior to the demand realization. Some of the possible examples of features are the dependent random variables, seasonality, location, weather, or any information which is related to demand and available prior to the realization of demand. [Ban and Rudin, 2014] proposed a modi ed version of SAA which aims to exploit the information provided by the features. Suppose that the C(q;D) is the cost func tion of the newsvendor model, where q is the order quantity, the minimization of expected cost of the newsvendor model can be expressed as, min q E[C(q;D)] In case of the presence of a feature vector f, the minimization of the expected cost of the newsvendor problem is expressed as, min q E[C(q(f);D(f))jf] The features are denoted as f = [[f(1) 1 ; :::; f(1) n ]; [f(2) 1 ; :::; f(2) n ]; :::; [f(m) 1 ; :::; f(m) n ]], the demand is denoted as d = [d1; :::; dn], where there are n periods, and m features. The proposed formulation is as follows; min q:q(f)= Pm j=1 (j)f(j) 1 n Xn i=1 C(q(f); di) 16 Chapter 2: Literature Review and Background A more detailed LP formulation of this model is explained in Chapter 3.2.2. For two example cases, they showed that the suggested algorithm has a nite bias and yields asymptotically optimal solutions whereas the Sample Average Approximation method which does not include features in the decision criteria has nite bias and yields suboptimal (inconsistent) solutions. In addition, they showed the bounds on the outofsample performances of the algorithm. [Ban and Rudin, 2014] suggested a quadratic programming version of the model which limits the number of features in the decision criteria by adding a regularization term to the objective function. [Sachs and Minner, 2014] also worked on the datadriven newsvendor problem when the demand data is censored. Similar to [Ban and Rudin, 2014], thier model es timates the order quantity as a linear function of exogenous variables, by constructing a linear program which uses historical data. Although their approaches were similar, [Sachs and Minner, 2014] focused on the numerical comparison of the algorithm with benchmarks cases and measured the e ect of problems settings such as the number of available data, pricedemand dependence, etc. However their paper does not provide the mathematical model de nitively for the exogenous variables case. Therefore we will refer to [Ban and Rudin, 2014] for introducing exogenous variables in datadriven optimization literature. Risk sensitive datadriven newsvendor formulations also exist in the literature. [Zhang et al., 2009] used Sample Average Approximation method to solve newsvendor problem with a CVaR constraint and analyzed the convergence rates of solutions with respect to the number of samples. Similarly, [Choi and Ruszczy nSki, 2008] used a sample based linear problem (datadriven) to solve newsvendor problem with mean CVaR objective. For portfolio optimization, [Karoui et al., 2011] proposed a di erent technique called Performance Based Regularization, and they showed that it performs better than Sample Average Approximation method for meanCVaR objectives. Among the literature cited throughout this section, [Ban and Rudin, 2014], in terms of solution methodology, and [Choi and Ruszczy nSki, 2008] and [Zhang et al., 2009], in terms of the risk minimization approaches, are the most related pieces of works Chapter 2: Literature Review and Background 17 that are most related to Chapter 3 of my thesis. Nevertheless, [Ban and Rudin, 2014] does not address the risk averse behavior but focuses on the expected pro t maxi mization. Another important di erence between [Ban and Rudin, 2014] and Chapter 3 is the de nition of the price. While [Ban and Rudin, 2014] uses a constant price, my model has a random process which might be correlated with the random demand. In addition the main focus of Chapter 3 is to show the impact of the price process on the decision of datadriven optimization model. In contrast to [Ban and Rudin, 2014], works of [Choi and Ruszczy nSki, 2008] and [Zhang et al., 2009] both consider risk important and use CVaR as a risk measure. However their models do not address the e ect of neither the exogenous features nor the price uncertainty, and possible correlation between price and demand. Therefore [Zhang et al., 2009] fail to solve the problem proposed. Robust optimization is another method for solving stochastic problems in a risk averse manner. While the robust optimization is a way to solve the stochastic prob lems, its way of handling uncertainty is di erent than the other models. It aims to protect the system from the worst case scenarios caused by the uncertainty. In other words, it nds to best decision when all the decisions are countered by the worst pos sible realizations within the uncertainty set. The datadriven approach is widely used in robust optimization problems. Rather than being a way of avoiding risk in decision making, and its relevance to the datadriven optimization, robust optimization theory and its applications are less relevant to my work, because of the unique way of de n ing its objective. More information on datadriven robust optimization can be found in [Bertsimas and Thiele, 2006]. A datadriven robust optimization formulation of newsvendor problem can be found in [Bertsimas and Thiele, 2005]. Chapter 3 SINGLEPERIOD PROCUREMENT POLICY VIA DATADRIVEN LP As explained in detail in Chapter 2, datadriven optimization is a nonparametric optimization approach where the decision maker uses the historical data directly to make a decision without estimating the parameters of the underlying distributions of the data available. In this chapter, a datadriven linear programming approach is proposed to deter mine the procurement policy of the problem de ned in the following section. We will investigate the procurement strategies for the cases where the decision maker is risk neutral and risk sensitive. The risk neutral case aims to maximize its expected pro t whereas the risk averse case aims to minimize the Conditional Value at Risk of the loss function (negative pro t), as it is reviewed in Chapter 2. The structure of this chapter is as follows; after the problem de nition, the rst section is on the solution methods of the risk neutral case (expected pro t maximiza tion). First, a closed form solution for the expected pro t maximization objective is proposed when no features are available. Then, we introduce the datadriven tech niques to solve cases which can exploit the information provided by the available features. After a detailed explanation of [Ban and Rudin, 2014], the datadriven LP formulation which provides a basis for our solution methodology, we proposed a data driven linear program to generate a solution to our problem when the features are available. The next section, another datadriven LP formulation is proposed for the risk averse case (CVaR minimization) when features are available. Since the perfor mance of the datadriven approaches are evaluated by simulation, the next section is the detailed explanation of simulation procedure, selection of parameters, and prepa Chapter 3: Singleperiod Procurement Policy via DataDriven LP 19 ration of simulation environment. Finally, the last section is on the analysis of the simulation results. 3.1 Problem De nition Similar to the classical newsvendor problem, the decision maker needs to satisfy an uncertain demand (D units) occurring in a speci c time interval, and will make an order before the demand is observed. While the wholesale price per item (c TL) is known before the decision is made, the retail price of the commodity (P TL) is uncertain and will not be realized until the demand is observed. The retail price is determined by the spot market of the commodity. The decision maker is assumed to have no e ect on the spot market price. The commodity is perishable, i.e. excess amount of items cannot be stored for the upcoming periods. However, the decision maker is able to sell excess inventory to the spot market with a penalty cost per item ( o TL) after the demand and the price is realized. Therefore, in case of excess inventory, the decision maker will sell any amount of goods to the spot market with price (P ô€€€ o) TL. The analogous case is also true. In case of shortage, the decision maker may satisfy the demand from the spot market with a penalty cost per item ( u TL). In other words, any amount of goods can be purchased from the spot market with price (P + u) TL. Therefore, the pro t function of the decision maker is (q; P;D), where q is the order quantity. (q; P;D) = (P ô€€€ c)q ô€€€ u(D ô€€€ q)+ ô€€€ o(q ô€€€ D)+ The decision maker does not know the distribution function of the demand as well as underlying price process of the spot market prices. S/he needs to use the historical data of the demand and the spot market prices for n periods and historical data of exogenous variables (features), to nd the optimal order quantity. The features are the variables which are possibly correlated with the demand and/or the price, and can be observed prior to demand, and price realization. Examples of the features could be the weather data (such as temperature, wind, humidity etc.), the data of 20 Chapter 3: Singleperiod Procurement Policy via DataDriven LP nancial indicators (such as historical exchange rates, stock market prices, etc.), date information in order to capture the seasonality if it exists, or any possible available data which might be related to the demand and/or price. Now, assume that there are m features each having the information of n pe riods. The vector [f(i) 1 ; f(i) 2 ; :::; f(i) n ] contains the data of feature i for i = 1; :::;m. The vector f contains all the features, f = [[f(1) 1 ; f(1) 2 ; :::; f(1) n ]; [f(2) 1 ; f(2) 2 ; :::; f(2) n ]; :::; [f(m) 1 ; f(m) 2 ; :::; f(m) n ]]. Using the historical data available for demand d = [d1; d2; :::; dn], the historical data available for price p = [p1; p2; :::; pn], and the feature vector f the decision maker aims to nd the optimal order quantity which yields the best outcome for his/her objective function. 3.2 Maximization of Expected Pro t In this section, we will investigate the solution methods when the objective of the decision maker is to maximize his/her expected pro t. We rst propose a theoretical solution for when no exogenous variables (features) are available. In the following part, the datadriven linear programming approach proposed by [Ban and Rudin, 2014] is explained. Then a datadriven linear model is formulated by using their approach to solve our problem. Finally, a modi ed version of the linear model is proposed to improve the performance of the model in terms of the memory requirements. 3.2.1 Theoretical Solution for No Feature Case Proposition 1. The closed form solution for the optimal order quantity q which maximizes the expected pro t at period t when all the information until time t is known, q = arg max q 0 Et[(Pt ô€€€ ct)q ô€€€ u(Dt ô€€€ q)+ ô€€€ o(q ô€€€ Dt)+] Chapter 3: Singleperiod Procurement Policy via DataDriven LP 21 is q = 8>>>>>< >>>>>: 0 Et[Pt] ô€€€ ct ô€€€ u Fô€€€1 Dt Et[Pt]ô€€€ct+ u u+ o ô€€€ u < Et[Pt] ô€€€ ct < o +1 o Et[Pt] ô€€€ ct where Pt is the price in period t, Dt is the demand in period t and ct is the procurement price in period t, and Et[:] is a conditional expectation where all the information until time t is known. Proof. Let us note that: Et[ (q; Pt;Dt)] = Et[(Pt ô€€€ ct)q] ô€€€ uEt[(Dt ô€€€ q)+] ô€€€ oEt[(q ô€€€ Dt)+] The derivative with respect to q is: @Et[ (q; Pt;Dt)] @q = (Et[Pt] ô€€€ ct) + u(1 ô€€€ FDt(q)) ô€€€ oFDt(q) and the second derivative is: @2Et[ (q; Pt;Dt)] @q2 = ô€€€( u + o)fDt(q) Since the second derivative is always negative ( o, and o are nonnegative by de  nition), the function is concave, and q which satis es @Et[ (q;Pt;Dt)] @q = 0 will be the optimal order quantity. (Et[Pt] ô€€€ ct) + u(1 ô€€€ FDt(q)) ô€€€ oFDt(q) = 0 if Et[Pt] ô€€€ ct ô€€€ u, q = 0 if ô€€€ u < Et[Pt] ô€€€ ct < o, q = Fô€€€1 Dt Et[Pt] ô€€€ ct + u u + o if o Et[Pt] ô€€€ ct, q = +1 22 Chapter 3: Singleperiod Procurement Policy via DataDriven LP 3.2.2 [Ban and Rudin, 2014], DataDriven Linear Programming Approach for the Newsvendor Problem As it is brie y explained in Chapter 2.3, [Ban and Rudin, 2014] proposed a data driven linear program to generate an ordering policy which minimizes the expected cost of the classical Newsvendor Problem (Chapter 2.2). Suppose that the decision maker does not know the true distribution of the demand (D), yet s/he has the historical data of the demand (d = [d1; :::dn]) and a set of features f = [[f(1) 1 ; :::; f(1) n ]; [f(2) 1 ; :::; f(2) n ]; :::; [f(m) 1 ; :::; f(m) n ]] which is believed to explain the demand information in the form of linear combinations. The proposed linear programming model which combines Sample Average Ap proximation approach with information of feature set is, Sets I : set of periods, historical data of which are available, I = f1; :::; ng J : set of features, J = f1; :::;mg Parameters c : wholesale price of the item u : underage cost per unsatis ed demand o : overage cost per unsold item di : demand in period i, 8i 2 I f(j) i : the value of feature j in period i, 8i 2 I, and 8j 2 J Decision variables xi : order quantity in period i, 8i 2 I q+ i : (xi ô€€€ di)+, i.e. amount of unsold products in period i, 8i 2 I qô€€€ i : (di ô€€€ xi)+, i.e. amount of unsatis ed demand in period i, 8i 2 I (j) : weight of feature j on the order quantity , 8j 2 J Mathematical Model Chapter 3: Singleperiod Procurement Policy via DataDriven LP 23 min =[ (1);:::; (m)] 1 n Xn i=1 (uqô€€€ i + oq+ i ) s:to 8i = 1; :::; n: qô€€€ i di ô€€€ (1) ô€€€ Xm j=2 ( (j) + f(j) i ) q+ i (1) + Xm j=2 ( (j) + f(j) i ) ô€€€ di qô€€€ i ; q+ i 0 Note that this model provides a vector = [ (1); :::; (m)] which minimizes expected cost of newsvendor problem over the sample data set. [Ban and Rudin, 2014] claim that the decision maker can use the resulting vector to nd the order quantity (qt(ft)) for a period t which is not used to train the model (outofsample), using corresponding period's features ft, i.e. qt(ft) = Pm i=1 (j)f(j) t . 3.2.3 Mathematical Model for Maximization of Expected Pro t Our claim is that the decision maker can modify the datadriven linear programming approach proposed by [Ban and Rudin, 2014], to solve the problem de ned in Section 3.1. Although the problem is similar to the classical newsvendor model, there are major di erences such as the random price and underage and overage costs are being functions of that random demand. Our claim is that a similar approach to [Ban and Rudin, 2014] su ces to generate optimal solutions when the exogenous vari ables (features) are available. Since the decision maker aims to maximize the expected pro t function when the historical data is available, the objective function is, max x 0 E[ (x; P;D)j(d; p; f)] We constructed h, the parameters array, by using the features and other available information such as historical data of price process. The parameters array is similar 24 Chapter 3: Singleperiod Procurement Policy via DataDriven LP to the feature vector f of [Ban and Rudin, 2014]. We chose to denote it di erently to emphasize that it does not only consist of exogenous variables, but it may also include endogenous variables such as previous price realizations. The claim of [Ban and Rudin, 2014] requires a linear dependence between exoge nous features (or their functions) and the demand, in order to be able to use the solution methodology. We extend their claim, and suggest that if the selling price is volatile and generated by a random process, historical price information (or the functions of which) can be used alongside with the available exogenous variables in the parameters array h. We claim that, there exists an array of parameters, h, a linear combination of which yields a nearoptimal solution for the problem. ~ x i = Xjhj j=1 jhij where ~ x i is the nearoptimal solution for the ith period. Since is the vector of coe cients, the aim of the mathematical model is to nd the vector to evaluate order quantity ~ x i given a parameters array h. The mathematical model chooses the optimal vector to maximize the sample mean pro t of the previous periods. The resulting vector which generates optimal ~ x i for each period to yield the maximum pro t is used to nd the optimal order quantity for the upcoming period. The decision maker is faced with the question of how to construct a correct pa rameter array h which su ces to represent the characteristics of an ordering decision. While the scope of this thesis does not cover the optimal strategy of obtaining the optimal parameter array h, the performances of di erent parameter arrays under dif ferent scenarios will be tested by simulation in the following section. Even though this does not provide an optimal strategy, it will help the decision maker in the process of selecting the parameter array. For instance, if the price is assumed to have an autoregressive process where price of ith period is heavily depends on the previous price. Then, the price of (i ô€€€ 1)th period can possibly be selected as one of elements of the parameters array to re ect the e ect of ith price on the (i + 1)th price, consequently on the ~ x i . Furthermore, Chapter 3: Singleperiod Procurement Policy via DataDriven LP 25 let's assume that the demand is correlated with a feature observed in ith period. Therefore, the resulting parameters array for the ith period to be used to evaluate the order quantity can be selected as hi = [1; piô€€€1; f(1) i ], for all i. Note that, the rst element of the parameters array is selected as 1. Even though it is not mandatory to allocate rst term to 1, it is a useful practice since it provides a historical data free coe cient 1 which may serve as an intercept term. Note that any function of the historical data can be used while constructing the parameters array. For instance, addition to the example case above, if the demand during the weekends happens to be greater than the weekdays, the decision maker may add an indicator function of date data, i.e. Iff(2) i 2[Saturday;Sunday]g where f(2) i is the date information of ith period and I is the indicator function, Itrue = 1 and Ifalse = 0. Then the resulting parameters array for the ith period can be hi = [1; piô€€€1; f(1) i ; Iff(2) i 2[Saturday;Sunday]g]. The decision maker is free to make any linear or nonlinear transformation to the historical data to come up with a parameters array h. A sample parameters array for the ith period hi could be hi = [1; (piô€€€1)2; diô€€€7; (diô€€€1piô€€€1); Iff(1) i 0g; q f(2) iô€€€1; log( f(3) i 1 ô€€€ f(3) i )] After the parameters array h is constructed, the mathematical model is solved to nd vector which maximizes the optimal expected pro t of the sample data available. Sets I : set of periods, historical data of which are available, I = f1; :::; ng H : set of parameters, H = f1; :::;mg Parameters pi : retail price of the item in period i, 8i 2 I ci : wholesale price of the item in period i, 8i 2 I di : demand in period i, 8i 2 I u : penalty cost per item if the demand is satis ed from the spot market 26 Chapter 3: Singleperiod Procurement Policy via DataDriven LP o : penalty cost per item if the excess inventory is sold to the spot market hij : value of parameter j in period i, 8i 2 I, and 8j 2 H Decision variables xi : order quantity in period i q+ i : (xi ô€€€ di)+, i.e. amount of product sold to spot market in period i qô€€€ i : (di ô€€€ xi)+, i.e. amount of product purchased from the spot market in period i j : weight of parameter j on the order quantity, 8j 2 H Mathematical Model max 1 n Xn i=1 (pi ô€€€ ci)xi ô€€€ oq+ i ô€€€ uqô€€€ i s:to 8i 2 I xi = Xm j=1 jhij q+ i xi ô€€€ di qô€€€ i di ô€€€ xi xi; q+ i ; qô€€€ i 0 The linear model has the following memory requirements; for jIj = n, and jHj = m, the number of decision variables is 3n + m, the number of constraints is 3n, and the number of nonnegativity constraints is 3n. Although the model above is straightforward and easy to comprehend, there is a better way of implementing the problem. By not de ning the variable x, the user may decrease the memory need of the model. Modi ed Version of the Model max 1 n Xn i=1 (pi ô€€€ ci) Xm j=1 jhij ô€€€ oq+ i ô€€€ uqô€€€ i s:to 8i 2 I q+ i Xm j=1 jhij ô€€€ di Chapter 3: Singleperiod Procurement Policy via DataDriven LP 27 qô€€€ i di ô€€€ Xm j=1 jhij Xm j=1 jhij 0 q+ i ; qô€€€ i 0 The modi ed version has the following memory requirements; for jIj = n , and jHj = m, the number of decision variables is 2n+m, the number of constraints is 3n, and the number of nonnegativity constraints is 2n. Although, we assure that this model maximizes insample expected pro t, its out sample performance should be tested. In Section 3.4, a simulation model is proposed to test both insample and outsample performance of the model for di erent price processes, di erent demand models to simulate di erent pricedemand dependence, di erent features, and di erent parameters array selections. 3.3 Minimization of CVaR Consider the case where the decision maker is riskaverse and willing to manage its risk by having a di erent objective function. Rather than maximizing the expec tation of the pro t function, s/he will minimize the CVaR of the distribution of a loss function (x; y) where x is the decision variable and y is the uncertain vector. First, the mathematical model for the datadriven CVaR minimization of the prob lem is presented in this section. Then, a modi ed version is proposed to improve the performance of the model in terms of the memory requirements. In addition to the variables and parameters de ned for the expected pro t maxi mization model (Section 3.2.3), Proposition 2 requires the introduction of the follow ing parameters and variables: is parameter denoting the CVaR level, variable is the resulting VaR level of the CVaR, i is the pro t acquired in period i, and zi is an auxiliary variable. 28 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Proposition 2. The following linear program minimizes the insample CVaR of the loss function ô€€€ (q; P;D), where (q; P;D) = (P ô€€€c)qô€€€ u(Dô€€€q)+ô€€€ o(qô€€€D)+, when features are available. Mathematical Model min + 1 (1 ô€€€ )n Xn i=1 zi s:to 8i 2 I xi = Xm j=1 jhij i = (pi ô€€€ ci)xi ô€€€ oq+ i ô€€€ uqô€€€ i zi ô€€€ ô€€€ i q+ i xi ô€€€ di qô€€€ i di ô€€€ xi xi; zi; q+ i ; qô€€€ i 0 Proof. Note that, CVaR is the expectation of the losses exceeding a threshold , which is percentile of the loss distribution. Suppose that p.d.f. of a loss function (x; y) is f (y) (where x is the decision vector, and y is the random vector. See Section 2.1 for a detailed de nition of CVaR risk measure). If (x; y) is convex for a xed y, [Rockafellar and Uryasev, 2000] showed that minimization of CVaR of loss function (x; y), can be achieved by minimization of F (x; ) which is de ned as, F (x; ) = + 1 1 ô€€€ Z y2Rm [ (x; y)) ô€€€ ]+f (y)dy Furthermore, [Rockafellar and Uryasev, 2000] also proposed that F (x; ) can be ap proximated by the sampling of the random vector y. F^ (x; ) = + 1 1 ô€€€ Xn i=1 [ (x; yi) ô€€€ ]+ where [y1; y2; :::; yn] vector consists of n realizations of the random vector y. Chapter 3: Singleperiod Procurement Policy via DataDriven LP 29 In our problem the loss function is the negative of the pro t function ( (x; [p; d]) = ô€€€ (q = x; p; d)) which is, (x; [p; d]) = ô€€€(p ô€€€ c)x + u(d ô€€€ x)+ + o(x ô€€€ d)+ Note that in order to use F^ (x; ) to minimize CVaR of the loss function, (x; y) should be convex in x. (x; [p; d]) can be represented as piecewise linear functions. (x; [p; d]) = 8>< >: (ô€€€p + c ô€€€ u)x + ud x < d (ô€€€p + c + o)x ô€€€ od d x (x; y) is continuous, i.e. (d; [p; d]) = (ô€€€p+c)d, and it is convex in x for a xed [p; d], when o > ô€€€ u which is always true since o and u are nonnegative by de nition. Therefore our problem is to minimize F^ (x; ), min x; + 1 1 ô€€€ Xn i=1 [ô€€€ (x; pi; di) ô€€€ ]+ The expression above can be turned into a linear form by removing [:]+ function. We introduce the auxiliary variables zi, as [Rockafellar and Uryasev, 2000] suggested. min x; + 1 1 ô€€€ Xn i=1 zi s:to 8i 2 I zi ô€€€ (x; pi; di) ô€€€ zi 0 A datadriven approach similar to [Ban and Rudin, 2014], can be implemented to this problem as follows; min x; + 1 1 ô€€€ Xn i=1 zi s:to 8i 2 I xi = Xm j=1 jhij i = (pi ô€€€ ci)xi ô€€€ oq+ i ô€€€ uqô€€€ i 30 Chapter 3: Singleperiod Procurement Policy via DataDriven LP zi ô€€€ i ô€€€ q+ i xi ô€€€ di qô€€€ i di ô€€€ xi xi; zi; q+ i ; qô€€€ i 0 The CVaR minimization model has the following memory requirements; for jIj = n, and jHj = m, the number of decision variables is 5n + m + 1, and the number of constraints is 5n, and the number of nonnegativity constraints is 4n. The memory need of this model can be decreased by eliminating the variables x and , leading to the following modi ed model. Modi ed Version min + 1 (1 ô€€€ )n Xn i=1 zi s:to 8i 2 I zi ô€€€ ô€€€ (pi ô€€€ ci) Xm j=1 jhij + oq+ i + uqô€€€ i q+ i Xm j=1 jhij ô€€€ di qô€€€ i di ô€€€ Xm j=1 jhij Xm j=1 jhij 0 zi; q+ i ; qô€€€ i 0 The modi ed version of the CVaR minimization has the following memory re quirements; for jIj = n , and jHj = m, the number of decision variables is 3n+m+1, the number of constraints is 3n, and the number of nonnegativity constraints is 3n. Chapter 3: Singleperiod Procurement Policy via DataDriven LP 31 Although this model generates minimum CVaR for the periods that is trained (insample), its performance should be tested for outsample data. The simulation model is proposed to test both insample and outsample performance of the model for di erent settings in the following section. 3.4 Simulation Model The performance of the datadriven linear programs that are proposed to solve the procurement problem is measured by a simulation model. The simulation model is constructed to test as many scenarios as possible in order to show the solution methodology is capable of providing solution to a wide range of di erent scenarios. The simulation model tests a combination of 11 di erent price processes, 5 dif ferent pricedemand relations and 2 exogenous variables (one continuous, one bi nary) each having 2 di erent correlation levels with demand, which results 11(price process) 5(demand model) 3(continuous feature) 3(binary feature)= 495 di erent scenarios. For each problem scenario, the parameters are selected in such a way that the comparison between the scenarios is possible, i.e. the same and stationary mean for all the price processes, the same variance or the conditional variance (variance at time t when all the information until time t ô€€€ 1 is known), same mean for each demand scenario, and the same variance or the conditional variance for demand. In addition, the random seed, which is used to generate realizations of random variables, is di erent for all iterations, but the same within an iteration for di erent problem scenarios in order to eliminate the possible anomalies caused by chance. Within an iteration, 495 di erent but equivalent scenario data is generated for 400 consecutive periods each. For each scenario two datadriven approaches are applied to the problem, datadriven linear programs having expected pro t maximization(risk neutral) and CVaR minimization(risk averse). Furthermore, for each linear program, 12 di erent parameter arrays is used to solve each 495 unique problem. Therefore, the simulation model provides the most suitable parameters arrays for the speci c scenario. 32 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Each di erent scenario with 400 periods is solved with 2 di erent objective and each objective have 12 di erent solution setup (parameters array) which yields 24 di erent vectors which are the outcomes of the linear programs. Each vector is the vector yields the optimal objective value for its objective function given the scenario data. The data that are used to evaluate vector is called training data. The accuracy of the model can only be measured via out of sample tests. Therefore, for each iteration and for each scenario, 100 di erent sample paths of 200 periods are simulated which are called test data. The vector evaluated using training data is tested for 100 di erent test data, for each theta, for each scenario and for each iteration. Figure 3.1: Simulation setup 100 replications z } { Training Sample Test Samples 400 periods 200 periods  {z } 100 di erent sample paths The procedure is repeated for 100 iterations and the resulting statistics are ana lyzed at the last section of this chapter. The following part of this chapter presents the detailed explanations for model and parameter selections to construct di erent scenarios, selection of parameters array, and selecting benchmarks. 3.4.1 Price Process Settings While constructing di erent scenarios to be tested, the selection of the price process model is the primary decision. Since the price is determined via a spot market, the model to be selected should show the characteristics of a spot market model while having the exibility to re ect di erent patterns. Furthermore, despite re ecting di erent patterns, the process should be comparable among di erent cases. Therefore, I chose the price process to be an ARMA (Autoregressive  Moving Average Model) Chapter 3: Singleperiod Procurement Policy via DataDriven LP 33 model with di erent parameters which is able to re ect a wide range of di erent patterns. ARMA is a time series model, and it has the following mathematical representa tion, Pt = k + "t + Xp i=1 iPtô€€€i + Xq j=1 j"tô€€€j This process is called ARMA(p; q). Pt is the price at period t (autoregressive terms), and "t is the moving average term at period t, and k is a constant. "t are i.i.d. random variables with variance 2. Note that the price process is stationary, i.e. p = E[Pt] = E[Pt+1]; 8t 0, if all zeros of lie outside of the unit circle. If the process is stationary, then the mean of the process can be found by using this formula: p = k 1 ô€€€ 1 ô€€€ 2 ô€€€ ::: ô€€€ p Variance of the process V ar(Pt) depends on the coe cients of the autoregressive and moving average terms. I will provide the variances of ARMA(0; 0), ARMA(1; 0), ARMA(2; 0), and ARMA(1; 1), since these are the ones that are used in the simula tion. V ar(Pt) = 8>>>>>>>>< >>>>>>>>: 2 ARMA(0; 0) 2 1ô€€€ 21 ARMA(1; 0) 1ô€€€ 2 1+ 2 2 (1ô€€€ 2)2ô€€€ 21 ARMA(2; 0) 2(1+ 21 +2 1 1) 1ô€€€ 21 ARMA(1; 1) Note that, V art(Pt) and V ar(Pt) are di erent measures. V art(Pt) is a conditional variance of Pt where all the information until time t is known, while V ar(Pt) is the variance of Pt at time 0. V art(Pt) = 2; 8t 0 4 di erent ARMA process will be simulated; ARMA(0; 0), ARMA(1; 0), ARMA(2; 0), and ARMA(1; 1). All of these processes have the following mathematical representa tion. Pt = k + "t + 1Ptô€€€1 + 2Ptô€€€2 + 1"tô€€€1 34 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Each di erent set of parameters k; 1; 2; 1 and 2 variance of "t, will generate a di erent price process. Note that all moving average terms " are normally distributed with mean 0, and variance 2. Table 3.1: Coe cient sets of Pt = k + "t + 1Ptô€€€1 + 2Ptô€€€2 + 1"tô€€€1 with resulting V art(Pt), and V ar(Pt). Note that, all of them are stationary processes with p = 100. The rst row is the is the i.i.d. case where V art(Pt) = V ar(Pt) = 25. V art(Pt) of P1P10 are the same with the i.i.d. case. Tag k 1 2 1 V ar("t) V art(Pt) V ar(Pt) (Ptô€€€1; Ptô€€€2; "tô€€€1) 2 IID : ( ; ; ) 100 0 0 0 25.00 25.00 25.00 P1 : (+; ; ) 30 0.7 0 0 25.00 25.00 49.02 P2 : (ô€€€; ; ) 170 0.7 0 0 25.00 25.00 49.02 P3 : (+; ; +) 30 0.7 0 0.5 25.00 25.00 95.59 P4 : (ô€€€; ; +) 170 0.7 0 0.5 25.00 25.00 26.96 P5 : (+; ;ô€€€) 30 0.7 0 0.5 25.00 25.00 26.96 P6 : (ô€€€; ;ô€€€) 170 0.7 0 0.5 25.00 25.00 95.59 P7 : (+;+; ) 10 0.7 0.2 0 25.00 25.00 111.11 P8 : (ô€€€;+; ) 150 0.7 0.2 0 25.00 25.00 111.11 P9 : (+;ô€€€; ) 50 0.7 0.2 0 25.00 25.00 39.47 P10 : (ô€€€;+; ) 190 0.7 0.2 0 25.00 25.00 39.47 The simulation model generates 11 di erent price process for each iteration. The coe cients of each price process are chosen arbitrarily yet they are adjusted to cover a large set of possible price scenarios, while having comparable statistical proper ties. All of these are stationary processes with mean p = 100. The rst process is ARMA(0,0), with mean 100 and variance 25, i.e. prices are identically and indepen dently distributed. Note that variance and conditional variance are equal for the i.d.d case. The next 10 processes are di erent variations of ARMA(1; 0), ARMA(2; 0), and ARMA(1; 1) which cover all positive and negative parameter combinations, and Chapter 3: Singleperiod Procurement Policy via DataDriven LP 35 the parameters are adjusted to make the conditional variance of the process equals to 25. However their variances do not equal 25. All the simulated processes, their respective parameter, and resulting variance and conditional variance values are listed in Table 3.1. Within the same iteration, all the processes are generated by using the same random seed, therefore the same random variables. A 100period sample path of i.i.d. price process is shown in Figure 3.2. The sample paths of other 10 price processes is shown in Figure 3.3 (blue or light processes). Note that all the di erent price processes are generated via the same random seed (including Figure 3.2). Figure 3.3 is provided to depict the behavior of di erent ARMA con gurations. The graphs on the left consist of the processes with positive 1, while the price processes shown in the right graphs have a negative 1 coe cient which increases the spikiness of the process. We use the term "spikiness" to assess the magnitude of the oscillation around their mean. In addition, in order to emphasize the e ect of the variance on the shape of process for di erent price models, Figure 3.3 provides reference price processes (red or dark) having variance of 25. Note that the price processes, P1 to P10 (blue or light) have a conditional variance of 25, however their variances di er. Figure 3.2: A 100period sample path of normally distributed (mean: 100, variance: 25) i.i.d. price (case 1). x axis is the price and y axis is the periods. 36 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Figure 3.3: 100period sample paths of prices processes case P1 to case 10 (upper left is case P1, bottom right corner is case P10). x axis is the price and y axis is the periods. 3.4.2 Demand Settings The simulation model generates di erent demand streams in order to test a wide set of scenarios with di erent correlations between the price and the demand. An additive model is used to generate demand streams correlated with the price process. The mathematical formulation of the additive model is as follows, Dt = a ô€€€ bPt + t Note that Dt is the amount of demand occurred in period t, 8t 0 where Pt is the spot price, a, and b are constant, and t is i.i.d. random variable with Normal distribution, with mean 0, and and standard deviation . The values of b, and determine the correlation between the price and demand in a given period. Similar to the selection of parameters of price process, di erent parameters are selected to test a wide range of scenarios for demand. 5 di erent demand models are generated which are: independent from price, positively or negatively correlated Chapter 3: Singleperiod Procurement Policy via DataDriven LP 37 (correlation coe cient is either 0.7 or 0.7, respectively), and weakly positively or neg atively correlated (correlation coe cient is either 0.3 or 0.3, respectively). To make comparison between scenarios possible, parameters selected to satisfy the following conditions; the expected pro t is equal to D = 1000, and V art(Dt) = 1002. All the respective parameters and their resulting variance and can be found in Table 3.2. Table 3.2: Coe cient sets of Dt = a ô€€€ bPt + t with resulting V art(Dt) and Corrt(Dt; Pt). Note that, there are 5 di erent demand scenario and all have the same expected value which is d = 1000. Tag a b V ar( t) V art(Dt) Corrt(Dt; Pt) 2 = t 2 [2; 11] t 2 [2; 11] iid 1000 0 10000 1002 0 l+ 400 6 9100 1002 0.3 lô€€€ 1600 6 9100 1002 0.3 h+ 400 14 5100 1002 0.7 hô€€€ 2400 14 5100 1002 0.7 The mathematical relations between variance, correlation, conditional variance, conditional correlation, and parameters are provided in below formulations. V ar(Dt) = V ar(a ô€€€ bPt + t) = V ar(a) + V ar(bPt) + V ar( t) = b2V ar(Pt) + 2 V art(Dt) = b2V art(Pt) + 2 38 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Corr(Dt; Pt) = Cov(Dt; Pt) p V ar(Dt)V ar(Pt) = Cov(a ô€€€ bPt + t; Pt) p (b2V ar(Pt) + 2 )V ar(Pt) = Cov(a; Pt) ô€€€ bCov(Pt; Pt) + Cov( t; Pt) p (b2V ar(Pt)2 + 2 V ar(Pt) = ô€€€bV ar(Pt) p (b2V ar(Pt)2 + 2 V ar(Pt) Corrt(Dt; Pt) = ô€€€bV art(Pt) p (b2V art(Pt)2 + 2 V art(Pt) 3.4.3 Feature Set Settings The presence of exogenous variable (feature) might have an important impact on the decision criteria. In order to measure the e ect of a feature that is correlated to the demand (and/or price) stream, two di erent feature models are proposed. For each model, two correlation levels are tested (high/low). Scalar Feature Suppose that there is a feature that is correlated with the demand and/or the price. The feature is observed before the realization of demand. The rst model for the fea ture is a noise added over the demand. The correlation between feature and demand streams are controlled by the standard deviation of the noise. The mathematical formulation of the model is, f(1) t = Dt + wt where, wt is the random noise added to demand to adjust the rate of correlation. wt is normally distributed with mean 0 and variance 2w . Values of 2w selected to simu late high (0.9) and low (0.6) correlation values between f(1) t and Dt. Corresponding coe cients and their respective correlation values are listed in Table 3.3. The correlation values shown in Table 3.3 are computed via following expressions. Chapter 3: Singleperiod Procurement Policy via DataDriven LP 39 Table 3.3: Coe cient Set of f(1) t . Tag V ar(wt) Corrt(Dt; f(1) t ) 2w = t 2 [2; 11] high 2500 0.9 low 17500 0.6 Corr(Dt; f(1) t ) = V ar(Dt) p (V ar(Dt)2 + 2w V ar(Dt) Corrt(Dt; f(1) t ) = V art(Dt) p (V art(Dt)2 + 2w V art(Dt) Binary Feature Suppose that there is an exogenous variable (feature) which signals whether the de mand is going to be higher than its mean with a level of certainty, before the demand is observed. This feature can be modeled via the following mathematical expression, f(2) t = 8>< >: 1 Dt + wt > D 0 Dt + wt D where, wt is the random noise added to demand to adjust the level of accuracy of the indicator function. wt is normally distributed with mean 0 and variance 2w . 3.4.4 Parameters Array Selection The solution methodology requires the selection of the parameters array hi. The parameters array is important, because the accuracy of the model depends on this selection. According to the selection of hi the datadriven linear program nds 40 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Table 3.4: Coe cient Set of binary feature f(2) t . Since the explicit solution of PfDt > Djf(2) t = 1g does not exist, the corresponding probabilities are calculated via simulation. Tag V ar(wt) PfDt > Djf(2) t = 1g 2w = t 2 [2; 11] high 1000 0.9 low 10000 0.75 vector which optimizes the objective function of the problem. ~ x i = Xjhj j=1 jhij The simulation model solves datadriven linear programs for every di erent sce nario, with each of parameters array con gurations to test the performance of the respective con guration. All the parameters array con gurations are listen in Table 3.5. 3.4.5 Run Con guration Parameters selected for simulation model are as follows; mean demand is 1000, stan dard deviation of demand is 100 (Note that standard deviation is measured with two di erent methods, one step ahead, i.e. standard deviation of next period when all the information is known until the current period, and the standard deviation of a period without any information). Price is stationary and the mean price is 100, and standard deviation of each price is 5 (two di erent standard deviation calculation applies for the price process, too). The underage penalty u = 40, and overage penalty o = 60. The procurement cost is constant for all periods, ci = 80, 8i > 0. Note on procurement cost, c, being a constant: The procurement cost is modeled as a constant and it is the same for all periods. Therefore it is independent from the spot market price. One might argue that the assumption on the procurement cost is misleading, and not relevant. Since the price Chapter 3: Singleperiod Procurement Policy via DataDriven LP 41 Table 3.5: Parameters array con guration # Ptô€€€1 Ptô€€€2 f(1) t f(2) t ht 1 0 0 0 0 [1] 2 0 0 1 0 [1,f(1) t ] 3 0 0 0 1 [1,f(2) t ] 4 0 0 1 1 [1,f(1) t ,f(2) t ] 5 1 0 0 0 [1,Ptô€€€1] 6 1 0 1 0 [1,Ptô€€€1,f(1) t ] 7 1 0 0 1 [1,Ptô€€€1,f(2) t ] 8 1 0 1 1 [1,Ptô€€€1,f(1) t ,f(2) t ] 9 1 1 0 0 [1,Ptô€€€1,Ptô€€€2] 10 1 1 1 0 [1,Ptô€€€1,Ptô€€€2,f(1) t ] 11 1 1 0 1 [1,Ptô€€€1,Ptô€€€2,f(2) t ] 12 1 1 1 1 [1,Ptô€€€1,Ptô€€€2,f(1) t ,f(2) t ] is modeled as an ARMA process, and the pro t function requires only the margin of the price and the procurement cost (P ô€€€ c) and the margin (P ô€€€ c) turns out to be another ARMA process. Therefore even if the procurement cost is modeled as a function of the previous price, or even if it has a noise added, i.e. ci = Piô€€€1 + , the margin (Pt ô€€€ ct) is going to be another ARMA process. Hence, a procurement cost modeled as an ARMA process can be modeled as a constant procurement cost and modi ed ARMA coe cients. Therefore the current simulation model is su cient to test the cases where the procurement costs depends on the previous periods, since it test a wide range of ARMA processes. 3.4.6 Benchmarks A theoretical benchmark can be found for no feature cases by Proposition 1. The simulation model uses ARMA price processes, and an additive demandprice model, 42 Chapter 3: Singleperiod Procurement Policy via DataDriven LP where all the error terms are normally distributed. Note that the price and demand models used in simulation are, Pt = k + "t + 1Ptô€€€1 + 2Ptô€€€2 + 1"tô€€€1 and Dt = a ô€€€ bPt + t Corollary 1. Theoretical benchmark of the simulation model, q , i.e. optimal order quantity of the single period problem where Pt is an ARMA process, Dt an additive pricedemand model and all the information until time t is known, can be computed by the following expression: q = 8>>>>>< >>>>>: 0 p ô€€€ ct ô€€€ u d + d ô€€€1 pô€€€ct+ u u+ o ô€€€ u < p ô€€€ ct < o +1 o p ô€€€ ct where Et[Pt] = p = k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 , and Et[Dt] = d = a ô€€€ b k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 and p V art(Dt) = d = p b2 2 + 2 Proof. The benchmark should be calculated using the same information which is available for the simulation. In other words, the theoretical optimal decision for time period t, should be calculated given all the information until time t is known. Since all the information until time t is known, values of Ptô€€€1, Ptô€€€2, and "tô€€€1 are already observed (all realized random variables are signed by a hat^). The uncertainty of Pt is caused only by "t (which has a 0 mean and standard deviation), and t (which has a 0 mean and standard deviation). Since both "t, and t are normally distributed variables, the pro t function can be rewritten using the information available. Pt Normal p = k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 ; Dt Normal d = a ô€€€ b k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 ; d = q b2 2 + 2 Chapter 3: Singleperiod Procurement Policy via DataDriven LP 43 Since Et[Pt] = p = k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 , and Dt is normal mean d = a ô€€€ b k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 and standard deviation d = p b2 2 + 2 , by using Proposition 1 the optimal order quantity can be calculated as, q = d + d ô€€€1 p ô€€€ ct + u u + o The above equation is valid only when ô€€€ u < pô€€€ct < o. Therefore the resulting optimal order quantity with respect to the di erent parameter values is, q = 8>>>>>< >>>>>: 0 p ô€€€ ct ô€€€ u d + d ô€€€1 pô€€€ct+ u u+ o ô€€€ u < p ô€€€ ct < o +1 o p ô€€€ ct 3.5 Simulation Results of Expected Pro t Maximization This section covers the analysis of datadriven linear program with expected pro t maximization objective. Before we begin the analysis of the results, we will de ne some terms which will be used through this section. "EPLP" stands for the datadriven linear program with expected pro t maximization which is proposed in Section 3.2.3. "Insample" refers any direct result of the linear program. For instance, expected pro t result of EPLP is called "insample" expected pro t. When we apply the policy generated by EPLP to another data set rather than the data used in the EPLP, resulting statistics are called as "outsample". "Theoretical" term is used to indicate the resulting statistics when the theoretical optimal policy is used. The aim of this simulation is to show the power of the datadriven LP formulation in generating optimal decisions to maximize outsample expected pro t, for all possible scenarios, i.e. for all price processes, for all pricedemand dependency, and for all feature availability cases. 44 Chapter 3: Singleperiod Procurement Policy via DataDriven LP We rst analyze the insample performance of the algorithm, then, before moving into the analysis of outsample performance which is more important, we provide an analysis for the theoretical results. Outsample performance is analyzed in two parts. We rst looked at the when the features are not available. The e ect of price process and demand model and the impact of parameters array selection is investigated. Then the e ect of the exogenous feature availability and the dispersion of the results are analyzed. The tables presented in this section are constructed to provide insights to the sim ulation results. More detailed simulation results are listed in Appendix A (expected pro ts) and Appendix B (dispersion of the outsample pro ts). 3.5.1 Insample Performance Insample performance of the datadriven LP formulation (EPLP): EPLP is able to maximize insample mean pro t for all scenarios. Insample performance of EPLP increases as the number of elements in the parameters array increases for all scenarios. The fact that the performance of insample results increases as the size of the parameter array increases is not surprising because a larger parameters array causes an increment in the dimension of the LP which enables to nd values improves the optimal policy. In other words, the feasible region of a datadriven LP with a given parameters array is always a subset of feasible region of a datadriven LP parameters array of which is a super set of the initial parameters array. Therefore, the improvement in the objective function is expected as the size of parameters array increases. However it may cause over tting, a poorer performance in the outsample results. The comparison of the outsample results are more meaningful to evaluate the performance of the solution method. These observations are consistent for all possible scenarios, i.e. di erent price processes, demand models and availability of features. As an example case, insample mean pro t values of a scenario are presented in Table A.1 (Appendix A). The table Chapter 3: Singleperiod Procurement Policy via DataDriven LP 45 shows the insample and outsample mean pro ts for all price processes when the demand is i.i.d. and no feature is available. Insample results may perform better than the theoretical benchmark which is not surprising since the LP uses the information of all periods in the computation, while the theoretical benchmark only uses the information of the previous periods. Note that in Table A.1, there is a di erence between insample and outsample results of theoretical benchmarks. This di erence is not expected and it is caused by the variance of the simulation results. Number of iterations are increased, we expect that both values converge to one another. However this variance does not cause a problem for measuring the outcome of EPLP since, insample and outsample values should be compared with their respective benchmarks. Although insample results are valuable to depict the capability of EPLP, the true indicator of the performance is the outsample results. Before the analysis of the outsample performance of the datadriven LP for no feature case, results of the theoretical benchmark should be investigated. 3.5.2 Analysis of Theoretical Expected Pro t Our ndings on the theoretical expected pro t are as follows, For all price processes, as the correlation level of price and demand increases, the theoretical expected pro t increases. (As the correlation level of price and demand decreases, the theoretical expected pro t decreases.) The e ect of correlation on the theoretical expected pro t increases with respect to the variance of the price process. The variance of the theoretical expected pro t increases as the correlation increases (both positive and negative correlation increases the variance of the results.), as variance of the price process increases. The variance of the theoretical expected pro t decreases as the spikiness of the price process increases. (Smoother price processes result bigger variances on their theoretical expected pro ts with respect to the spikier processes with the same 46 Chapter 3: Singleperiod Procurement Policy via DataDriven LP variance.) Table 3.6: Expected Value of the theoretical benchmark. (1500015500: Very Low, 1550016000: Low, 1600016500: Moderate, 1650017000: High, 17000: Very High) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IIDP4P5 Moderate Moderate Moderate Moderate Moderate Low P9P10 Low Moderate Moderate Moderate Moderate Moderate P1P2 Low Moderate Moderate Moderate High High P3P6 Very Low Low Moderate High Very High Very High P7P8 Very Low Moderate Moderate High Very High Table 3.6 shows the e ect of variance of the price process and the correlation between price and demand. The variance of the theoretical results does not only depend on the variance of the price and the correlation level between the price and the demand, but also they depend on the spikiness of the price process (Table 3.7). The sign of 1 which is the coe cient of Ptô€€€1 of the ARMA process determines the spikiness of the process; therefore, the variance of the theoretical results depends heavily on the sign of the parameter 1. Negative and zero 1 cases result small variances for demand models whereas positive 1 cases, the variance of the theoretical outcome increases as the correlation level, and the variance of the price process. 3.5.3 Outsample Performance for No Feature Cases The true performance of EPLP can only be understood by the analysis of the out sample results. The analysis of the outsample results for the cases where the features are not available is straightforward, since we have theoretical benchmarks for these cases. The outsample results are compared with the respective theoretical results. The simulation results show that, Chapter 3: Singleperiod Procurement Policy via DataDriven LP 47 Table 3.7: Variance of the theoretical benchmark. (0500: Very Low, 5001000: Low, 10001500: Moderate, 15002000: High, 2500: Very High) Correlation of Price and Demand 1 Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+)  Very Low P5 Very Low Very Low Very Low Very Low Very Low  Low P9 Very Low Very Low Very Low Very Low Very Low  Moderate P1 Very Low Very Low Very Low Very Low Very Low  High P3 Very Low Very Low Very Low Very Low Very Low  Very High P7 Very Low Very Low Very Low Very Low Very Low 0 Very Low IID Very Low Very Low Very Low Very Low Very Low + Very Low P4 Very Low Very Low Very Low Low Low + Low P10 Very Low Very Low Low Low Low + Moderate P2 Low Low Low Low Moderate + High P6 Low Moderate Moderate Moderate High + Very High P8 High Very High Very High Very High Very High EPLP is able to nd a procurement rule which yields an expected pro t which is as good as the theoretical optimal policy for all no feature cases. The simulation results show that the performance of the datadriven LP depends on the correlation of demand and price. As the correlation between demand and price decreases (positively or negatively) the performance of the solution methodology increases. (Table 3.8) The performance of the datadriven LP is a ected by the number of parameters exist in the price process. For simpler price processes the solution method performs better than for more complex price processes.(Table 3.8) The simulation results of outsample mean pro t show that even the scenario with the worst expected pro t is as good as the theoretical upper bound, the data driven LP is only ô€€€0:44% o the theoretical result, whereas the scenario with the 48 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Table 3.8: E ect of the price process and the demand model on the performance of EPLP with respect to the theoretical benchmark. (Percentage deviation from the theoretical benchmark, a more detailed table can be found in Appendix A A.3) Correlation of Price and Demand # of Parameters Corresponding Very Low Negative Independent Positive Very High of Price Process Price Process (h) (l) (i.i.d.) (l+) (h+) 0 IID 0.06 0.04 0.04 0.05 0.06 1 P1P2 0.08  0.09 0.07  0.09 0.08  0.09 0.09 0.10  0.12 2 P3...P10 0.13  0.32 0.07  0.13 0.06  0.13 0.14  0.22 0.15  0.44 best performance is as good as ô€€€0:04% for all price process  demand model pairs. (See Appandix A Table A.1 and, Table A.2 for resulting outsample mean pro ts, and see Table A.3 for the percentage deviation of the outsample mean pro ts to the theoretical benchmark) Despite the performance of the EPLP depends on the correlation level between the price and the demand, interestingly, it does not directly depend on neither the variance of the price process, nor the spikiness of but it depends on the number of parameters exist in the price process. For simpler price processes, i.e. i.i.d. or ARMA(1,0), the solution method performs better than more complex price processes such as ARMA(1,1) or ARMA(2,0). Nevertheless, the di erence in terms of perfor mance negligible. (Table 3.8) The E ect of the Parameters Array Selection: Selection of the parameters array plays an important role on the performance of the datadriven approach. Note that all insample and outsample performance statistics presented in the previous sections are the results of the best performing parameters array selection. Our aim is to investigate the best parameters array selection for di erent price processes and demand models. Without the presence of the features, the parameters array is constructed by using only the previous price information. We have tested Chapter 3: Singleperiod Procurement Policy via DataDriven LP 49 three di erent parameters array con gurations, h1 = [1], h2 = [1; Ptô€€€1], and h3 = [1; Ptô€€€1; Ptô€€€2]. Simulation results show that the selection of the best performed parameters array depends on the following conditions: The performance of the parameters array depends on the structure of the underlying ARMA process of the price most. Parameters array should include the variables of the ARMA process, i.e. h1 = [1] is the best option for i.i.d. price (ARMA(0,0)), h2 = [1; Ptô€€€1] is the best option for P1 and P2 which are ARMA(1,0). In case of more complex ARMA processes (ARMA(1,1) and ARMA(2,0)) both variance of the price process, and the correlation level between the price and the demand a ect the best performing parameters array selection, and h1 and h2 might perform better than h3 = [1; Ptô€€€1; Ptô€€€2] which we would expect that it would be the best option according to the rst observation. However always performs almost as good as the best performing parameters array selection. Therefore the rst observa tion still holds. Spikiness of the price process does not a ect the performance of the parameters array selection, if the variances of the processes are the same. Note that EPLP with the parameters array h1 = [1] is the same with Sample Average Approximation (SAA) method. The results of Appendix A Table A.2 shows that SAA is not able adapt pricedemand correlation especially with processes with bigger variance. It lacks responding to di erent price levels, since it does not possess the price information of the previous periods. Nevertheless, if the price is i.i.d., then since the previous realization of the price does not a ect the future, then the information of the previous price does not contribute to the solution, and in that case SAA results are immune to the pricedemand correlation. Therefore, for i.i.d. price processes, it is preferable to use SAA (or datadriven LP formulation with parameters array [1]) for all correlation levels of the price and the demand. The SAA case (h1) yields higher pro ts if price process is i.i.d., but for the rest of the price processes, other two parameters array con gurations perform better. 50 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Table 3.9: Percentage di erence of outsample mean pro t and theoretical benchmark when parameters array is h1 = [1] (SAA). (00.10: Very Good, 0.100.25: Good, 0.25 1.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID Very Good Very Good Very Good Very Good Very Good Very Low P4P5 Moderate Very Good Very Good Good Moderate Low P9P10 Bad Good Good Bad Bad Moderate P1P2 Bad Moderate Good Bad Very Bad High P3P6 Very Bad Moderate Moderate Very Bad Extremely Bad Very High P7P8 Very Bad Bad Moderate Very Bad Extremely Bad Table 3.10: Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h2 = [1; Ptô€€€1]. (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID Very Good Very Good Very Good Very Good Good Very Low P4P5 Good Very Good Very Good Good Moderate Low P9P10 Good Very Good Very Good Good Moderate Moderate P1P2 Very Good Very Good Very Good Good Good High P3P6 Moderate Good Good Moderate Bad Very High P7P8 Moderate Very Good Very Good Good Moderate Simulations results show that the parameters array should be constructed to provide information to represent underlying ARMA process. Although, the variance of the price process and the correlation of the demand and the price a ect the parameters Chapter 3: Singleperiod Procurement Policy via DataDriven LP 51 Table 3.11: Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h3 = [1; Ptô€€€1; Ptô€€€2]. (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID Good Good Good Good Good Very Low P4P5 Good Good Good Good Good Low P9P10 Good Good Good Good Good Moderate P1P2 Good Good Good Good Good High P3P6 Moderate Good Good Good Moderate Very High P7P8 Good Good Good Good Good Table 3.12: Best Performing parameters arrays for di erent price processes and dif ferent demand models (1: h1 = [1], 2: h2 = [1; Ptô€€€1], 3: h3 = [1; Ptô€€€1; Ptô€€€2]) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID 1 1 1 1 1 Very Low P4P5 3 1 1 2 3 Low P9P10 3 2 2 3 3 Moderate P1P2 2 2 2 2 2 High P3P6 3 3 2 3 3 Very High P7P8 3 2 2 3 3 array performance especially for complex price processes, for complex price processes, it is useful to construct larger parameters arrays. 52 Chapter 3: Singleperiod Procurement Policy via DataDriven LP 3.5.4 Outsample Performance when the Features are Available In this section, the e ect of features (exogenous variables) on the outsample perfor mance of the EPLP is analyzed. First of all, it is important to remind that a theoretical closed form solution of the problem does not exist when the features are available. Therefore, it is not possible to calculate the deviation of the EPLP from the optimal value directly, and only the relative performance of the method can be measured, i.e. comparison of the out sample mean pro ts of the theoretical benchmark of the featureless case and results the EPLP. Although this comparison does not prove the optimality of the method, it reveals the ability of EPLP to capture and exploit the extra information provided by the features on the demand and/or the price. The simulation results show that The decision maker would better o if s/he uses the EPLP with features rather than using theoretical optimal values which does not use the feature information, for all pricedemand scenarios and all parameters array con gurations. As the information provided by the feature become more accurate, i.e. the correlation between the demand and feature increases, the gain increases with respect to the theoretical benchmark of no feature case. This condition holds for all price processes and all demand models. (Table 3.13) Although both scalar and binary features yield greater pro ts than the the oretical results, scalar features performs better than binary feature cases. (Table 3.13) Presence of multiple features increases the gain acquired. (Table 3.13) The e ects of variance of the price process and the correlation level between price and demand on the performance of EPLP are consistent with no feature cases. Table 3.13 presents the percentage gains acquired when EPLP is preferred instead of the theoretical benchmark of no feature case. It lists the minimum and the max imum gains acquired among all scenarios. Therefore, we can conclude that having extra information improves the performance of the solution method regardless of the Chapter 3: Singleperiod Procurement Policy via DataDriven LP 53 Table 3.13: Minimum and maximum percentage gain acquired in outsample mean pro t with respect to the theoretical benchmark of no feature cases, for di erent feature availability cases. (f(1): Scalar Feature, f(2): Binary Feature ) Binary Feature Scalar Feature No Low High No (0.44)  (0.04) 2.69  4.82 4.77  9.72 Low 3.94  5.59 5.65  8.21 6.94  11.43 High 11.49  14.96 11.90  15.44 12.44  16.26 scenario, and even when the amount of information provided by the features is small, EPLP still performs better than the theoretical benchmark of the featureless case in terms of the outsample mean pro t. More detailed tables presenting the outsample mean pro ts for all scenarios and feature availability cases can be found in Appendix A. Table A.4 and Table A.5 presents the outsample mean pro ts of EPLP with scalar feature cases, and Table A.6 and Table A.7 presents the outsample mean pro ts of EPLP with binary feature cases. Simulation results of multiple feature cases can be found in Appendix A Tables A.8, A.9, A.10, and A.11. The simulation results coincide with the ndings of no feature cases in terms of the e ect of variance of the price process, the correlation level between price and demand on the outsample mean pro t, and the e ect of parameters array selection. For instance, when the prices are i.i.d. the presence of previous prices does not improve the performance. However, for price processes which evolves conditionally on the previous realizations, the parameters array with the price information (h2, h3) yields better outcomes. Furthermore, the gain acquired by selection of the parameters array with price information accumulates as the variance of the price process and as the price and demand become more correlated. Nevertheless, this gain is proportionally smaller than the no feature case. This is reasonable since the feature already induced the model to result a better solution, and a smaller room for improvement is left with 54 Chapter 3: Singleperiod Procurement Policy via DataDriven LP respect to the no feature case. In conclusion, having a feature which is correlated with the demand improves the performance of the datadriven LP approach and a proper price information should be included to parameters array to yield a better mean pro t. 3.5.5 Dispersion of the Simulation Results Although the analysis on sample means of the simulation results provides insights on the datadriven LP, the dispersion of the results should be investigated in order to ensure the validity of the strategy. An outsample test with a smaller variance is more preferable, because smaller variance indicates that solution methodology is capable of generating outcomes near the outsample mean. However, being able to assess the magnitude of a statistical property requires a reference point. In this case, a reference statistic is required to measure the dispersion generated by datadriven LP. Simulation results of a theoretical benchmark can be used as a reference to as sess the performance of the proposed solution methodology. Table 3.14, representing coe cient of variation of simulation results of theoretical benchmark, provides these reference points for each scenario (pricedemand pair) to assess the performance of datadriven LP. The table presents the coe cient of variations of the sample mean pro t within an iteration accumulated when the theoretical optimal procurement strategy is used. In other words, for no feature cases, the variation of the datadriven LP results can only be compared with these theoretical values. Table 3.14 shows the outsample coe cient of variations among separate out sample simulation iterations, for each scenario (PriceDemand pair). Note that coef cient of variation is CV = which scales the standard deviation of the collection with its mean to measure the dispersion, and enables to compare the dispersion of di erent data sets with di erent mean values. The coe cient of variation values pre sented in Table 3.14 show that they vary among di erent scenarios. While its value is around 0.02 to 0.05 for most of the scenarios (8 out of 11 scenarios), the value can be as high as 0.26 (P7h+ pair). This dispersion prevents direct comparison of the Chapter 3: Singleperiod Procurement Policy via DataDriven LP 55 Table 3.14: Coe cient of Variation (CV = ) of outsample theoretical mean pro ts for all pricedemand scenarios Demand IID l+ lô€€€ h+ hô€€€ IID 0.03 0.03 0.03 0.03 0.02 P1 0.08 0.08 0.07 0.09 0.06 P2 0.02 0.02 0.02 0.02 0.02 P3 0.11 0.12 0.10 0.13 0.09 P4 0.03 0.03 0.02 0.03 0.02 P5 0.04 0.04 0.04 0.05 0.03 P6 0.02 0.02 0.02 0.02 0.02 P7 0.22 0.23 0.20 0.26 0.17 P8 0.02 0.03 0.02 0.04 0.04 P9 0.05 0.05 0.04 0.06 0.04 P10 0.02 0.02 0.02 0.02 0.02 outsample variances of the solution methodology. Therefore, we measure the dispersion of the EPLP by investigating the statistical properties of the di erence between results of theoretical optimal strategy and the solution approach for the same realizations of the random environment. For instance, for a given scenario, and a given realization of demandprice pair, theoretical optimal strategy and a EPLP is used concurrently to compute outsample mean pro t. Dif ference between the resulting outsample mean pro ts is collected for all outsample realizations. Analysis of the statistical properties of these di erences reveal the true dispersion of the solution strategy which is mostly puri ed from the volatility already existing in theoretical results. Table 3.15 shows the percentage of the mean values of the di erence between outsample results of theoretical benchmark and EPLP in each simulation run to the theoretical benchmark for all scenarios when no features available. Table 3.16 56 Chapter 3: Singleperiod Procurement Policy via DataDriven LP shows the percentages of the standard deviations. The simulation results on the ta bles show that the solution methodology is successfully able to imitate the behavior of the theoretical benchmark. None of the results con icts this claim. First of all, the distribution of the di erences between theoretical and datadriven LP are no tably small when they are scaled with the mean of the theoretical benchmark (the percentage values). The mean of the di erences between the datadriven LP and the theoretical benchmark are very small with respect to the mean of the benchmark. The scenario with the worst performance, performed only 0:42% less than the theoreti cal benchmark for correct parameters array selection. Not only the mean di erence but also the standard deviation is very small with respect to the benchmark mean value. The deviation of result generated by the datadriven LP is as small as 0:42% of the theoretical benchmark mean for the worst performing scenario. More detailed statistics can be found in Appendix B Tables B.1, B.2, B.3, B.4, and B.5. Among all scenarios, the worst performing one realized within a range of ô€€€3:99%, +0:98% of the theoretical benchmark mean. Therefore, we can conclude the following, Since the dispersion of the simulation results are very small with respect to the mean values of the theoretical benchmark, the analysis performed using the out sample mean pro ts are accurate. Although the performance of EPLP is satisfactory for all scenarios, the variance of the price process and the correlation level between the price and the demand, still a ects the performance of EPLP. The correlation level decreases the performance of the solution methodology for both positive and negative cases. Furthermore, the e ect of the price variance can be observed in Table 3.15, and Table 3.16. Dispersion of datadriven LP is investigated not only for nofeature cases, but also for the cases when the features are available. They show the dispersion on the results of datadriven LP when the features are available. Since there are so many scenarios and parameters array con gurations, only three scenarios are selected to be able to represent the characteristics of a wide range of possible scenarios (among 55 possible scenarios), and result of the rest can be found in Appendix Table B.6, Table B.7, and Chapter 3: Singleperiod Procurement Policy via DataDriven LP 57 Table 3.15: The percentage of the mean values of the di erence between outsample results of theoretical benchmark and EPLP in each simulation run to the theoretical benchmark for all scenarios when no features available. Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID 0.01 0.00 0.00 0.01 0.02 Very Low P4P5 0.04  0.07 0.01  0.01 0.00  0.00 0.00  0.00 0.09  0.11 Low P9P10 0.09  0.07 0.02  0.00 0.00  0.01 0.05  0.05 0.08  0.09 Moderate P1P2 0.08  0.06 0.02  0.01 0.01  0.01 0.06  0.06 0.08  0.08 High P3
Click tabs to swap between content that is broken into logical sections.
Title  Procurement strategies of a commodity with a spot market 
Author  GÃ¶ksel, Mustafa GÃ¶kÃ§en 
Subject  Industrial procurement; Industrial management; Purchasing; Prices; Spot prices 
Faculty Advisor  Karaesmen, Fikri 
Institute  KoÃ§ University Graduate School of Sciences & Engineering 
Program  Industrial Engineering 
Physical Description  xx, 134 leaves : illustrations ; 30 cm. 
Place of Publication  Ä°stanbul 
Publisher  KoÃ§ University 
Resource Type  goksel_mustafa_gokcen_thesis_2017.pdf 
Date  2017 
Collection  KU Theses and Dissertations 
Transcription  Procurement Strategies of a Commodity with a Spot Market by Mustafa G ok cen G oksel A Dissertation Submitted to the Graduate School of Sciences and Engineering in Partial Ful llment of the Requirements for the Degree of Master of Science in Industrial Engineering August 11, 2017 Procurement Strategies of a Commodity with a Spot Market Ko c University Graduate School of Sciences and Engineering This is to certify that I have examined this copy of a master's thesis by Mustafa G ok cen G oksel and have found that it is complete and satisfactory in all respects, and that any and all revisions required by the nal examining committee have been made. Committee Members: Prof. Fikri Karaesmen Prof. G urhan K ok Asst. Prof. Bora C ekyay Date: Dedicated to my late grandfather. iii ABSTRACT We investigated the single period procurement policy of a commodity which is traded in a spot market. The presence of a spot market di erentiates the problem de nition from the classical single period inventory models, and requires di erent solution strategies. We have proposed two datadriven linear programs to nd the optimal procurement strategies for two di erent objectives: (i) expected pro t maxi mization (riskneutral), (ii) minimization of CVaR (riskaverse). Our proposed solu tion approaches use historical demand and price data as well as the historical data of exogenous variables which are assumed to be correlated with demand and/or price. We have conducted a simulation to ensure the validity of the models. According to the simulation results, the riskneutral case is able to yield nearoptimal solutions for all price processes and all pricedemand dependence cases. The riskaverse model is able to outperform the riskneutral one in terms of CVaR risk measure for certain cases of price processes and pricedemand dependence cases. The presence of the exogenous variables improved the performance of both programs. iv OZETC E Spot piyasas bulunan emtialar n tek d onemlik sat n alma politikalar n inceledik. Spot piyasas n n varl g , problem tan m n di ger tek d onemlik envanter modellerinden ay rmaktad r ve bu sebeple daha farkl c oz um stratejileri gerektirir. Beklenen kar mak simizasyonu (riske n otr) ve CVaR minimizasyonu (riskten ka c nan) olmak uzere iki farkl amaca y onelik optimal sat n alma stratejilerini belirlemek ad na iki veri g ud uml u do grusal program oneriyoruz. Onerdi gimiz c oz um yakla s m , ge cmi s talep ve yat verilerini, ayr ca talep ve yat ile aralar nda bir korelasyon oldu gu varsay lan ge cmi s d ssal de gi sken verilerini de kullanmaktadr. Modellerin ge cerlili ginden emin olmak i cin bir sim ulasyon ger cekle stirdik. Sim ulasyon sonu clar na g ore, riske n otr durum, t um yat s ure clerinde ve yat ve talebin birbirine ba gl oldu gu durumlarda optimale yak n c oz umler uretebilmektedir. Riskten ka c nan model ise belirli yat s ure clerinde ve yat ve talebin birbirine ba gl oldu gu durumlarda CVaR risk ol c umlerinde riske n otr durumdan daha iyi performans g ostermi stir. Ayr ca, d ssal de gi skenlerin varl g programlar n performans n y ukseltmi stir. v ACKNOWLEDGMENTS First and foremost, I would like to express my sincere gratitude to my thesis advisor Prof. Fikri Karaesmen for his guidance and support in the last two years. He has guided me through the process of writing my thesis and provided valuable advice whenever I needed it. This being said, I am most grateful for his sincere attitude and unwavering positive mood. Additionally, I would like to thank my committee members Prof. G urhan K ok and, Asst. Prof. Bora C ekyay for their interest in my work. I would like to acknowledge all faculty members of Ko c University for their involve ment in my learning process both during my undergraduate and graduate studies. And last but not least, I would like to thank my family and friends for their unconditional support and endless patience. vi TABLE OF CONTENTS List of Tables ix List of Figures xvii Nomenclature xix Chapter 1: Introduction 1 Chapter 2: Literature Review and Background 5 2.1 Conditional ValueatRisk . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Newsvendor Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Newsvendor Problem with Risk Consideration . . . . . . . . . 9 2.2.2 Newsvendor Problem with PriceDemand Dependence . . . . . 11 2.3 DataDriven Optimization . . . . . . . . . . . . . . . . . . . . . . . . 13 Chapter 3: Singleperiod Procurement Policy via DataDriven LP 18 3.1 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Maximization of Expected Pro t . . . . . . . . . . . . . . . . . . . . 20 3.2.1 Theoretical Solution for No Feature Case . . . . . . . . . . . . 20 3.2.2 [Ban and Rudin, 2014], DataDriven Linear Programming Ap proach for the Newsvendor Problem . . . . . . . . . . . . . . 22 3.2.3 Mathematical Model for Maximization of Expected Pro t . . 23 3.3 Minimization of CVaR . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.4 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.1 Price Process Settings . . . . . . . . . . . . . . . . . . . . . . 32 vii 3.4.2 Demand Settings . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4.3 Feature Set Settings . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.4 Parameters Array Selection . . . . . . . . . . . . . . . . . . . 39 3.4.5 Run Con guration . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4.6 Benchmarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.5 Simulation Results of Expected Pro t Maximization . . . . . . . . . . 43 3.5.1 Insample Performance . . . . . . . . . . . . . . . . . . . . . . 44 3.5.2 Analysis of Theoretical Expected Pro t . . . . . . . . . . . . . 45 3.5.3 Outsample Performance for No Feature Cases . . . . . . . . . 46 3.5.4 Outsample Performance when the Features are Available . . . 52 3.5.5 Dispersion of the Simulation Results . . . . . . . . . . . . . . 54 3.6 Simulation Results of CVaR Minimization . . . . . . . . . . . . . . . 58 3.6.1 Insample Performance . . . . . . . . . . . . . . . . . . . . . . 59 3.6.2 Outsample Performance . . . . . . . . . . . . . . . . . . . . . 59 3.6.3 Dispersion of the Simulation Results . . . . . . . . . . . . . . 63 Chapter 4: Conclusion 66 Appendix A: Appendix A 67 Appendix B: Appendix B 82 Appendix C: Appendix C 91 Bibliography 130 viii LIST OF TABLES 3.1 Coe cient sets of Pt = k+"t + 1Ptô€€€1 + 2Ptô€€€2 + 1"tô€€€1 with resulting V art(Pt), and V ar(Pt). Note that, all of them are stationary processes with p = 100. The rst row is the is the i.i.d. case where V art(Pt) = V ar(Pt) = 25. V art(Pt) of P1P10 are the same with the i.i.d. case. 34 3.2 Coe cient sets of Dt = a ô€€€ bPt + t with resulting V art(Dt) and Corrt(Dt; Pt). Note that, there are 5 di erent demand scenario and all have the same expected value which is d = 1000. . . . . . . . . . 37 3.3 Coe cient Set of f(1) t . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4 Coe cient Set of binary feature f(2) t . Since the explicit solution of PfDt > Djf(2) t = 1g does not exist, the corresponding probabilities are calculated via simulation. . . . . . . . . . . . . . . . . . . . . . . 40 3.5 Parameters array con guration . . . . . . . . . . . . . . . . . . . . . 41 3.6 Expected Value of the theoretical benchmark. (1500015500: Very Low, 1550016000: Low, 1600016500: Moderate, 1650017000: High, 17000: Very High) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.7 Variance of the theoretical benchmark. (0500: Very Low, 5001000: Low, 10001500: Moderate, 15002000: High, 2500: Very High) . . . 47 3.8 E ect of the price process and the demand model on the performance of EPLP with respect to the theoretical benchmark. (Percentage de viation from the theoretical benchmark, a more detailed table can be found in Appendix A A.3) . . . . . . . . . . . . . . . . . . . . . . . . 48 ix 3.9 Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h1 = [1] (SAA). (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) 50 3.10 Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h2 = [1; Ptô€€€1]. (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) 50 3.11 Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h3 = [1; Ptô€€€1; Ptô€€€2]. (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.00 10.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.12 Best Performing parameters arrays for di erent price processes and di erent demand models (1: h1 = [1], 2: h2 = [1; Ptô€€€1], 3: h3 = [1; Ptô€€€1; Ptô€€€2]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.13 Minimum and maximum percentage gain acquired in outsample mean pro t with respect to the theoretical benchmark of no feature cases, for di erent feature availability cases. (f(1): Scalar Feature, f(2): Binary Feature ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.14 Coe cient of Variation (CV = ) of outsample theoretical mean prof its for all pricedemand scenarios . . . . . . . . . . . . . . . . . . . . 55 3.15 The percentage of the mean values of the di erence between outsample results of theoretical benchmark and EPLP in each simulation run to the theoretical benchmark for all scenarios when no features available. 57 x 3.16 The percentage of the standard deviations of the di erence between outsample results of theoretical benchmark and EPLP in each sim ulation run to the theoretical benchmark for all scenarios when no features available. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.17 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (no feature cases). . . . . . . . . . . . . . . . . . . . . 60 3.18 The best performing parameters arrays for di erent price processes and di erent demand models for CVaR Minimization (1: h1 = [1], 2: h2 = [1; Ptô€€€1], 3: h3 = [1; Ptô€€€1; Ptô€€€2]) . . . . . . . . . . . . . . . . . . 61 3.19 Percentage gain acquired by the CVARLP with respect to EPLP in terms of outsample CVaR for di erent feature availability cases (IID Price, h+ Demand) (f(1): Scalar Feature, f(2): Binary Feature ) . . . 62 3.20 The percentage of the di erence between standard deviations of out sample CVaR values of CVARLP and THEP for di erent scenarios to the theoretical outsample means (no feature cases). . . . . . . . . 63 A.1 Sample Mean Pro t (Demand is i.i.d, no features) . . . . . . . . . . 68 A.2 Outsample Mean Pro t (no features, all correlated demand cases) . 70 A.3 Percentage di erence of outsample means of Theoretical benchmark and datadriven LPs. Percentage Difference = ô€€€100Theoreticalô€€€LP Result Theoretical .(no features, all demand cases, for 3 parameters array con guration h1 = [1]; h2 = [1; Ptô€€€1]; h3 = [1; Ptô€€€1; Ptô€€€2]). Bold numbers indicates the parameters array with the best performance . . . . . . . . . . . . 71 A.4 Outsample mean pro t when a scalar feature (f(1)) is available. (low/high correlated scalar feature, all demand cases, price processes IID, P1, P2, P3, P4 and P5, and 3 parameters array con gurations, h1 = [1; f(1)], h2 = [1; f(1); Ptô€€€1], and h3 = [1; f(1); Ptô€€€1; Ptô€€€2]) . . . . . . . . . . . . 73 xi A.5 (Cont. of Table A.4) Outsample mean pro t when a scalar feature (f(1)) is available. (low/high correlated scalar feature, all demand cases, price processes P6, P7, P8, P9, P10, and 3 parameters array con gurations, h1 = [1; f(1)], h2 = [1; f(1); Ptô€€€1], and h3 = [1; f(1); Ptô€€€1; Ptô€€€2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 A.6 Outsample mean pro t when a binary feature (f(2)) is available. (low/high correlated scalar feature, all demand cases, price processes IID, P1, P2, P3, P4 and P5), and parameters array con gurations h1 = [1; f(2)], h2 = [1; f(2); Ptô€€€1], and h3 = [1; f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . 76 A.7 (Cont. of Table A.6) Outsample mean pro t when a binary feature (f(2)) is available. (low/high correlated scalar feature, all demand cases, price processes P6, P7, P8, P9, P10), and parameters array con gurations h1 = [1; f(2)], h2 = [1; f(2); Ptô€€€1], and h3 = [1; f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 A.8 Outsample mean pro t when multiple features (f(1) and f(2) = high) are available. (low/high correlated scalar feature, all demand cases, price processes IID, P1, P2, P3, P4, P5), and parameters array con g urations h1 = [1; f(1); f(2)], h2 = [1; f(1); f(2); Ptô€€€1], and h3 = [1; f(1); f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 A.9 (Cont. of Table A.8) Outsample mean pro t when multiple features (f(1) and f(2) = high) are available. (low/high correlated scalar fea ture, all demand cases, price processes P6, P7, P8, P9, P10), and parameters array con gurations h1 = [1; f(1); f(2)], h2 = [1; f(1); f(2); Ptô€€€1], and h3 = [1; f(1); f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . 79 xii A.10 Outsample mean pro t when multiple features (f(1) and f(2) = low) are available. (low/high correlated scalar feature, all demand cases, price processes IID, P1, P2, P3, P4, P5), and parameters array con g urations h1 = [1; f(1); f(2)], h2 = [1; f(1); f(2); Ptô€€€1], and h3 = [1; f(1); f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 A.11 (Cont. of Table A.10) Outsample mean pro t when multiple features (f(1) and f(2) = low) are available. (low/high correlated scalar feature, all demand cases, price processes P6, P7, P8, P9, P10), and parameters array con gurations h1 = [1; f(1); f(2)], h2 = [1; f(1); f(2); Ptô€€€1], and h3 = [1; f(1); f(2); Ptô€€€1; Ptô€€€2].) . . . . . . . . . . . . . . . . . . . . . . 81 B.1 Dispersion of simulation results for i.i.d. Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 82 B.2 Dispersion of simulation results for l+ Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 83 B.3 Dispersion of simulation results for lô€€€ Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 84 xiii B.4 Dispersion of simulation results for h+ Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 85 B.5 Dispersion of simulation results for hô€€€ Demand (di . : di erence between theoretical and datadriven LP outsample mean pro ts in each outsample simulation runs for the same demandprice realiza tion), (values in parentheses: relative percentages of the values to the theoretical means, i.e. 100x Theoretical Mean ) . . . . . . . . . . . . . . . . . . 86 B.6 Dispersion of simulation results with features for scenario: IID Demand IID Price case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 B.7 Dispersion of simulation results with features for scenario: lô€€€ Demand  P1 Price case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 B.8 Dispersion of simulation results with features for scenario: h+ Demand  P7 Price case. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 C.1 i.i.d. Demand  i.i.d. Price insample/outsample CVaR results of CVaR Minimization LP and Expected Pro t Maximization LP . . . . 92 C.2 Mean CVaR no feature IIDP5 . . . . . . . . . . . . . . . . . . . . . . 93 C.3 Mean CVaR no feature P6P10 . . . . . . . . . . . . . . . . . . . . . 94 C.4 Mean CVaR f1 high IIDP1 . . . . . . . . . . . . . . . . . . . . . . . 95 C.5 Mean CVaR f1 high P6P10 . . . . . . . . . . . . . . . . . . . . . . . 96 C.6 Mean CVaR f1 low IIDP5 . . . . . . . . . . . . . . . . . . . . . . . . 97 C.7 Mean CVaR f1 low P6P10 . . . . . . . . . . . . . . . . . . . . . . . . 98 C.8 Mean CVaR f2 high IIDP5 . . . . . . . . . . . . . . . . . . . . . . . 99 C.9 Mean CVaR f2 high P6P10 . . . . . . . . . . . . . . . . . . . . . . . 100 C.10 Mean CVaR f2 low IIDP5 . . . . . . . . . . . . . . . . . . . . . . . . 101 xiv C.11 Mean CVaR f2 low P6P10 . . . . . . . . . . . . . . . . . . . . . . . . 102 C.12 Mean CVaR f1 high f2 high IIDP5 . . . . . . . . . . . . . . . . . . . 103 C.13 Mean CVaR f1 high f2 high P6P10 . . . . . . . . . . . . . . . . . . . 104 C.14 Mean CVaR f1 high f2 low IIDP5 . . . . . . . . . . . . . . . . . . . . 105 C.15 Mean CVaR f1 high f2 low P6P10 . . . . . . . . . . . . . . . . . . . 106 C.16 Mean CVaR f1 low f2 high IIDP5 . . . . . . . . . . . . . . . . . . . . 107 C.17 Mean CVaR f1 low f2 high P6P10 . . . . . . . . . . . . . . . . . . . 108 C.18 Mean CVaR f1 low f2 low IIDP5 . . . . . . . . . . . . . . . . . . . . 109 C.19 Mean CVaR f1 low f2 low P6P10 . . . . . . . . . . . . . . . . . . . . 110 C.20 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = low). . . . . . . . . . . . . . . . . . . . . . . . . 111 C.21 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = high). . . . . . . . . . . . . . . . . . . . . . . . 111 C.22 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(2) = low). . . . . . . . . . . . . . . . . . . . . . . . . 112 C.23 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(2) = high). . . . . . . . . . . . . . . . . . . . . . . . 112 C.24 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = high, f(2) = high). . . . . . . . . . . . . . . . . 113 C.25 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = high, f(2) = low). . . . . . . . . . . . . . . . . . 113 xv C.26 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = low, f(2) = high). . . . . . . . . . . . . . . . . . 114 C.27 The percentage of the di erence between outsample CVaR values of CVARLP and EPLP for di erent scenarios to the theoretical out sample means (f(1) = low, f(2) = low). . . . . . . . . . . . . . . . . . 114 C.28 Dispersion of simulation results of CVaR for hô€€€ Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 C.29 Dispersion of simulation results of CVaR for lô€€€ Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 C.30 Dispersion of simulation results of CVaR for i:i:d: Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 C.31 Dispersion of simulation results of CVaR for l+ Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 C.32 Dispersion of simulation results of CVaR for h+ Demand (CVARLP vs. Theoretical EP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 xvi LIST OF FIGURES 3.1 Simulation setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 A 100period sample path of normally distributed (mean: 100, vari ance: 25) i.i.d. price (case 1). x axis is the price and y axis is the periods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 100period sample paths of prices processes case P1 to case 10 (upper left is case P1, bottom right corner is case P10). x axis is the price and y axis is the periods. . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Distributions of CVaR values of CVARLP (Blue or Light) and TH EP (Red or Dark) for IID Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . 64 C.1 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P1 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 120 C.2 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P2 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 121 C.3 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P3 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 122 C.4 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P4 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 123 xvii C.5 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P5 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 124 C.6 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P6 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 125 C.7 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P7 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 126 C.8 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P8 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 127 C.9 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P9 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 128 C.10 Distributions of CVaR values of CVARLP (Blue) and THEP (Red) for P10 Price Process, and Demand Models hô€€€, lô€€€, i:i:d:, l+, and h+ (in descending order) . . . . . . . . . . . . . . . . . . . . . . . . . . 129 xviii NOMENCLATURE Xt the random variable X at period t FX the cumulative distribution function a random variable X Fô€€€1 X inverse of the cumulative distribution function a random variable X E[Xt] expected value of the random variable Xt Et[Xt] expected value of the random variable Xt, given that all the infor mation until time t is known. V ar(Xt) variance of the random variable Xt V art(Xt) variance of the random variable Xt, given that all the information until time t is known. Corr(Xt; Yt) correlation function of the random variables Xt and Yt Corrt(Xt; Yt) correlation function of the random variables Xt and Yt, given that all the information until time t is known. (:) Pro t function (:) Loss function f(i) t a data point of feature f(i), at time t h the parameters array (i) ith element of the parameters array, the coe cient of feature f(i). P expected value of the random variable E[P]). u penalty cost per item if the demand is satis ed from the spot market o penalty cost per item if the excess inventory is sold to the spot market xix CVaR Conditional ValueatRisk VaR ValueatRisk ARMA Autoregressive Moving Average Model EPLP the datadriven linear program with expected pro t maximization in the simulation model CVARLP the datadriven linear program with CVaR minimization in the sim ulation model THEP the theoretical benchmark of the expected pro t maximization in the simulation model xx Chapter 1 INTRODUCTION Procurement decisions of commodities are essential managerial decisions in most sectors, and due to di erent problem settings, the types of procurement decisions vary. This dissertation focuses on the procurement decisions of the single period in ventory models which are widely studied in Operations Research literature. Di erent from the classical single period inventory model, we focus on the procurement policies of commodities which have a spot market. The presence of the spot market entails several modi cations to the classical model. The selling price of the commodity is determined by the market price which is volatile. In addition, all the excess inven tories can be liquidated in the spot market by paying a penalty costs per unit item. Similarly, any unsatis ed demand can be met by the spot market. Although this problem de nition covers many commodities, it would be most suitable for electricity procurement, since the electricity can be traded in realtime via its spot market. The presence of a spot market changes the dynamics of the procurement problem in several ways. While it provides an immediate trade opportunity which causes high service levels, the volatility of the price increases the complexity of the procurement problem. Therefore, using solution methods derived for the constant price settings may not address the characteristics of the problem and the solutions might be sensitive to the price uctuations and may yield risky outcomes. Although there are certain so lution methodologies that are speci cally modeled for the volatile price environments, most of the solution methodologies in the existing literature require probability distri bution functions of the demand, and/or the price, and even the underlying stochastic model of the price process if the problem is de ned in a multiperiod environment, 2 Chapter 1: Introduction to be known. However, in practice these distributions are unknown and need to be estimated from previous data, or by any other technique. The methods which do not require the estimation of such distributions but use the historical data directly are called datadriven optimization. Datadriven optimization is a well studied topic in Operations Research literature, yet it became more popular in recent years because of the availability of abundant data in almost every sector. [Ban and Rudin, 2014] proposed a datadriven linear pro gramming approach to solve the classical Newsvendor Problem that uses the historical demand data as well as the data of exogenous variables (features) that are assumed to describe demand information. Their aim is to exploit the information provided by the exogenous variables to improve the maximum expected pro t yielded. We have modi ed the method provided by [Ban and Rudin, 2014] to solve the single period procurement problem of commodity with a spot market with expected pro t maxi mization objective (riskneutral), instead of the classical newsvendor formulation. In addition to historical data of demand and the exogenous variables, our model uses historical price information to develop a procurement policy with respect to the under lying price process of the spot market. We showed that the solution approach is able to generate optimal strategies for single period procurement problems of commodities which have a spot market. Another di culty in nding optimal procurement policies for commodities which are traded in a spot market is the pricedemand dependence. Since both demand and price are uncertain, they can possibly be correlated. The simulation results showed that our riskneutral model is capable of not only exploiting the information provided by the exogenous variables, but also nding optimal procurement policies in the presence of the pricedemand dependence. In addition to the riskneutral case, we have proposed a new solution approach for the riskaverse decision makers. Although nding theoretical results might be straightforward for the expected pro t maximization case, this is not true for the riskaverse case. The existing literature does not have a closed form solution that Chapter 1: Introduction 3 covers our problem de nition, when the risk aversion is applied via minimization of Conditional ValueatRisk measure (CVaR is explained in detail in Chapter 2). We have proposed a datadriven linear model which uses the Conditional ValueatRisk measure to implement riskaverse objective. Our model uses historical demand and price data as well as the exogenous variables to produce a riskaverse procurement policy. We showed that the approach is successful for certain price processes and pricedemand dependence levels. In order to test the performance of the proposed solution approaches we have constructed a simulation model. The simulation model generates stationary price processes with di erent characteristics in order to test the performance of the ap proaches under di erent cases. We also tested the e ect of pricedemand dependence, which would be important in case of commodities with spot market, by generating several additive demand model to generate di erent correlation levels between the price and the demand. We have generated synthetic features (exogenous variables) that are correlated with demand and tested di erent correlation levels and di erent functional forms. The simulation results showed that the expected pro t maximization case is able to generate nearoptimal policies for outsample tests for all price processes and dif ferent pricedemand dependence levels, for no feature cases. Although we do not have a theoretical benchmark for the cases when exogenous variables are available, the datadriven approach with features was able to outperform the no feature cases, and therefore we conclude that the datadriven approach is able to exploit the information provided by the features. The simulation results of the riskaverse case showed that the performance of the datadriven approach depends on the variance of the price process and the correlation level between the price and the demand. Although the datadriven approach is able make notable improvements for some cases, it is not able make improvements in terms of riskaversion with respect to the expected pro t maximization objective. Therefore, while the datadriven approach for the risk aversion case works well for certain cases, 4 Chapter 1: Introduction the approach may not be applicable for all cases. The structure of this document is as follows: In Chapter 2, problem de nition and the review of the related literature is presented. We also provided background information for the related concepts. Chapter 3 is on the datadriven linear program ming approach for solving the single period problem under two di erent objectives: expected pro t maximization, and the CVaR minimization (riskaverse). First the solution methods are introduced, then the simulation model is explained, and nally the simulation results are discussed. Detailed simulation results can be found in Ap pendix A, B and C. Finally, Chapter 4 is the conclusion part where the summary of the dissertation, as well as the key ndings and future research directions are presented. Chapter 2 LITERATURE REVIEW AND BACKGROUND In this chapter the problem de nition and solution strategies are introduced to position the contribution made to the existing literature. After a brief problem def inition, we present the preliminary information which is needed to understand the model and solution approaches. Then, the literature that is comparable to this work is reviewed. Problem De nition: Our problem is to nd the optimal procurement strategy of a commodity which is traded in a spot market. The retail price of the commodity changes over the discrete time intervals (periods) and it is determined by the spot market which evolves ran domly. The decision maker is assumed not to have an impact on the market prices, and s/he needs to satisfy an uncertain demand in each period. The decision maker cannot carry inventory, i.e. s/he always starts all periods with zero inventory. If the realized demand for the commodity happens to be greater than the total procurement quantity for that period, the shortage amount is satis ed from the spot market im mediately. However, a penalty cost u TL incurs per item purchased from the market. The analogous case, excess inventory, has the same condition. If the realized demand happens to be smaller than the total procurement for that period, the excess amount is sold to the spot market with a penalty cost of o TL per item. The mathematical relationship of the selling price and demand is modeled di erently for each chapter. In the following section (Section 2.1), we present a detailed de nition of the Con ditional Valueatrisk (CVaR), as well as its properties which make it more favorable than its alternatives. Section 2.2 will cover the existing literature on risksensitive decision making for the newsvendor problem, particularly via the CVaR risk measure, 6 Chapter 2: Literature Review and Background and the newsvendor problem in PriceDemand dependent environment. Section 2.3 introduces the existing literature on datadriven optimization and its applications on the newsvendor problem, and discusses the extensions to the problem de nitions such as the features a ecting the demand, and the newsvendor problems with meanCVaR objective function. 2.1 Conditional ValueatRisk Conditional ValueatRisk (CVaR), also known as expected shortfall, is a widely ac cepted risk measure and studied in the Operations Research literature extensively because of its intuitive de nition and convenient mathematical properties. CVaR of a random variable is the expectation of the values less than (1ô€€€ ) percentile of the random variable, i.e. CVaR equals to average of the smallest 100 % of the values of the corresponding random variable. [Rockafellar and Uryasev, 2000] rst proposed the formal de nition of CVaR and came up with the mathematical properties which made CVaR more preferable to alternative downside risk measures. Using the nota tion provided by [Rockafellar and Uryasev, 2000], f(x; y) is the loss function where x 2 Rn is the decision vector and y 2 Rm is the random vector with probability den sity function p(y). The probability of loss which does not exceed a given threshold is de ned as (x; ). (x; ) = Z f(x;y) p(y)dy We assume that (x; ) is continuous. A formal CVaR de nition and its mathematical properties for general loss distributions, without requiring a continuity assumption on the distribution function, can be found in [Rockafellar and Uryasev, 2002]. Let (x) be ValueatRisk with level ( VaR), and (x) be the Conditional ValueatRisk with level ( CVaR). (x) = minf 2 R : (x; ) g (x) = 1 1 ô€€€ Z f(x;y) (x) f(x; y)p(y)dy Chapter 2: Literature Review and Background 7 This representation requires calculation of (x), to calculate the (x). [Rockafellar and Uryasev, 2000] showed crucial mathematical properties can be found via the function F (x; ) which is de ned as; F (x; ) = + 1 1 ô€€€ Z y2Rm [f(x; y)) ô€€€ ]+p(y)dy [Rockafellar and Uryasev, 2000] proved that if F (x; ) is convex and continuously di erentiable in , the following expression holds. (x) = min 2R F (x; ) This expression indicates that the CVaR of a loss function can be calculated without calculation of the VaR of the function. Since it only requires to calculate an integral, numerical methods can be used to compute the CVaR value. [Rockafellar and Uryasev, 2000] also proved that minimization CVaR ( (x)) can be achieved by minimizing F (x; ) over x and . This theorem provides a handy optimization technique since F (x; ) can be minimized, to nd optimal  CVaR, otherwise direct minimization CVaR requires nding VaR rst which is not necessarily convex. Furthermore, since the integral can be approximated by a nite sum, in stochastic programming, CVaR can be modeled via linear equations which is not the case in VaR. Another advantage of using CVaR over VaR is its being a "Coherent Risk Mea sure". A risk measure is called coherent, if it satis es the following properties: mono tonicity, subadditivity, homogeneity, and translational invariance. The de nition is proposed in [Artzner et al., 1999], it de nes the properties a risk measure should have. CVaR satis es all the properties, while VaR fails to satisfy one of the proper ties (subadditivity). A detailed review on the coherence of CVaR, its advantages over VaR and its mathematical properties can be found in [Acerbi and Tasche, 2002a], [Acerbi and Tasche, 2002b], and [Tasche, 2002]. Since CVaR considers the expectation under a certain threshold, it is sensitive to the long tails. Therefore it is a more useful risk measure than its competing 8 Chapter 2: Literature Review and Background risk measures such as Value at Risk (VaR) to capture worst case scenarios with relatively high losses with respect to the mean of the distribution. A more for mal and general proposition stating the relation between VaR and CVaR can be found in [Bertsimas et al., 2004]. They examined the mathematical properties of CVaR and its relation with other risk measures such as VaR and standard deviation. [Bertsimas et al., 2004] also showed that meanshortfall optimization can be mod eled as a linear optimization model whereas the classical mean variance optimization method proposed by [Markowitz, 1952] for portfolio selection can only be modeled as quadratic problem. For continuous distributions, [Krokhmal et al., 2002] showed minimizing negative expected return (i.e. maximizing expected return) with a CVaR constraint yields the same e ciency frontier with minimizing CVaR with a constraint on expected return. Therefore, a stochastic optimization problem having a risk constraint can be modeled as a linear model by using CVaR as a risk measure. 2.2 Newsvendor Problem The Newsvendor Problem is a wellknown and researched problem in Operations Research. The problem is to nd the order quantity which maximizes expected pro t when there is an uncertain demand. If the realized demand happens to be greater than the order quantity, there is shortage penalty (s TL) for per unit excess demand. If the realized demand happens to be smaller than the order quantity, the excess inventory can be sold to salvage value (r TL). The unit selling price of item is p TL, and purchase cost of per item is c TL. The solution of the problem is straightforward and balances costs occurring in excess and shortage cases. The pro t function (q;D) is, (q;D) = (p ô€€€ c)D ô€€€ (p + s ô€€€ c)(D ô€€€ q)+ ô€€€ (c ô€€€ r)(q ô€€€ D)+ where q is the order quantity, and D is the random variable that represents the demand. FD denotes the cumulative distribution function of demand and optimal Chapter 2: Literature Review and Background 9 order quantity (q ) which maximizes the expected value of the pro t function is, q = Fô€€€1 D u u + o where u = p + s ô€€€ c is the underage cost, and o = c ô€€€ r is the overage cost. In our problem de nition, when the decision maker is restricted to make a decision to satisfy the demand of a single period, the resulting problem has a newsvendor problem representation. For the single period case, the cost of a unit of product is c TL, the retail price of the item, equivalently the market price during the selling period is P TL, and random demand realized in the selling period is D units. FD is the cumulative distribution function of the random demand D, and P is the expected retail price during the selling period. The single period pro t function of the decision maker is (q; P;D) = (P ô€€€ c)q ô€€€ u(D ô€€€ q)+ ô€€€ o(q ô€€€ D)+ Using the relation q = D ô€€€(D ô€€€q)+ ô€€€(q ô€€€D)+, the problem is equivalent to the classical newsvendor problem (q; P;D) = (P ô€€€ c)D ô€€€ (P ô€€€ c + u)(D ô€€€ q)+ ô€€€ (ô€€€P + c + o)(q ô€€€ D)+ with the corresponding underage cost u = P ô€€€c+ u, and overage cost o = ô€€€P +c+ o. Therefore, our problem is a version of the newsvendor problem where price is uncertain and the underage and overage costs are functions of this random price. 2.2.1 Newsvendor Problem with Risk Consideration Risk sensitive decision making in single period problems has been a popular topic. There is a number of di erent approaches to represent the risk in stochastic models. One of these approaches is to use utility theory which focuses on the optimization of the utility functions, since a utility function is the representation of one's risk pro le by de nition. Another method of modeling risk sensitivity is to use risk measures. Although there are plenty of di erent risk measures, I will focus on the literature on the CVaR, since it is the risk measure that I used in my model. 10 Chapter 2: Literature Review and Background [Ahmed et al., 2007] analyzed a newsvendor problem with a coherent risk measure minimization objective. They have both investigated single and multiperiod prob lems. In the single period case, they found that the structure of the optimal solution is similar to the original expected cost minimization problem. In addition to their solution framework for general coherent risk measures, for a special condition they provided a speci c solution for CVaR risk measure. [Gotoh and Takano, 2007] proposed a closed form solution to the single period problem with CVaR minimization objective. Using theorems proposed by [Rockafellar and Uryasev, 2000], F (q; ) function being the objective to be mini mized, F (q; ) = + 1 1 ô€€€ Z 2Rm [f(q; ) ô€€€ ]+p( )d where f(q; ) is the loss function associated with the newsvendor problem. [Gotoh and Takano, 2007] found optimal solutions for two di erent loss functions de ned from the newsvendor problem. For f(q; ) = ô€€€ (q; ), i.e. negative pro t or net loss, the optimal solution (q ; ) which minimizes F (q; ) is, q = o + v o + u Fô€€€1 D u(1 ô€€€ ) o + u + u ô€€€ v o + u Fô€€€1 D o + u) o + u = o(u ô€€€ v) o + u Fô€€€1 D o + u o + u + u ô€€€ v o + u Fô€€€1 D u(1 ô€€€ ) o + u where v = uô€€€s. Note that when there is no penalty cost (s = 0), the optimal solution has a much simpler form which is, q = Fô€€€1 D u o + u (1 ô€€€ ) = ô€€€uq [Chen et al., 2014] modeled the single period newsvendor model with CVaR as a satis cing measure which is used to ensure that the expected pro t reaches to a target with a given con dence level ( of CVaR). Since their model does not have shortage penalty, [Chen et al., 2014] have reached the same optimal solution with the Chapter 2: Literature Review and Background 11 no shortage penalty cost case of [Gotoh and Takano, 2007] which is intuitive because minimizing negative pro t and maximizing positive pro t are identical. To nd the optimal they implemented a binary search on . Finally, [Chen et al., 2014] have showed that mathematical characteristics of the solution are the same with the Cer tainty Equivalent formulation which is the utility function approach to model the risk. [Jammernegg and Kischka, 2007] used a meanCVaR approach to model risk  sensitive behavior of the decision maker. The objective function of their model is the convex combinations of CVaR and the expected pro t. According to the weights of these components, the problem can be turned into the original newsvendor problem to CVaR minimization problem. Therefore their model can grasp a wider spectrum of risk preferences. [Xu and Li, 2010] also worked on the same problem setting and they reached the same result with [Gotoh and Takano, 2007] for the CVaR minimization case, and a similar result with [Jammernegg and Kischka, 2007] for meanCVaR ob jective. However, the model of [Xu and Li, 2010] also includes the shortage penalty. [Choi and Ruszczy nSki, 2008] proved a broader result which establishes that any risk averse newsvendor problem with general law invariant coherent measure of risk, has an equivalent meanrisk objective representation, i.e. meanCVaR objective. [Xinsheng et al., 2015] approach to the riskaverse newsvendor problem from a di erent perspective. [Xinsheng et al., 2015] use a function called legacy loss rather than the pro t function, which only takes into account the cost parts of the original pro t function. [Xinsheng et al., 2015] found closed form solutions for minimization of expected legacy loss function, minimization of CVaR of legacy loss function and, minimization of their convex combinations (similar to the meanCVaR approach). 2.2.2 Newsvendor Problem with PriceDemand Dependence Although there are several papers on the newsvendor problem having pricedemand dependence, all of the papers cited above assume the price and demand are inde pendent, moreover none of them assumes that the price is a random variable. Price 12 Chapter 2: Literature Review and Background demand dependence is usually used to model the newsvendor problems with pric ing options. [Petruzzi and Dada, 1999] investigated a special version of the problem where the demand distribution is a function of the price and their model suggests that the decision maker can control not only the stock levels but also the selling price. [Petruzzi and Dada, 1999] have found the optimal strategy of choosing selling price and stock levels for maximizing expected pro t under given conditions for both linear and multiplicative demandprice dependence. [Agrawal and Seshadri, 2000] took a step further and considered the riskaverse de cision makers, too. Similar to [Petruzzi and Dada, 1999], the decision maker should decide on the price and the order quantity, and the demand depends on the price. Nevertheless their objective is to maximize a utility function rather than the pro t maximization. For the risk neutral utility functions, which is identical to pro t max imization, [Agrawal and Seshadri, 2000] found slightly di erent results with respect to [Petruzzi and Dada, 1999], because of di erences in problem de nitions. For the risk averse case, [Agrawal and Seshadri, 2000] reported how optimal decisions change with respect to the risk neutral case. Although their work encapsulates both risk aversion and pricedemand dependence for single period inventory models, there are two major factors which di erentiate my work from theirs. First, they have used util ity functions to measure risk rather than a risk measure, particularly CVaR. Second, they had control over the price, which my model does not cover. The model proposed by [Chen et al., 2009] covers both the CVaR criterion and pricedemand dependence. They modeled the demand as a function of price and a random variable (D(p) = d(p;X)). If the demand function satis es certain mathemat ical properties whose details can be found in their paper, for a xed price and general demand distributions, they found similar results to the independent price case. The optimal order quantity as a function of price is q (p) = Fô€€€1 ô€€€ p; u o+u(1 ô€€€ ) where F(p; x) is the c.d.f. of d(p;X) (note that, there is no shortage penalty cost). They also investigated the cases which price is also a decision variable. [Chen et al., 2009] showed that, for both multiplicative and additive cases of demand a unique optimal Chapter 2: Literature Review and Background 13 price exists; in addition to that, for the additive case it is less than the riskneutral optimal price. [Xu, 2010] studied a very similar problem, the only di erence is that, the excess demand can be satis ed via emergency procurement which inhibits the lost sale case. The results are signi cantly similar to [Chen et al., 2009], except for the small deviations due to the lack of lost sales. While its problem de nition is similar to the problem proposed, [Chen et al., 2009] fails to respond the modi cations on newsvendor problem where price is a random variable and underage and overage costs are the functions of price. The other major di erence of their model is the role of price in their problem. Since they have sug gested pricedemand dependence in order to observe the e ect of the pricing decisions and price is a decision variable in their model. Therefore, the solution provided by [Chen et al., 2009] does not cover the problem proposed. For a more broad and detailed review of literature and recent publications on newsvendor problem, please refer to [Qin et al., 2011]. 2.3 DataDriven Optimization Di erent optimization approaches have been used in order to nd the optimal order quantities in single period inventory problems (the Newsvendor Problem) under dif ferent objectives. Even though we assume that the demand distributions are known and apply the probability laws to nd the optimal levels, in real life the demand distributions are not known and they should be estimated from historical demand data. The classical approach rst estimates the demand probability distribution and its parameters based on the historical data, then performs optimization based on the estimated parameters. There are several alternatives to this classical separated estimation and optimiza tion approach. [Liyanage and Shanthikumar, 2005] proposed operational statistics which combines the estimation of distribution parameters and optimization to solve inventory models. [Akcay et al., 2011] showed the e ect of length of historical de mand data and several other factors on the accuracy of the optimization in the 14 Chapter 2: Literature Review and Background separated parameter estimation and optimization case, and they showed optimal or dering levels considering the uncertainty caused by the estimation of the demand parameters. These approaches are called parametric approaches, since they still es timate the distribution parameters. However there are nonparametric approaches where the optimization model does not require the estimation of a parametric dis tribution function. More information can be found in [Godfrey and Powell, 2001], [Huh and Rusmevichientong, 2009] , and [Huh et al., 2011] about di erent nonparametric approaches used to solve inventory problems. Datadriven optimization is another nonparametric approach which does not re quire to estimate the distributions of the random variables but uses historical ob servations directly in the mathematical models. In this section, we will focus on the datadriven optimization methods where the demand distribution is unknown but the historical demand data is available. [Kleywegt et al., 2002] proposed a method called Sample Average Approximation (SAA) to solve stochastic optimization problems via Monte Carlo simulation approach. The method can be summarized as follows; sup pose that the minimum value of the expectation of a function g(q;D) is r , where q is a real valued decision vector and de ned in nite set Q, and D is a random variable. r can be found by the following expression: r = min q Q E[g(q;D)] If a set containing n realizations of the random variable D (i.i.d. random samples, d = [d1; :::dn]) is available , the SAA of r is ~ r and it is de ned as; ~ r = min q Q 1 n Xn i=1 g(q; di) [Kleywegt et al., 2002] showed that ~ r converges to r as n increases. [Kleywegt et al., 2002] were able to report the bounds on the number of samples required to achieve a speci c performance level. [Shapiro, 2003] investigated the sta tistical properties of the results of the algorithm. [Levi et al., 2007] applied Sample Average Approximation to the newsvendor problem, and found the bounds of number Chapter 2: Literature Review and Background 15 of samples required to have a close performance to the case where the demand distri bution is known. Later, the bound was signi cantly improved by [Levi et al., 2015]. [Ban and Rudin, 2014] used datadriven optimization techniques to nd optimal order quantity of a newsvendor problem, where the demand distribution is unknown but the historical demand data is known prior. Contrary to others, their work also considers the extra information available which might help to describe the demand distribution. [Ban and Rudin, 2014] assume that for each period there is a feature vector f which can describe the demand information with the following relation D = g(f) + . The demand can be represented as Taylor Series Expansion of g. In other words, there exists a multivariate polynomials of feature vector which describes the demand. The feature vector f is known prior to the demand realization. Some of the possible examples of features are the dependent random variables, seasonality, location, weather, or any information which is related to demand and available prior to the realization of demand. [Ban and Rudin, 2014] proposed a modi ed version of SAA which aims to exploit the information provided by the features. Suppose that the C(q;D) is the cost func tion of the newsvendor model, where q is the order quantity, the minimization of expected cost of the newsvendor model can be expressed as, min q E[C(q;D)] In case of the presence of a feature vector f, the minimization of the expected cost of the newsvendor problem is expressed as, min q E[C(q(f);D(f))jf] The features are denoted as f = [[f(1) 1 ; :::; f(1) n ]; [f(2) 1 ; :::; f(2) n ]; :::; [f(m) 1 ; :::; f(m) n ]], the demand is denoted as d = [d1; :::; dn], where there are n periods, and m features. The proposed formulation is as follows; min q:q(f)= Pm j=1 (j)f(j) 1 n Xn i=1 C(q(f); di) 16 Chapter 2: Literature Review and Background A more detailed LP formulation of this model is explained in Chapter 3.2.2. For two example cases, they showed that the suggested algorithm has a nite bias and yields asymptotically optimal solutions whereas the Sample Average Approximation method which does not include features in the decision criteria has nite bias and yields suboptimal (inconsistent) solutions. In addition, they showed the bounds on the outofsample performances of the algorithm. [Ban and Rudin, 2014] suggested a quadratic programming version of the model which limits the number of features in the decision criteria by adding a regularization term to the objective function. [Sachs and Minner, 2014] also worked on the datadriven newsvendor problem when the demand data is censored. Similar to [Ban and Rudin, 2014], thier model es timates the order quantity as a linear function of exogenous variables, by constructing a linear program which uses historical data. Although their approaches were similar, [Sachs and Minner, 2014] focused on the numerical comparison of the algorithm with benchmarks cases and measured the e ect of problems settings such as the number of available data, pricedemand dependence, etc. However their paper does not provide the mathematical model de nitively for the exogenous variables case. Therefore we will refer to [Ban and Rudin, 2014] for introducing exogenous variables in datadriven optimization literature. Risk sensitive datadriven newsvendor formulations also exist in the literature. [Zhang et al., 2009] used Sample Average Approximation method to solve newsvendor problem with a CVaR constraint and analyzed the convergence rates of solutions with respect to the number of samples. Similarly, [Choi and Ruszczy nSki, 2008] used a sample based linear problem (datadriven) to solve newsvendor problem with mean CVaR objective. For portfolio optimization, [Karoui et al., 2011] proposed a di erent technique called Performance Based Regularization, and they showed that it performs better than Sample Average Approximation method for meanCVaR objectives. Among the literature cited throughout this section, [Ban and Rudin, 2014], in terms of solution methodology, and [Choi and Ruszczy nSki, 2008] and [Zhang et al., 2009], in terms of the risk minimization approaches, are the most related pieces of works Chapter 2: Literature Review and Background 17 that are most related to Chapter 3 of my thesis. Nevertheless, [Ban and Rudin, 2014] does not address the risk averse behavior but focuses on the expected pro t maxi mization. Another important di erence between [Ban and Rudin, 2014] and Chapter 3 is the de nition of the price. While [Ban and Rudin, 2014] uses a constant price, my model has a random process which might be correlated with the random demand. In addition the main focus of Chapter 3 is to show the impact of the price process on the decision of datadriven optimization model. In contrast to [Ban and Rudin, 2014], works of [Choi and Ruszczy nSki, 2008] and [Zhang et al., 2009] both consider risk important and use CVaR as a risk measure. However their models do not address the e ect of neither the exogenous features nor the price uncertainty, and possible correlation between price and demand. Therefore [Zhang et al., 2009] fail to solve the problem proposed. Robust optimization is another method for solving stochastic problems in a risk averse manner. While the robust optimization is a way to solve the stochastic prob lems, its way of handling uncertainty is di erent than the other models. It aims to protect the system from the worst case scenarios caused by the uncertainty. In other words, it nds to best decision when all the decisions are countered by the worst pos sible realizations within the uncertainty set. The datadriven approach is widely used in robust optimization problems. Rather than being a way of avoiding risk in decision making, and its relevance to the datadriven optimization, robust optimization theory and its applications are less relevant to my work, because of the unique way of de n ing its objective. More information on datadriven robust optimization can be found in [Bertsimas and Thiele, 2006]. A datadriven robust optimization formulation of newsvendor problem can be found in [Bertsimas and Thiele, 2005]. Chapter 3 SINGLEPERIOD PROCUREMENT POLICY VIA DATADRIVEN LP As explained in detail in Chapter 2, datadriven optimization is a nonparametric optimization approach where the decision maker uses the historical data directly to make a decision without estimating the parameters of the underlying distributions of the data available. In this chapter, a datadriven linear programming approach is proposed to deter mine the procurement policy of the problem de ned in the following section. We will investigate the procurement strategies for the cases where the decision maker is risk neutral and risk sensitive. The risk neutral case aims to maximize its expected pro t whereas the risk averse case aims to minimize the Conditional Value at Risk of the loss function (negative pro t), as it is reviewed in Chapter 2. The structure of this chapter is as follows; after the problem de nition, the rst section is on the solution methods of the risk neutral case (expected pro t maximiza tion). First, a closed form solution for the expected pro t maximization objective is proposed when no features are available. Then, we introduce the datadriven tech niques to solve cases which can exploit the information provided by the available features. After a detailed explanation of [Ban and Rudin, 2014], the datadriven LP formulation which provides a basis for our solution methodology, we proposed a data driven linear program to generate a solution to our problem when the features are available. The next section, another datadriven LP formulation is proposed for the risk averse case (CVaR minimization) when features are available. Since the perfor mance of the datadriven approaches are evaluated by simulation, the next section is the detailed explanation of simulation procedure, selection of parameters, and prepa Chapter 3: Singleperiod Procurement Policy via DataDriven LP 19 ration of simulation environment. Finally, the last section is on the analysis of the simulation results. 3.1 Problem De nition Similar to the classical newsvendor problem, the decision maker needs to satisfy an uncertain demand (D units) occurring in a speci c time interval, and will make an order before the demand is observed. While the wholesale price per item (c TL) is known before the decision is made, the retail price of the commodity (P TL) is uncertain and will not be realized until the demand is observed. The retail price is determined by the spot market of the commodity. The decision maker is assumed to have no e ect on the spot market price. The commodity is perishable, i.e. excess amount of items cannot be stored for the upcoming periods. However, the decision maker is able to sell excess inventory to the spot market with a penalty cost per item ( o TL) after the demand and the price is realized. Therefore, in case of excess inventory, the decision maker will sell any amount of goods to the spot market with price (P ô€€€ o) TL. The analogous case is also true. In case of shortage, the decision maker may satisfy the demand from the spot market with a penalty cost per item ( u TL). In other words, any amount of goods can be purchased from the spot market with price (P + u) TL. Therefore, the pro t function of the decision maker is (q; P;D), where q is the order quantity. (q; P;D) = (P ô€€€ c)q ô€€€ u(D ô€€€ q)+ ô€€€ o(q ô€€€ D)+ The decision maker does not know the distribution function of the demand as well as underlying price process of the spot market prices. S/he needs to use the historical data of the demand and the spot market prices for n periods and historical data of exogenous variables (features), to nd the optimal order quantity. The features are the variables which are possibly correlated with the demand and/or the price, and can be observed prior to demand, and price realization. Examples of the features could be the weather data (such as temperature, wind, humidity etc.), the data of 20 Chapter 3: Singleperiod Procurement Policy via DataDriven LP nancial indicators (such as historical exchange rates, stock market prices, etc.), date information in order to capture the seasonality if it exists, or any possible available data which might be related to the demand and/or price. Now, assume that there are m features each having the information of n pe riods. The vector [f(i) 1 ; f(i) 2 ; :::; f(i) n ] contains the data of feature i for i = 1; :::;m. The vector f contains all the features, f = [[f(1) 1 ; f(1) 2 ; :::; f(1) n ]; [f(2) 1 ; f(2) 2 ; :::; f(2) n ]; :::; [f(m) 1 ; f(m) 2 ; :::; f(m) n ]]. Using the historical data available for demand d = [d1; d2; :::; dn], the historical data available for price p = [p1; p2; :::; pn], and the feature vector f the decision maker aims to nd the optimal order quantity which yields the best outcome for his/her objective function. 3.2 Maximization of Expected Pro t In this section, we will investigate the solution methods when the objective of the decision maker is to maximize his/her expected pro t. We rst propose a theoretical solution for when no exogenous variables (features) are available. In the following part, the datadriven linear programming approach proposed by [Ban and Rudin, 2014] is explained. Then a datadriven linear model is formulated by using their approach to solve our problem. Finally, a modi ed version of the linear model is proposed to improve the performance of the model in terms of the memory requirements. 3.2.1 Theoretical Solution for No Feature Case Proposition 1. The closed form solution for the optimal order quantity q which maximizes the expected pro t at period t when all the information until time t is known, q = arg max q 0 Et[(Pt ô€€€ ct)q ô€€€ u(Dt ô€€€ q)+ ô€€€ o(q ô€€€ Dt)+] Chapter 3: Singleperiod Procurement Policy via DataDriven LP 21 is q = 8>>>>>< >>>>>: 0 Et[Pt] ô€€€ ct ô€€€ u Fô€€€1 Dt Et[Pt]ô€€€ct+ u u+ o ô€€€ u < Et[Pt] ô€€€ ct < o +1 o Et[Pt] ô€€€ ct where Pt is the price in period t, Dt is the demand in period t and ct is the procurement price in period t, and Et[:] is a conditional expectation where all the information until time t is known. Proof. Let us note that: Et[ (q; Pt;Dt)] = Et[(Pt ô€€€ ct)q] ô€€€ uEt[(Dt ô€€€ q)+] ô€€€ oEt[(q ô€€€ Dt)+] The derivative with respect to q is: @Et[ (q; Pt;Dt)] @q = (Et[Pt] ô€€€ ct) + u(1 ô€€€ FDt(q)) ô€€€ oFDt(q) and the second derivative is: @2Et[ (q; Pt;Dt)] @q2 = ô€€€( u + o)fDt(q) Since the second derivative is always negative ( o, and o are nonnegative by de  nition), the function is concave, and q which satis es @Et[ (q;Pt;Dt)] @q = 0 will be the optimal order quantity. (Et[Pt] ô€€€ ct) + u(1 ô€€€ FDt(q)) ô€€€ oFDt(q) = 0 if Et[Pt] ô€€€ ct ô€€€ u, q = 0 if ô€€€ u < Et[Pt] ô€€€ ct < o, q = Fô€€€1 Dt Et[Pt] ô€€€ ct + u u + o if o Et[Pt] ô€€€ ct, q = +1 22 Chapter 3: Singleperiod Procurement Policy via DataDriven LP 3.2.2 [Ban and Rudin, 2014], DataDriven Linear Programming Approach for the Newsvendor Problem As it is brie y explained in Chapter 2.3, [Ban and Rudin, 2014] proposed a data driven linear program to generate an ordering policy which minimizes the expected cost of the classical Newsvendor Problem (Chapter 2.2). Suppose that the decision maker does not know the true distribution of the demand (D), yet s/he has the historical data of the demand (d = [d1; :::dn]) and a set of features f = [[f(1) 1 ; :::; f(1) n ]; [f(2) 1 ; :::; f(2) n ]; :::; [f(m) 1 ; :::; f(m) n ]] which is believed to explain the demand information in the form of linear combinations. The proposed linear programming model which combines Sample Average Ap proximation approach with information of feature set is, Sets I : set of periods, historical data of which are available, I = f1; :::; ng J : set of features, J = f1; :::;mg Parameters c : wholesale price of the item u : underage cost per unsatis ed demand o : overage cost per unsold item di : demand in period i, 8i 2 I f(j) i : the value of feature j in period i, 8i 2 I, and 8j 2 J Decision variables xi : order quantity in period i, 8i 2 I q+ i : (xi ô€€€ di)+, i.e. amount of unsold products in period i, 8i 2 I qô€€€ i : (di ô€€€ xi)+, i.e. amount of unsatis ed demand in period i, 8i 2 I (j) : weight of feature j on the order quantity , 8j 2 J Mathematical Model Chapter 3: Singleperiod Procurement Policy via DataDriven LP 23 min =[ (1);:::; (m)] 1 n Xn i=1 (uqô€€€ i + oq+ i ) s:to 8i = 1; :::; n: qô€€€ i di ô€€€ (1) ô€€€ Xm j=2 ( (j) + f(j) i ) q+ i (1) + Xm j=2 ( (j) + f(j) i ) ô€€€ di qô€€€ i ; q+ i 0 Note that this model provides a vector = [ (1); :::; (m)] which minimizes expected cost of newsvendor problem over the sample data set. [Ban and Rudin, 2014] claim that the decision maker can use the resulting vector to nd the order quantity (qt(ft)) for a period t which is not used to train the model (outofsample), using corresponding period's features ft, i.e. qt(ft) = Pm i=1 (j)f(j) t . 3.2.3 Mathematical Model for Maximization of Expected Pro t Our claim is that the decision maker can modify the datadriven linear programming approach proposed by [Ban and Rudin, 2014], to solve the problem de ned in Section 3.1. Although the problem is similar to the classical newsvendor model, there are major di erences such as the random price and underage and overage costs are being functions of that random demand. Our claim is that a similar approach to [Ban and Rudin, 2014] su ces to generate optimal solutions when the exogenous vari ables (features) are available. Since the decision maker aims to maximize the expected pro t function when the historical data is available, the objective function is, max x 0 E[ (x; P;D)j(d; p; f)] We constructed h, the parameters array, by using the features and other available information such as historical data of price process. The parameters array is similar 24 Chapter 3: Singleperiod Procurement Policy via DataDriven LP to the feature vector f of [Ban and Rudin, 2014]. We chose to denote it di erently to emphasize that it does not only consist of exogenous variables, but it may also include endogenous variables such as previous price realizations. The claim of [Ban and Rudin, 2014] requires a linear dependence between exoge nous features (or their functions) and the demand, in order to be able to use the solution methodology. We extend their claim, and suggest that if the selling price is volatile and generated by a random process, historical price information (or the functions of which) can be used alongside with the available exogenous variables in the parameters array h. We claim that, there exists an array of parameters, h, a linear combination of which yields a nearoptimal solution for the problem. ~ x i = Xjhj j=1 jhij where ~ x i is the nearoptimal solution for the ith period. Since is the vector of coe cients, the aim of the mathematical model is to nd the vector to evaluate order quantity ~ x i given a parameters array h. The mathematical model chooses the optimal vector to maximize the sample mean pro t of the previous periods. The resulting vector which generates optimal ~ x i for each period to yield the maximum pro t is used to nd the optimal order quantity for the upcoming period. The decision maker is faced with the question of how to construct a correct pa rameter array h which su ces to represent the characteristics of an ordering decision. While the scope of this thesis does not cover the optimal strategy of obtaining the optimal parameter array h, the performances of di erent parameter arrays under dif ferent scenarios will be tested by simulation in the following section. Even though this does not provide an optimal strategy, it will help the decision maker in the process of selecting the parameter array. For instance, if the price is assumed to have an autoregressive process where price of ith period is heavily depends on the previous price. Then, the price of (i ô€€€ 1)th period can possibly be selected as one of elements of the parameters array to re ect the e ect of ith price on the (i + 1)th price, consequently on the ~ x i . Furthermore, Chapter 3: Singleperiod Procurement Policy via DataDriven LP 25 let's assume that the demand is correlated with a feature observed in ith period. Therefore, the resulting parameters array for the ith period to be used to evaluate the order quantity can be selected as hi = [1; piô€€€1; f(1) i ], for all i. Note that, the rst element of the parameters array is selected as 1. Even though it is not mandatory to allocate rst term to 1, it is a useful practice since it provides a historical data free coe cient 1 which may serve as an intercept term. Note that any function of the historical data can be used while constructing the parameters array. For instance, addition to the example case above, if the demand during the weekends happens to be greater than the weekdays, the decision maker may add an indicator function of date data, i.e. Iff(2) i 2[Saturday;Sunday]g where f(2) i is the date information of ith period and I is the indicator function, Itrue = 1 and Ifalse = 0. Then the resulting parameters array for the ith period can be hi = [1; piô€€€1; f(1) i ; Iff(2) i 2[Saturday;Sunday]g]. The decision maker is free to make any linear or nonlinear transformation to the historical data to come up with a parameters array h. A sample parameters array for the ith period hi could be hi = [1; (piô€€€1)2; diô€€€7; (diô€€€1piô€€€1); Iff(1) i 0g; q f(2) iô€€€1; log( f(3) i 1 ô€€€ f(3) i )] After the parameters array h is constructed, the mathematical model is solved to nd vector which maximizes the optimal expected pro t of the sample data available. Sets I : set of periods, historical data of which are available, I = f1; :::; ng H : set of parameters, H = f1; :::;mg Parameters pi : retail price of the item in period i, 8i 2 I ci : wholesale price of the item in period i, 8i 2 I di : demand in period i, 8i 2 I u : penalty cost per item if the demand is satis ed from the spot market 26 Chapter 3: Singleperiod Procurement Policy via DataDriven LP o : penalty cost per item if the excess inventory is sold to the spot market hij : value of parameter j in period i, 8i 2 I, and 8j 2 H Decision variables xi : order quantity in period i q+ i : (xi ô€€€ di)+, i.e. amount of product sold to spot market in period i qô€€€ i : (di ô€€€ xi)+, i.e. amount of product purchased from the spot market in period i j : weight of parameter j on the order quantity, 8j 2 H Mathematical Model max 1 n Xn i=1 (pi ô€€€ ci)xi ô€€€ oq+ i ô€€€ uqô€€€ i s:to 8i 2 I xi = Xm j=1 jhij q+ i xi ô€€€ di qô€€€ i di ô€€€ xi xi; q+ i ; qô€€€ i 0 The linear model has the following memory requirements; for jIj = n, and jHj = m, the number of decision variables is 3n + m, the number of constraints is 3n, and the number of nonnegativity constraints is 3n. Although the model above is straightforward and easy to comprehend, there is a better way of implementing the problem. By not de ning the variable x, the user may decrease the memory need of the model. Modi ed Version of the Model max 1 n Xn i=1 (pi ô€€€ ci) Xm j=1 jhij ô€€€ oq+ i ô€€€ uqô€€€ i s:to 8i 2 I q+ i Xm j=1 jhij ô€€€ di Chapter 3: Singleperiod Procurement Policy via DataDriven LP 27 qô€€€ i di ô€€€ Xm j=1 jhij Xm j=1 jhij 0 q+ i ; qô€€€ i 0 The modi ed version has the following memory requirements; for jIj = n , and jHj = m, the number of decision variables is 2n+m, the number of constraints is 3n, and the number of nonnegativity constraints is 2n. Although, we assure that this model maximizes insample expected pro t, its out sample performance should be tested. In Section 3.4, a simulation model is proposed to test both insample and outsample performance of the model for di erent price processes, di erent demand models to simulate di erent pricedemand dependence, di erent features, and di erent parameters array selections. 3.3 Minimization of CVaR Consider the case where the decision maker is riskaverse and willing to manage its risk by having a di erent objective function. Rather than maximizing the expec tation of the pro t function, s/he will minimize the CVaR of the distribution of a loss function (x; y) where x is the decision variable and y is the uncertain vector. First, the mathematical model for the datadriven CVaR minimization of the prob lem is presented in this section. Then, a modi ed version is proposed to improve the performance of the model in terms of the memory requirements. In addition to the variables and parameters de ned for the expected pro t maxi mization model (Section 3.2.3), Proposition 2 requires the introduction of the follow ing parameters and variables: is parameter denoting the CVaR level, variable is the resulting VaR level of the CVaR, i is the pro t acquired in period i, and zi is an auxiliary variable. 28 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Proposition 2. The following linear program minimizes the insample CVaR of the loss function ô€€€ (q; P;D), where (q; P;D) = (P ô€€€c)qô€€€ u(Dô€€€q)+ô€€€ o(qô€€€D)+, when features are available. Mathematical Model min + 1 (1 ô€€€ )n Xn i=1 zi s:to 8i 2 I xi = Xm j=1 jhij i = (pi ô€€€ ci)xi ô€€€ oq+ i ô€€€ uqô€€€ i zi ô€€€ ô€€€ i q+ i xi ô€€€ di qô€€€ i di ô€€€ xi xi; zi; q+ i ; qô€€€ i 0 Proof. Note that, CVaR is the expectation of the losses exceeding a threshold , which is percentile of the loss distribution. Suppose that p.d.f. of a loss function (x; y) is f (y) (where x is the decision vector, and y is the random vector. See Section 2.1 for a detailed de nition of CVaR risk measure). If (x; y) is convex for a xed y, [Rockafellar and Uryasev, 2000] showed that minimization of CVaR of loss function (x; y), can be achieved by minimization of F (x; ) which is de ned as, F (x; ) = + 1 1 ô€€€ Z y2Rm [ (x; y)) ô€€€ ]+f (y)dy Furthermore, [Rockafellar and Uryasev, 2000] also proposed that F (x; ) can be ap proximated by the sampling of the random vector y. F^ (x; ) = + 1 1 ô€€€ Xn i=1 [ (x; yi) ô€€€ ]+ where [y1; y2; :::; yn] vector consists of n realizations of the random vector y. Chapter 3: Singleperiod Procurement Policy via DataDriven LP 29 In our problem the loss function is the negative of the pro t function ( (x; [p; d]) = ô€€€ (q = x; p; d)) which is, (x; [p; d]) = ô€€€(p ô€€€ c)x + u(d ô€€€ x)+ + o(x ô€€€ d)+ Note that in order to use F^ (x; ) to minimize CVaR of the loss function, (x; y) should be convex in x. (x; [p; d]) can be represented as piecewise linear functions. (x; [p; d]) = 8>< >: (ô€€€p + c ô€€€ u)x + ud x < d (ô€€€p + c + o)x ô€€€ od d x (x; y) is continuous, i.e. (d; [p; d]) = (ô€€€p+c)d, and it is convex in x for a xed [p; d], when o > ô€€€ u which is always true since o and u are nonnegative by de nition. Therefore our problem is to minimize F^ (x; ), min x; + 1 1 ô€€€ Xn i=1 [ô€€€ (x; pi; di) ô€€€ ]+ The expression above can be turned into a linear form by removing [:]+ function. We introduce the auxiliary variables zi, as [Rockafellar and Uryasev, 2000] suggested. min x; + 1 1 ô€€€ Xn i=1 zi s:to 8i 2 I zi ô€€€ (x; pi; di) ô€€€ zi 0 A datadriven approach similar to [Ban and Rudin, 2014], can be implemented to this problem as follows; min x; + 1 1 ô€€€ Xn i=1 zi s:to 8i 2 I xi = Xm j=1 jhij i = (pi ô€€€ ci)xi ô€€€ oq+ i ô€€€ uqô€€€ i 30 Chapter 3: Singleperiod Procurement Policy via DataDriven LP zi ô€€€ i ô€€€ q+ i xi ô€€€ di qô€€€ i di ô€€€ xi xi; zi; q+ i ; qô€€€ i 0 The CVaR minimization model has the following memory requirements; for jIj = n, and jHj = m, the number of decision variables is 5n + m + 1, and the number of constraints is 5n, and the number of nonnegativity constraints is 4n. The memory need of this model can be decreased by eliminating the variables x and , leading to the following modi ed model. Modi ed Version min + 1 (1 ô€€€ )n Xn i=1 zi s:to 8i 2 I zi ô€€€ ô€€€ (pi ô€€€ ci) Xm j=1 jhij + oq+ i + uqô€€€ i q+ i Xm j=1 jhij ô€€€ di qô€€€ i di ô€€€ Xm j=1 jhij Xm j=1 jhij 0 zi; q+ i ; qô€€€ i 0 The modi ed version of the CVaR minimization has the following memory re quirements; for jIj = n , and jHj = m, the number of decision variables is 3n+m+1, the number of constraints is 3n, and the number of nonnegativity constraints is 3n. Chapter 3: Singleperiod Procurement Policy via DataDriven LP 31 Although this model generates minimum CVaR for the periods that is trained (insample), its performance should be tested for outsample data. The simulation model is proposed to test both insample and outsample performance of the model for di erent settings in the following section. 3.4 Simulation Model The performance of the datadriven linear programs that are proposed to solve the procurement problem is measured by a simulation model. The simulation model is constructed to test as many scenarios as possible in order to show the solution methodology is capable of providing solution to a wide range of di erent scenarios. The simulation model tests a combination of 11 di erent price processes, 5 dif ferent pricedemand relations and 2 exogenous variables (one continuous, one bi nary) each having 2 di erent correlation levels with demand, which results 11(price process) 5(demand model) 3(continuous feature) 3(binary feature)= 495 di erent scenarios. For each problem scenario, the parameters are selected in such a way that the comparison between the scenarios is possible, i.e. the same and stationary mean for all the price processes, the same variance or the conditional variance (variance at time t when all the information until time t ô€€€ 1 is known), same mean for each demand scenario, and the same variance or the conditional variance for demand. In addition, the random seed, which is used to generate realizations of random variables, is di erent for all iterations, but the same within an iteration for di erent problem scenarios in order to eliminate the possible anomalies caused by chance. Within an iteration, 495 di erent but equivalent scenario data is generated for 400 consecutive periods each. For each scenario two datadriven approaches are applied to the problem, datadriven linear programs having expected pro t maximization(risk neutral) and CVaR minimization(risk averse). Furthermore, for each linear program, 12 di erent parameter arrays is used to solve each 495 unique problem. Therefore, the simulation model provides the most suitable parameters arrays for the speci c scenario. 32 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Each di erent scenario with 400 periods is solved with 2 di erent objective and each objective have 12 di erent solution setup (parameters array) which yields 24 di erent vectors which are the outcomes of the linear programs. Each vector is the vector yields the optimal objective value for its objective function given the scenario data. The data that are used to evaluate vector is called training data. The accuracy of the model can only be measured via out of sample tests. Therefore, for each iteration and for each scenario, 100 di erent sample paths of 200 periods are simulated which are called test data. The vector evaluated using training data is tested for 100 di erent test data, for each theta, for each scenario and for each iteration. Figure 3.1: Simulation setup 100 replications z } { Training Sample Test Samples 400 periods 200 periods  {z } 100 di erent sample paths The procedure is repeated for 100 iterations and the resulting statistics are ana lyzed at the last section of this chapter. The following part of this chapter presents the detailed explanations for model and parameter selections to construct di erent scenarios, selection of parameters array, and selecting benchmarks. 3.4.1 Price Process Settings While constructing di erent scenarios to be tested, the selection of the price process model is the primary decision. Since the price is determined via a spot market, the model to be selected should show the characteristics of a spot market model while having the exibility to re ect di erent patterns. Furthermore, despite re ecting di erent patterns, the process should be comparable among di erent cases. Therefore, I chose the price process to be an ARMA (Autoregressive  Moving Average Model) Chapter 3: Singleperiod Procurement Policy via DataDriven LP 33 model with di erent parameters which is able to re ect a wide range of di erent patterns. ARMA is a time series model, and it has the following mathematical representa tion, Pt = k + "t + Xp i=1 iPtô€€€i + Xq j=1 j"tô€€€j This process is called ARMA(p; q). Pt is the price at period t (autoregressive terms), and "t is the moving average term at period t, and k is a constant. "t are i.i.d. random variables with variance 2. Note that the price process is stationary, i.e. p = E[Pt] = E[Pt+1]; 8t 0, if all zeros of lie outside of the unit circle. If the process is stationary, then the mean of the process can be found by using this formula: p = k 1 ô€€€ 1 ô€€€ 2 ô€€€ ::: ô€€€ p Variance of the process V ar(Pt) depends on the coe cients of the autoregressive and moving average terms. I will provide the variances of ARMA(0; 0), ARMA(1; 0), ARMA(2; 0), and ARMA(1; 1), since these are the ones that are used in the simula tion. V ar(Pt) = 8>>>>>>>>< >>>>>>>>: 2 ARMA(0; 0) 2 1ô€€€ 21 ARMA(1; 0) 1ô€€€ 2 1+ 2 2 (1ô€€€ 2)2ô€€€ 21 ARMA(2; 0) 2(1+ 21 +2 1 1) 1ô€€€ 21 ARMA(1; 1) Note that, V art(Pt) and V ar(Pt) are di erent measures. V art(Pt) is a conditional variance of Pt where all the information until time t is known, while V ar(Pt) is the variance of Pt at time 0. V art(Pt) = 2; 8t 0 4 di erent ARMA process will be simulated; ARMA(0; 0), ARMA(1; 0), ARMA(2; 0), and ARMA(1; 1). All of these processes have the following mathematical representa tion. Pt = k + "t + 1Ptô€€€1 + 2Ptô€€€2 + 1"tô€€€1 34 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Each di erent set of parameters k; 1; 2; 1 and 2 variance of "t, will generate a di erent price process. Note that all moving average terms " are normally distributed with mean 0, and variance 2. Table 3.1: Coe cient sets of Pt = k + "t + 1Ptô€€€1 + 2Ptô€€€2 + 1"tô€€€1 with resulting V art(Pt), and V ar(Pt). Note that, all of them are stationary processes with p = 100. The rst row is the is the i.i.d. case where V art(Pt) = V ar(Pt) = 25. V art(Pt) of P1P10 are the same with the i.i.d. case. Tag k 1 2 1 V ar("t) V art(Pt) V ar(Pt) (Ptô€€€1; Ptô€€€2; "tô€€€1) 2 IID : ( ; ; ) 100 0 0 0 25.00 25.00 25.00 P1 : (+; ; ) 30 0.7 0 0 25.00 25.00 49.02 P2 : (ô€€€; ; ) 170 0.7 0 0 25.00 25.00 49.02 P3 : (+; ; +) 30 0.7 0 0.5 25.00 25.00 95.59 P4 : (ô€€€; ; +) 170 0.7 0 0.5 25.00 25.00 26.96 P5 : (+; ;ô€€€) 30 0.7 0 0.5 25.00 25.00 26.96 P6 : (ô€€€; ;ô€€€) 170 0.7 0 0.5 25.00 25.00 95.59 P7 : (+;+; ) 10 0.7 0.2 0 25.00 25.00 111.11 P8 : (ô€€€;+; ) 150 0.7 0.2 0 25.00 25.00 111.11 P9 : (+;ô€€€; ) 50 0.7 0.2 0 25.00 25.00 39.47 P10 : (ô€€€;+; ) 190 0.7 0.2 0 25.00 25.00 39.47 The simulation model generates 11 di erent price process for each iteration. The coe cients of each price process are chosen arbitrarily yet they are adjusted to cover a large set of possible price scenarios, while having comparable statistical proper ties. All of these are stationary processes with mean p = 100. The rst process is ARMA(0,0), with mean 100 and variance 25, i.e. prices are identically and indepen dently distributed. Note that variance and conditional variance are equal for the i.d.d case. The next 10 processes are di erent variations of ARMA(1; 0), ARMA(2; 0), and ARMA(1; 1) which cover all positive and negative parameter combinations, and Chapter 3: Singleperiod Procurement Policy via DataDriven LP 35 the parameters are adjusted to make the conditional variance of the process equals to 25. However their variances do not equal 25. All the simulated processes, their respective parameter, and resulting variance and conditional variance values are listed in Table 3.1. Within the same iteration, all the processes are generated by using the same random seed, therefore the same random variables. A 100period sample path of i.i.d. price process is shown in Figure 3.2. The sample paths of other 10 price processes is shown in Figure 3.3 (blue or light processes). Note that all the di erent price processes are generated via the same random seed (including Figure 3.2). Figure 3.3 is provided to depict the behavior of di erent ARMA con gurations. The graphs on the left consist of the processes with positive 1, while the price processes shown in the right graphs have a negative 1 coe cient which increases the spikiness of the process. We use the term "spikiness" to assess the magnitude of the oscillation around their mean. In addition, in order to emphasize the e ect of the variance on the shape of process for di erent price models, Figure 3.3 provides reference price processes (red or dark) having variance of 25. Note that the price processes, P1 to P10 (blue or light) have a conditional variance of 25, however their variances di er. Figure 3.2: A 100period sample path of normally distributed (mean: 100, variance: 25) i.i.d. price (case 1). x axis is the price and y axis is the periods. 36 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Figure 3.3: 100period sample paths of prices processes case P1 to case 10 (upper left is case P1, bottom right corner is case P10). x axis is the price and y axis is the periods. 3.4.2 Demand Settings The simulation model generates di erent demand streams in order to test a wide set of scenarios with di erent correlations between the price and the demand. An additive model is used to generate demand streams correlated with the price process. The mathematical formulation of the additive model is as follows, Dt = a ô€€€ bPt + t Note that Dt is the amount of demand occurred in period t, 8t 0 where Pt is the spot price, a, and b are constant, and t is i.i.d. random variable with Normal distribution, with mean 0, and and standard deviation . The values of b, and determine the correlation between the price and demand in a given period. Similar to the selection of parameters of price process, di erent parameters are selected to test a wide range of scenarios for demand. 5 di erent demand models are generated which are: independent from price, positively or negatively correlated Chapter 3: Singleperiod Procurement Policy via DataDriven LP 37 (correlation coe cient is either 0.7 or 0.7, respectively), and weakly positively or neg atively correlated (correlation coe cient is either 0.3 or 0.3, respectively). To make comparison between scenarios possible, parameters selected to satisfy the following conditions; the expected pro t is equal to D = 1000, and V art(Dt) = 1002. All the respective parameters and their resulting variance and can be found in Table 3.2. Table 3.2: Coe cient sets of Dt = a ô€€€ bPt + t with resulting V art(Dt) and Corrt(Dt; Pt). Note that, there are 5 di erent demand scenario and all have the same expected value which is d = 1000. Tag a b V ar( t) V art(Dt) Corrt(Dt; Pt) 2 = t 2 [2; 11] t 2 [2; 11] iid 1000 0 10000 1002 0 l+ 400 6 9100 1002 0.3 lô€€€ 1600 6 9100 1002 0.3 h+ 400 14 5100 1002 0.7 hô€€€ 2400 14 5100 1002 0.7 The mathematical relations between variance, correlation, conditional variance, conditional correlation, and parameters are provided in below formulations. V ar(Dt) = V ar(a ô€€€ bPt + t) = V ar(a) + V ar(bPt) + V ar( t) = b2V ar(Pt) + 2 V art(Dt) = b2V art(Pt) + 2 38 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Corr(Dt; Pt) = Cov(Dt; Pt) p V ar(Dt)V ar(Pt) = Cov(a ô€€€ bPt + t; Pt) p (b2V ar(Pt) + 2 )V ar(Pt) = Cov(a; Pt) ô€€€ bCov(Pt; Pt) + Cov( t; Pt) p (b2V ar(Pt)2 + 2 V ar(Pt) = ô€€€bV ar(Pt) p (b2V ar(Pt)2 + 2 V ar(Pt) Corrt(Dt; Pt) = ô€€€bV art(Pt) p (b2V art(Pt)2 + 2 V art(Pt) 3.4.3 Feature Set Settings The presence of exogenous variable (feature) might have an important impact on the decision criteria. In order to measure the e ect of a feature that is correlated to the demand (and/or price) stream, two di erent feature models are proposed. For each model, two correlation levels are tested (high/low). Scalar Feature Suppose that there is a feature that is correlated with the demand and/or the price. The feature is observed before the realization of demand. The rst model for the fea ture is a noise added over the demand. The correlation between feature and demand streams are controlled by the standard deviation of the noise. The mathematical formulation of the model is, f(1) t = Dt + wt where, wt is the random noise added to demand to adjust the rate of correlation. wt is normally distributed with mean 0 and variance 2w . Values of 2w selected to simu late high (0.9) and low (0.6) correlation values between f(1) t and Dt. Corresponding coe cients and their respective correlation values are listed in Table 3.3. The correlation values shown in Table 3.3 are computed via following expressions. Chapter 3: Singleperiod Procurement Policy via DataDriven LP 39 Table 3.3: Coe cient Set of f(1) t . Tag V ar(wt) Corrt(Dt; f(1) t ) 2w = t 2 [2; 11] high 2500 0.9 low 17500 0.6 Corr(Dt; f(1) t ) = V ar(Dt) p (V ar(Dt)2 + 2w V ar(Dt) Corrt(Dt; f(1) t ) = V art(Dt) p (V art(Dt)2 + 2w V art(Dt) Binary Feature Suppose that there is an exogenous variable (feature) which signals whether the de mand is going to be higher than its mean with a level of certainty, before the demand is observed. This feature can be modeled via the following mathematical expression, f(2) t = 8>< >: 1 Dt + wt > D 0 Dt + wt D where, wt is the random noise added to demand to adjust the level of accuracy of the indicator function. wt is normally distributed with mean 0 and variance 2w . 3.4.4 Parameters Array Selection The solution methodology requires the selection of the parameters array hi. The parameters array is important, because the accuracy of the model depends on this selection. According to the selection of hi the datadriven linear program nds 40 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Table 3.4: Coe cient Set of binary feature f(2) t . Since the explicit solution of PfDt > Djf(2) t = 1g does not exist, the corresponding probabilities are calculated via simulation. Tag V ar(wt) PfDt > Djf(2) t = 1g 2w = t 2 [2; 11] high 1000 0.9 low 10000 0.75 vector which optimizes the objective function of the problem. ~ x i = Xjhj j=1 jhij The simulation model solves datadriven linear programs for every di erent sce nario, with each of parameters array con gurations to test the performance of the respective con guration. All the parameters array con gurations are listen in Table 3.5. 3.4.5 Run Con guration Parameters selected for simulation model are as follows; mean demand is 1000, stan dard deviation of demand is 100 (Note that standard deviation is measured with two di erent methods, one step ahead, i.e. standard deviation of next period when all the information is known until the current period, and the standard deviation of a period without any information). Price is stationary and the mean price is 100, and standard deviation of each price is 5 (two di erent standard deviation calculation applies for the price process, too). The underage penalty u = 40, and overage penalty o = 60. The procurement cost is constant for all periods, ci = 80, 8i > 0. Note on procurement cost, c, being a constant: The procurement cost is modeled as a constant and it is the same for all periods. Therefore it is independent from the spot market price. One might argue that the assumption on the procurement cost is misleading, and not relevant. Since the price Chapter 3: Singleperiod Procurement Policy via DataDriven LP 41 Table 3.5: Parameters array con guration # Ptô€€€1 Ptô€€€2 f(1) t f(2) t ht 1 0 0 0 0 [1] 2 0 0 1 0 [1,f(1) t ] 3 0 0 0 1 [1,f(2) t ] 4 0 0 1 1 [1,f(1) t ,f(2) t ] 5 1 0 0 0 [1,Ptô€€€1] 6 1 0 1 0 [1,Ptô€€€1,f(1) t ] 7 1 0 0 1 [1,Ptô€€€1,f(2) t ] 8 1 0 1 1 [1,Ptô€€€1,f(1) t ,f(2) t ] 9 1 1 0 0 [1,Ptô€€€1,Ptô€€€2] 10 1 1 1 0 [1,Ptô€€€1,Ptô€€€2,f(1) t ] 11 1 1 0 1 [1,Ptô€€€1,Ptô€€€2,f(2) t ] 12 1 1 1 1 [1,Ptô€€€1,Ptô€€€2,f(1) t ,f(2) t ] is modeled as an ARMA process, and the pro t function requires only the margin of the price and the procurement cost (P ô€€€ c) and the margin (P ô€€€ c) turns out to be another ARMA process. Therefore even if the procurement cost is modeled as a function of the previous price, or even if it has a noise added, i.e. ci = Piô€€€1 + , the margin (Pt ô€€€ ct) is going to be another ARMA process. Hence, a procurement cost modeled as an ARMA process can be modeled as a constant procurement cost and modi ed ARMA coe cients. Therefore the current simulation model is su cient to test the cases where the procurement costs depends on the previous periods, since it test a wide range of ARMA processes. 3.4.6 Benchmarks A theoretical benchmark can be found for no feature cases by Proposition 1. The simulation model uses ARMA price processes, and an additive demandprice model, 42 Chapter 3: Singleperiod Procurement Policy via DataDriven LP where all the error terms are normally distributed. Note that the price and demand models used in simulation are, Pt = k + "t + 1Ptô€€€1 + 2Ptô€€€2 + 1"tô€€€1 and Dt = a ô€€€ bPt + t Corollary 1. Theoretical benchmark of the simulation model, q , i.e. optimal order quantity of the single period problem where Pt is an ARMA process, Dt an additive pricedemand model and all the information until time t is known, can be computed by the following expression: q = 8>>>>>< >>>>>: 0 p ô€€€ ct ô€€€ u d + d ô€€€1 pô€€€ct+ u u+ o ô€€€ u < p ô€€€ ct < o +1 o p ô€€€ ct where Et[Pt] = p = k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 , and Et[Dt] = d = a ô€€€ b k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 and p V art(Dt) = d = p b2 2 + 2 Proof. The benchmark should be calculated using the same information which is available for the simulation. In other words, the theoretical optimal decision for time period t, should be calculated given all the information until time t is known. Since all the information until time t is known, values of Ptô€€€1, Ptô€€€2, and "tô€€€1 are already observed (all realized random variables are signed by a hat^). The uncertainty of Pt is caused only by "t (which has a 0 mean and standard deviation), and t (which has a 0 mean and standard deviation). Since both "t, and t are normally distributed variables, the pro t function can be rewritten using the information available. Pt Normal p = k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 ; Dt Normal d = a ô€€€ b k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 ; d = q b2 2 + 2 Chapter 3: Singleperiod Procurement Policy via DataDriven LP 43 Since Et[Pt] = p = k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 , and Dt is normal mean d = a ô€€€ b k + 1 ^ Ptô€€€1 + 2 ^ Ptô€€€2 + 1^"tô€€€1 and standard deviation d = p b2 2 + 2 , by using Proposition 1 the optimal order quantity can be calculated as, q = d + d ô€€€1 p ô€€€ ct + u u + o The above equation is valid only when ô€€€ u < pô€€€ct < o. Therefore the resulting optimal order quantity with respect to the di erent parameter values is, q = 8>>>>>< >>>>>: 0 p ô€€€ ct ô€€€ u d + d ô€€€1 pô€€€ct+ u u+ o ô€€€ u < p ô€€€ ct < o +1 o p ô€€€ ct 3.5 Simulation Results of Expected Pro t Maximization This section covers the analysis of datadriven linear program with expected pro t maximization objective. Before we begin the analysis of the results, we will de ne some terms which will be used through this section. "EPLP" stands for the datadriven linear program with expected pro t maximization which is proposed in Section 3.2.3. "Insample" refers any direct result of the linear program. For instance, expected pro t result of EPLP is called "insample" expected pro t. When we apply the policy generated by EPLP to another data set rather than the data used in the EPLP, resulting statistics are called as "outsample". "Theoretical" term is used to indicate the resulting statistics when the theoretical optimal policy is used. The aim of this simulation is to show the power of the datadriven LP formulation in generating optimal decisions to maximize outsample expected pro t, for all possible scenarios, i.e. for all price processes, for all pricedemand dependency, and for all feature availability cases. 44 Chapter 3: Singleperiod Procurement Policy via DataDriven LP We rst analyze the insample performance of the algorithm, then, before moving into the analysis of outsample performance which is more important, we provide an analysis for the theoretical results. Outsample performance is analyzed in two parts. We rst looked at the when the features are not available. The e ect of price process and demand model and the impact of parameters array selection is investigated. Then the e ect of the exogenous feature availability and the dispersion of the results are analyzed. The tables presented in this section are constructed to provide insights to the sim ulation results. More detailed simulation results are listed in Appendix A (expected pro ts) and Appendix B (dispersion of the outsample pro ts). 3.5.1 Insample Performance Insample performance of the datadriven LP formulation (EPLP): EPLP is able to maximize insample mean pro t for all scenarios. Insample performance of EPLP increases as the number of elements in the parameters array increases for all scenarios. The fact that the performance of insample results increases as the size of the parameter array increases is not surprising because a larger parameters array causes an increment in the dimension of the LP which enables to nd values improves the optimal policy. In other words, the feasible region of a datadriven LP with a given parameters array is always a subset of feasible region of a datadriven LP parameters array of which is a super set of the initial parameters array. Therefore, the improvement in the objective function is expected as the size of parameters array increases. However it may cause over tting, a poorer performance in the outsample results. The comparison of the outsample results are more meaningful to evaluate the performance of the solution method. These observations are consistent for all possible scenarios, i.e. di erent price processes, demand models and availability of features. As an example case, insample mean pro t values of a scenario are presented in Table A.1 (Appendix A). The table Chapter 3: Singleperiod Procurement Policy via DataDriven LP 45 shows the insample and outsample mean pro ts for all price processes when the demand is i.i.d. and no feature is available. Insample results may perform better than the theoretical benchmark which is not surprising since the LP uses the information of all periods in the computation, while the theoretical benchmark only uses the information of the previous periods. Note that in Table A.1, there is a di erence between insample and outsample results of theoretical benchmarks. This di erence is not expected and it is caused by the variance of the simulation results. Number of iterations are increased, we expect that both values converge to one another. However this variance does not cause a problem for measuring the outcome of EPLP since, insample and outsample values should be compared with their respective benchmarks. Although insample results are valuable to depict the capability of EPLP, the true indicator of the performance is the outsample results. Before the analysis of the outsample performance of the datadriven LP for no feature case, results of the theoretical benchmark should be investigated. 3.5.2 Analysis of Theoretical Expected Pro t Our ndings on the theoretical expected pro t are as follows, For all price processes, as the correlation level of price and demand increases, the theoretical expected pro t increases. (As the correlation level of price and demand decreases, the theoretical expected pro t decreases.) The e ect of correlation on the theoretical expected pro t increases with respect to the variance of the price process. The variance of the theoretical expected pro t increases as the correlation increases (both positive and negative correlation increases the variance of the results.), as variance of the price process increases. The variance of the theoretical expected pro t decreases as the spikiness of the price process increases. (Smoother price processes result bigger variances on their theoretical expected pro ts with respect to the spikier processes with the same 46 Chapter 3: Singleperiod Procurement Policy via DataDriven LP variance.) Table 3.6: Expected Value of the theoretical benchmark. (1500015500: Very Low, 1550016000: Low, 1600016500: Moderate, 1650017000: High, 17000: Very High) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IIDP4P5 Moderate Moderate Moderate Moderate Moderate Low P9P10 Low Moderate Moderate Moderate Moderate Moderate P1P2 Low Moderate Moderate Moderate High High P3P6 Very Low Low Moderate High Very High Very High P7P8 Very Low Moderate Moderate High Very High Table 3.6 shows the e ect of variance of the price process and the correlation between price and demand. The variance of the theoretical results does not only depend on the variance of the price and the correlation level between the price and the demand, but also they depend on the spikiness of the price process (Table 3.7). The sign of 1 which is the coe cient of Ptô€€€1 of the ARMA process determines the spikiness of the process; therefore, the variance of the theoretical results depends heavily on the sign of the parameter 1. Negative and zero 1 cases result small variances for demand models whereas positive 1 cases, the variance of the theoretical outcome increases as the correlation level, and the variance of the price process. 3.5.3 Outsample Performance for No Feature Cases The true performance of EPLP can only be understood by the analysis of the out sample results. The analysis of the outsample results for the cases where the features are not available is straightforward, since we have theoretical benchmarks for these cases. The outsample results are compared with the respective theoretical results. The simulation results show that, Chapter 3: Singleperiod Procurement Policy via DataDriven LP 47 Table 3.7: Variance of the theoretical benchmark. (0500: Very Low, 5001000: Low, 10001500: Moderate, 15002000: High, 2500: Very High) Correlation of Price and Demand 1 Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+)  Very Low P5 Very Low Very Low Very Low Very Low Very Low  Low P9 Very Low Very Low Very Low Very Low Very Low  Moderate P1 Very Low Very Low Very Low Very Low Very Low  High P3 Very Low Very Low Very Low Very Low Very Low  Very High P7 Very Low Very Low Very Low Very Low Very Low 0 Very Low IID Very Low Very Low Very Low Very Low Very Low + Very Low P4 Very Low Very Low Very Low Low Low + Low P10 Very Low Very Low Low Low Low + Moderate P2 Low Low Low Low Moderate + High P6 Low Moderate Moderate Moderate High + Very High P8 High Very High Very High Very High Very High EPLP is able to nd a procurement rule which yields an expected pro t which is as good as the theoretical optimal policy for all no feature cases. The simulation results show that the performance of the datadriven LP depends on the correlation of demand and price. As the correlation between demand and price decreases (positively or negatively) the performance of the solution methodology increases. (Table 3.8) The performance of the datadriven LP is a ected by the number of parameters exist in the price process. For simpler price processes the solution method performs better than for more complex price processes.(Table 3.8) The simulation results of outsample mean pro t show that even the scenario with the worst expected pro t is as good as the theoretical upper bound, the data driven LP is only ô€€€0:44% o the theoretical result, whereas the scenario with the 48 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Table 3.8: E ect of the price process and the demand model on the performance of EPLP with respect to the theoretical benchmark. (Percentage deviation from the theoretical benchmark, a more detailed table can be found in Appendix A A.3) Correlation of Price and Demand # of Parameters Corresponding Very Low Negative Independent Positive Very High of Price Process Price Process (h) (l) (i.i.d.) (l+) (h+) 0 IID 0.06 0.04 0.04 0.05 0.06 1 P1P2 0.08  0.09 0.07  0.09 0.08  0.09 0.09 0.10  0.12 2 P3...P10 0.13  0.32 0.07  0.13 0.06  0.13 0.14  0.22 0.15  0.44 best performance is as good as ô€€€0:04% for all price process  demand model pairs. (See Appandix A Table A.1 and, Table A.2 for resulting outsample mean pro ts, and see Table A.3 for the percentage deviation of the outsample mean pro ts to the theoretical benchmark) Despite the performance of the EPLP depends on the correlation level between the price and the demand, interestingly, it does not directly depend on neither the variance of the price process, nor the spikiness of but it depends on the number of parameters exist in the price process. For simpler price processes, i.e. i.i.d. or ARMA(1,0), the solution method performs better than more complex price processes such as ARMA(1,1) or ARMA(2,0). Nevertheless, the di erence in terms of perfor mance negligible. (Table 3.8) The E ect of the Parameters Array Selection: Selection of the parameters array plays an important role on the performance of the datadriven approach. Note that all insample and outsample performance statistics presented in the previous sections are the results of the best performing parameters array selection. Our aim is to investigate the best parameters array selection for di erent price processes and demand models. Without the presence of the features, the parameters array is constructed by using only the previous price information. We have tested Chapter 3: Singleperiod Procurement Policy via DataDriven LP 49 three di erent parameters array con gurations, h1 = [1], h2 = [1; Ptô€€€1], and h3 = [1; Ptô€€€1; Ptô€€€2]. Simulation results show that the selection of the best performed parameters array depends on the following conditions: The performance of the parameters array depends on the structure of the underlying ARMA process of the price most. Parameters array should include the variables of the ARMA process, i.e. h1 = [1] is the best option for i.i.d. price (ARMA(0,0)), h2 = [1; Ptô€€€1] is the best option for P1 and P2 which are ARMA(1,0). In case of more complex ARMA processes (ARMA(1,1) and ARMA(2,0)) both variance of the price process, and the correlation level between the price and the demand a ect the best performing parameters array selection, and h1 and h2 might perform better than h3 = [1; Ptô€€€1; Ptô€€€2] which we would expect that it would be the best option according to the rst observation. However always performs almost as good as the best performing parameters array selection. Therefore the rst observa tion still holds. Spikiness of the price process does not a ect the performance of the parameters array selection, if the variances of the processes are the same. Note that EPLP with the parameters array h1 = [1] is the same with Sample Average Approximation (SAA) method. The results of Appendix A Table A.2 shows that SAA is not able adapt pricedemand correlation especially with processes with bigger variance. It lacks responding to di erent price levels, since it does not possess the price information of the previous periods. Nevertheless, if the price is i.i.d., then since the previous realization of the price does not a ect the future, then the information of the previous price does not contribute to the solution, and in that case SAA results are immune to the pricedemand correlation. Therefore, for i.i.d. price processes, it is preferable to use SAA (or datadriven LP formulation with parameters array [1]) for all correlation levels of the price and the demand. The SAA case (h1) yields higher pro ts if price process is i.i.d., but for the rest of the price processes, other two parameters array con gurations perform better. 50 Chapter 3: Singleperiod Procurement Policy via DataDriven LP Table 3.9: Percentage di erence of outsample mean pro t and theoretical benchmark when parameters array is h1 = [1] (SAA). (00.10: Very Good, 0.100.25: Good, 0.25 1.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID Very Good Very Good Very Good Very Good Very Good Very Low P4P5 Moderate Very Good Very Good Good Moderate Low P9P10 Bad Good Good Bad Bad Moderate P1P2 Bad Moderate Good Bad Very Bad High P3P6 Very Bad Moderate Moderate Very Bad Extremely Bad Very High P7P8 Very Bad Bad Moderate Very Bad Extremely Bad Table 3.10: Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h2 = [1; Ptô€€€1]. (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID Very Good Very Good Very Good Very Good Good Very Low P4P5 Good Very Good Very Good Good Moderate Low P9P10 Good Very Good Very Good Good Moderate Moderate P1P2 Very Good Very Good Very Good Good Good High P3P6 Moderate Good Good Moderate Bad Very High P7P8 Moderate Very Good Very Good Good Moderate Simulations results show that the parameters array should be constructed to provide information to represent underlying ARMA process. Although, the variance of the price process and the correlation of the demand and the price a ect the parameters Chapter 3: Singleperiod Procurement Policy via DataDriven LP 51 Table 3.11: Percentage di erence of outsample mean pro t and theoretical bench mark when parameters array is h3 = [1; Ptô€€€1; Ptô€€€2]. (00.10: Very Good, 0.100.25: Good, 0.251.00: Moderate, 1.005.00: Bad, 5.0010.00: Very Bad, 10.00: Extremely Bad) (See Appendix A A.3 for the values) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID Good Good Good Good Good Very Low P4P5 Good Good Good Good Good Low P9P10 Good Good Good Good Good Moderate P1P2 Good Good Good Good Good High P3P6 Moderate Good Good Good Moderate Very High P7P8 Good Good Good Good Good Table 3.12: Best Performing parameters arrays for di erent price processes and dif ferent demand models (1: h1 = [1], 2: h2 = [1; Ptô€€€1], 3: h3 = [1; Ptô€€€1; Ptô€€€2]) Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID 1 1 1 1 1 Very Low P4P5 3 1 1 2 3 Low P9P10 3 2 2 3 3 Moderate P1P2 2 2 2 2 2 High P3P6 3 3 2 3 3 Very High P7P8 3 2 2 3 3 array performance especially for complex price processes, for complex price processes, it is useful to construct larger parameters arrays. 52 Chapter 3: Singleperiod Procurement Policy via DataDriven LP 3.5.4 Outsample Performance when the Features are Available In this section, the e ect of features (exogenous variables) on the outsample perfor mance of the EPLP is analyzed. First of all, it is important to remind that a theoretical closed form solution of the problem does not exist when the features are available. Therefore, it is not possible to calculate the deviation of the EPLP from the optimal value directly, and only the relative performance of the method can be measured, i.e. comparison of the out sample mean pro ts of the theoretical benchmark of the featureless case and results the EPLP. Although this comparison does not prove the optimality of the method, it reveals the ability of EPLP to capture and exploit the extra information provided by the features on the demand and/or the price. The simulation results show that The decision maker would better o if s/he uses the EPLP with features rather than using theoretical optimal values which does not use the feature information, for all pricedemand scenarios and all parameters array con gurations. As the information provided by the feature become more accurate, i.e. the correlation between the demand and feature increases, the gain increases with respect to the theoretical benchmark of no feature case. This condition holds for all price processes and all demand models. (Table 3.13) Although both scalar and binary features yield greater pro ts than the the oretical results, scalar features performs better than binary feature cases. (Table 3.13) Presence of multiple features increases the gain acquired. (Table 3.13) The e ects of variance of the price process and the correlation level between price and demand on the performance of EPLP are consistent with no feature cases. Table 3.13 presents the percentage gains acquired when EPLP is preferred instead of the theoretical benchmark of no feature case. It lists the minimum and the max imum gains acquired among all scenarios. Therefore, we can conclude that having extra information improves the performance of the solution method regardless of the Chapter 3: Singleperiod Procurement Policy via DataDriven LP 53 Table 3.13: Minimum and maximum percentage gain acquired in outsample mean pro t with respect to the theoretical benchmark of no feature cases, for di erent feature availability cases. (f(1): Scalar Feature, f(2): Binary Feature ) Binary Feature Scalar Feature No Low High No (0.44)  (0.04) 2.69  4.82 4.77  9.72 Low 3.94  5.59 5.65  8.21 6.94  11.43 High 11.49  14.96 11.90  15.44 12.44  16.26 scenario, and even when the amount of information provided by the features is small, EPLP still performs better than the theoretical benchmark of the featureless case in terms of the outsample mean pro t. More detailed tables presenting the outsample mean pro ts for all scenarios and feature availability cases can be found in Appendix A. Table A.4 and Table A.5 presents the outsample mean pro ts of EPLP with scalar feature cases, and Table A.6 and Table A.7 presents the outsample mean pro ts of EPLP with binary feature cases. Simulation results of multiple feature cases can be found in Appendix A Tables A.8, A.9, A.10, and A.11. The simulation results coincide with the ndings of no feature cases in terms of the e ect of variance of the price process, the correlation level between price and demand on the outsample mean pro t, and the e ect of parameters array selection. For instance, when the prices are i.i.d. the presence of previous prices does not improve the performance. However, for price processes which evolves conditionally on the previous realizations, the parameters array with the price information (h2, h3) yields better outcomes. Furthermore, the gain acquired by selection of the parameters array with price information accumulates as the variance of the price process and as the price and demand become more correlated. Nevertheless, this gain is proportionally smaller than the no feature case. This is reasonable since the feature already induced the model to result a better solution, and a smaller room for improvement is left with 54 Chapter 3: Singleperiod Procurement Policy via DataDriven LP respect to the no feature case. In conclusion, having a feature which is correlated with the demand improves the performance of the datadriven LP approach and a proper price information should be included to parameters array to yield a better mean pro t. 3.5.5 Dispersion of the Simulation Results Although the analysis on sample means of the simulation results provides insights on the datadriven LP, the dispersion of the results should be investigated in order to ensure the validity of the strategy. An outsample test with a smaller variance is more preferable, because smaller variance indicates that solution methodology is capable of generating outcomes near the outsample mean. However, being able to assess the magnitude of a statistical property requires a reference point. In this case, a reference statistic is required to measure the dispersion generated by datadriven LP. Simulation results of a theoretical benchmark can be used as a reference to as sess the performance of the proposed solution methodology. Table 3.14, representing coe cient of variation of simulation results of theoretical benchmark, provides these reference points for each scenario (pricedemand pair) to assess the performance of datadriven LP. The table presents the coe cient of variations of the sample mean pro t within an iteration accumulated when the theoretical optimal procurement strategy is used. In other words, for no feature cases, the variation of the datadriven LP results can only be compared with these theoretical values. Table 3.14 shows the outsample coe cient of variations among separate out sample simulation iterations, for each scenario (PriceDemand pair). Note that coef cient of variation is CV = which scales the standard deviation of the collection with its mean to measure the dispersion, and enables to compare the dispersion of di erent data sets with di erent mean values. The coe cient of variation values pre sented in Table 3.14 show that they vary among di erent scenarios. While its value is around 0.02 to 0.05 for most of the scenarios (8 out of 11 scenarios), the value can be as high as 0.26 (P7h+ pair). This dispersion prevents direct comparison of the Chapter 3: Singleperiod Procurement Policy via DataDriven LP 55 Table 3.14: Coe cient of Variation (CV = ) of outsample theoretical mean pro ts for all pricedemand scenarios Demand IID l+ lô€€€ h+ hô€€€ IID 0.03 0.03 0.03 0.03 0.02 P1 0.08 0.08 0.07 0.09 0.06 P2 0.02 0.02 0.02 0.02 0.02 P3 0.11 0.12 0.10 0.13 0.09 P4 0.03 0.03 0.02 0.03 0.02 P5 0.04 0.04 0.04 0.05 0.03 P6 0.02 0.02 0.02 0.02 0.02 P7 0.22 0.23 0.20 0.26 0.17 P8 0.02 0.03 0.02 0.04 0.04 P9 0.05 0.05 0.04 0.06 0.04 P10 0.02 0.02 0.02 0.02 0.02 outsample variances of the solution methodology. Therefore, we measure the dispersion of the EPLP by investigating the statistical properties of the di erence between results of theoretical optimal strategy and the solution approach for the same realizations of the random environment. For instance, for a given scenario, and a given realization of demandprice pair, theoretical optimal strategy and a EPLP is used concurrently to compute outsample mean pro t. Dif ference between the resulting outsample mean pro ts is collected for all outsample realizations. Analysis of the statistical properties of these di erences reveal the true dispersion of the solution strategy which is mostly puri ed from the volatility already existing in theoretical results. Table 3.15 shows the percentage of the mean values of the di erence between outsample results of theoretical benchmark and EPLP in each simulation run to the theoretical benchmark for all scenarios when no features available. Table 3.16 56 Chapter 3: Singleperiod Procurement Policy via DataDriven LP shows the percentages of the standard deviations. The simulation results on the ta bles show that the solution methodology is successfully able to imitate the behavior of the theoretical benchmark. None of the results con icts this claim. First of all, the distribution of the di erences between theoretical and datadriven LP are no tably small when they are scaled with the mean of the theoretical benchmark (the percentage values). The mean of the di erences between the datadriven LP and the theoretical benchmark are very small with respect to the mean of the benchmark. The scenario with the worst performance, performed only 0:42% less than the theoreti cal benchmark for correct parameters array selection. Not only the mean di erence but also the standard deviation is very small with respect to the benchmark mean value. The deviation of result generated by the datadriven LP is as small as 0:42% of the theoretical benchmark mean for the worst performing scenario. More detailed statistics can be found in Appendix B Tables B.1, B.2, B.3, B.4, and B.5. Among all scenarios, the worst performing one realized within a range of ô€€€3:99%, +0:98% of the theoretical benchmark mean. Therefore, we can conclude the following, Since the dispersion of the simulation results are very small with respect to the mean values of the theoretical benchmark, the analysis performed using the out sample mean pro ts are accurate. Although the performance of EPLP is satisfactory for all scenarios, the variance of the price process and the correlation level between the price and the demand, still a ects the performance of EPLP. The correlation level decreases the performance of the solution methodology for both positive and negative cases. Furthermore, the e ect of the price variance can be observed in Table 3.15, and Table 3.16. Dispersion of datadriven LP is investigated not only for nofeature cases, but also for the cases when the features are available. They show the dispersion on the results of datadriven LP when the features are available. Since there are so many scenarios and parameters array con gurations, only three scenarios are selected to be able to represent the characteristics of a wide range of possible scenarios (among 55 possible scenarios), and result of the rest can be found in Appendix Table B.6, Table B.7, and Chapter 3: Singleperiod Procurement Policy via DataDriven LP 57 Table 3.15: The percentage of the mean values of the di erence between outsample results of theoretical benchmark and EPLP in each simulation run to the theoretical benchmark for all scenarios when no features available. Correlation of Price and Demand Variance Corresponding Very Low Negative Independent Positive Very High of Price Price Process (h) (l) (i.i.d.) (l+) (h+) Very Low IID 0.01 0.00 0.00 0.01 0.02 Very Low P4P5 0.04  0.07 0.01  0.01 0.00  0.00 0.00  0.00 0.09  0.11 Low P9P10 0.09  0.07 0.02  0.00 0.00  0.01 0.05  0.05 0.08  0.09 Moderate P1P2 0.08  0.06 0.02  0.01 0.01  0.01 0.06  0.06 0.08  0.08 High P3 
Format  
Material type  Text / Thesis 
Rating 



A 

B 

H 

J 

K 

S 

U 

V 

Ä 


