American Institute of Mathematical Sciences

Advanced
  • Previous Article
    A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update
  • JIMO Home
  • This Issue
  • Next Article
    Parametric solutions to the regulator-conjugate matrix equations
April  2017, 13(2): 633-647. doi: 10.3934/jimo.2016037

Distribution-free solutions to the extended multi-period newsboy problem

Yong Zhang 1, , Xingyu Yang 1,, and  Baixun Li 2,

1. 

School of Management, Guangdong University of Technology, Guangzhou 510520, China
2. 

School of Business Administration, Guangdong University of Finance & Economics, Guangzhou 510320, China

* Corresponding author: Xingyu Yang

Received  March 2015 Revised  December 2015 Published  May 2016

This paper concerns the distribution-free, multi-period newsboy problem in which the newsboy has to decide the order quantity of the newspaper in the subsequent period without knowing the distribution of the demand. The Weak Aggregating Algorithm (WAA) developed in learning and prediction with expert advices makes decision only based on historical information and provides theoretical guarantee for the decision-making method. Based on the advantage of WAA and stationary expert advices, this paper continues providing distribution-free methods for the extended multi-period newsboy problems in which the shortage cost and the integral order quantities are considered. In particular, we provide an alternative proof for the theoretical result which guarantees the cumulative gain our proposed method achieves is as large as that of the best stationary expert advice. Numerical examples are provided to illustrate the effectiveness of our proposed methods.

Keywords: Multi-period newsboy problem, shortage cost, integral order quantity, distribution-free solution, weak aggregating algorithm.
Mathematics Subject Classification: Primary: 90B05, 68W27; Secondary: 68W40.
Citation: Yong Zhang, Xingyu Yang, Baixun Li. Distribution-free solutions to the extended multi-period newsboy problem. Journal of Industrial & Management Optimization, 2017, 13 (2) : 633-647. doi: 10.3934/jimo.2016037
References:
[1]

S. Al-Binali, A risk-reward framework for the competitive analysis of financial games, Algorithmica, 25 (1999), 99-115.  doi: 10.1007/PL00009285.  Google Scholar

[2]

H. K. Alfares and H. H. Elmorra, The distribution-free newsboy problem: extension to the shortage penalty case, International Journal of Production Economics, 93-94 (2005), 465-477.  doi: 10.1016/j.ijpe.2004.06.043.  Google Scholar

[3]

O. Besbes and A. Muharremoglu, On implications of demand censoring in the newsvendor problem, Management Science, 59 (2013), 1407-1424.   Google Scholar

[4]

A. Burnetas and C. Smith, Adaptive ordering and pricing for perishable products, Operations Research, 48 (2000), 436-443.  doi: 10.1287/opre.48.3.436.12437.  Google Scholar

[5]

N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games, Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511546921.  Google Scholar

[6]

L. L. Ding, X. M. Liu and Y. F. Xu, Competitive risk management for online Bahncard problem, Journal of Industrial and Management Optimization, 6 (2010), 1-14.  doi: 10.3934/jimo.2010.6.1.  Google Scholar

[7]

G. Gallego and I. Moon, The distribution free newsboy problem: review and extensions, Journal of the Operational Research Society, 44 (1993), 825-834.  doi: 10.2307/2583894.  Google Scholar

[8]

W. T. Huh, R. Levi, P. Rusmevichientong and J. B. Orlin, Adaptive data-driven inventory control with censored demand based on Kaplan-Meier estimator, Operations Research, 59 (2011), 929-941.  doi: 10.1287/opre.1100.0906.  Google Scholar

[9]

W. T. Huh and P. Rusmevichientong, A non-parametric asymptotic analysis of inventory planning with censored demand, Mathematics of Operations Research, 34 (2009), 103-123.  doi: 10.1287/moor.1080.0355.  Google Scholar

[10]

Y. Kalnishkan and M. V. Vyugin, The weak aggregating algorithm and weak mixability, Journal of Computer and System Sciences, 74 (2008), 1228-1244.  doi: 10.1016/j.jcss.2007.08.003.  Google Scholar

[11]

M. Keisuke, The multi-period newsboy problem, European Journal of Operational Research, 171 (2006), 170-188.  doi: 10.1016/j.ejor.2004.08.030.  Google Scholar

[12]

S. Kunnumkal and H. Topaloglu, Using stochastic approximation methods to compute optimal base-stock levels in inventory inventory control problems, Operations Research, 56 (2008), 646-664.  doi: 10.1287/opre.1070.0477.  Google Scholar

[13]

S. Kunnumkal and H. Topaloglu, A stochastic approximation method for the single-leg revenue management problem with discrete demand distributions, Mathematical Methods of Operations Research, 70 (2009), 477-504.  doi: 10.1007/s00186-008-0278-x.  Google Scholar

[14]

T. Levina, Y. Levin, J. McGill, M. Nediak and V. Vovk, Weak aggregating algorithm for the distribution-free perishable inventory problem, Operations Research Letters, 38 (2010), 516-521.  doi: 10.1016/j.orl.2010.09.006.  Google Scholar

[15]

X. Lu, J. Song and K. Zhu, Analysis of perishable-inventory systems with censored demand data, Operations Research, 56 (2008), 1034-1038.  doi: 10.1287/opre.1080.0553.  Google Scholar

[16]

I. Moon and S. Choi, Distribution free newsboy problem with balking, Journal of the Operational Research Society, 46 (1995), 537-542.   Google Scholar

[17]

I. Moon and S. Choi, Distribution free procedures for make-to-order (MTO), make-in-advance (MIA), and composite policies, International Journal of Production Economics, 48 (1997), 21-28.  doi: 10.1016/S0925-5273(96)00026-6.  Google Scholar

[18]

I. Moon and E. A. Silver, The multi-item newsvendor problem with a budget constraint and fixed ordering costs, Journal of the Operational Research Society, 51 (2000), 602-608.   Google Scholar

[19]

G. R. Murray and E. A. Silver, A Bayesian analysis of the style goods inventory problem, Management Science, 12 (1996), 785-797.  doi: 10.1287/mnsc.12.11.785.  Google Scholar

[20]

H. Scarf, A min-max solution of an inventory problem, in: K. Arrow, S. Karlin, H. Scarf (Eds.), Studies in The Mathematical Theory of Inventory and Production, Stanford University Press, California, (1958), 201–209. Google Scholar

[21]

H. Scarf, Bayes solution of the statistical inventory problem, Annals of Mathematical Statistics, 30 (1959), 490-508.  doi: 10.1214/aoms/1177706264.  Google Scholar

[22]

G. L. Vairaktarakis, Robust multi-item newsboy models with abudget constraint, International Journal of Production Economics, 66 (2000), 213-226.   Google Scholar

[23]

Y. Zhang, V. Vovk and W. G Zhang, Probability-free solutions to the non-stationary newsvendor problem, Annals of Operation Research, 223 (2014), 433-449.  doi: 10.1007/s10479-014-1620-8.  Google Scholar

show all references

References:
[1]

S. Al-Binali, A risk-reward framework for the competitive analysis of financial games, Algorithmica, 25 (1999), 99-115.  doi: 10.1007/PL00009285.  Google Scholar

[2]

H. K. Alfares and H. H. Elmorra, The distribution-free newsboy problem: extension to the shortage penalty case, International Journal of Production Economics, 93-94 (2005), 465-477.  doi: 10.1016/j.ijpe.2004.06.043.  Google Scholar

[3]

O. Besbes and A. Muharremoglu, On implications of demand censoring in the newsvendor problem, Management Science, 59 (2013), 1407-1424.   Google Scholar

[4]

A. Burnetas and C. Smith, Adaptive ordering and pricing for perishable products, Operations Research, 48 (2000), 436-443.  doi: 10.1287/opre.48.3.436.12437.  Google Scholar

[5]

N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games, Cambridge University Press, Cambridge, 2006. doi: 10.1017/CBO9780511546921.  Google Scholar

[6]

L. L. Ding, X. M. Liu and Y. F. Xu, Competitive risk management for online Bahncard problem, Journal of Industrial and Management Optimization, 6 (2010), 1-14.  doi: 10.3934/jimo.2010.6.1.  Google Scholar

[7]

G. Gallego and I. Moon, The distribution free newsboy problem: review and extensions, Journal of the Operational Research Society, 44 (1993), 825-834.  doi: 10.2307/2583894.  Google Scholar

[8]

W. T. Huh, R. Levi, P. Rusmevichientong and J. B. Orlin, Adaptive data-driven inventory control with censored demand based on Kaplan-Meier estimator, Operations Research, 59 (2011), 929-941.  doi: 10.1287/opre.1100.0906.  Google Scholar

[9]

W. T. Huh and P. Rusmevichientong, A non-parametric asymptotic analysis of inventory planning with censored demand, Mathematics of Operations Research, 34 (2009), 103-123.  doi: 10.1287/moor.1080.0355.  Google Scholar

[10]

Y. Kalnishkan and M. V. Vyugin, The weak aggregating algorithm and weak mixability, Journal of Computer and System Sciences, 74 (2008), 1228-1244.  doi: 10.1016/j.jcss.2007.08.003.  Google Scholar

[11]

M. Keisuke, The multi-period newsboy problem, European Journal of Operational Research, 171 (2006), 170-188.  doi: 10.1016/j.ejor.2004.08.030.  Google Scholar

[12]

S. Kunnumkal and H. Topaloglu, Using stochastic approximation methods to compute optimal base-stock levels in inventory inventory control problems, Operations Research, 56 (2008), 646-664.  doi: 10.1287/opre.1070.0477.  Google Scholar

[13]

S. Kunnumkal and H. Topaloglu, A stochastic approximation method for the single-leg revenue management problem with discrete demand distributions, Mathematical Methods of Operations Research, 70 (2009), 477-504.  doi: 10.1007/s00186-008-0278-x.  Google Scholar

[14]

T. Levina, Y. Levin, J. McGill, M. Nediak and V. Vovk, Weak aggregating algorithm for the distribution-free perishable inventory problem, Operations Research Letters, 38 (2010), 516-521.  doi: 10.1016/j.orl.2010.09.006.  Google Scholar

[15]

X. Lu, J. Song and K. Zhu, Analysis of perishable-inventory systems with censored demand data, Operations Research, 56 (2008), 1034-1038.  doi: 10.1287/opre.1080.0553.  Google Scholar

[16]

I. Moon and S. Choi, Distribution free newsboy problem with balking, Journal of the Operational Research Society, 46 (1995), 537-542.   Google Scholar

[17]

I. Moon and S. Choi, Distribution free procedures for make-to-order (MTO), make-in-advance (MIA), and composite policies, International Journal of Production Economics, 48 (1997), 21-28.  doi: 10.1016/S0925-5273(96)00026-6.  Google Scholar

[18]

I. Moon and E. A. Silver, The multi-item newsvendor problem with a budget constraint and fixed ordering costs, Journal of the Operational Research Society, 51 (2000), 602-608.   Google Scholar

[19]

G. R. Murray and E. A. Silver, A Bayesian analysis of the style goods inventory problem, Management Science, 12 (1996), 785-797.  doi: 10.1287/mnsc.12.11.785.  Google Scholar

[20]

H. Scarf, A min-max solution of an inventory problem, in: K. Arrow, S. Karlin, H. Scarf (Eds.), Studies in The Mathematical Theory of Inventory and Production, Stanford University Press, California, (1958), 201–209. Google Scholar

[21]

H. Scarf, Bayes solution of the statistical inventory problem, Annals of Mathematical Statistics, 30 (1959), 490-508.  doi: 10.1214/aoms/1177706264.  Google Scholar

[22]

G. L. Vairaktarakis, Robust multi-item newsboy models with abudget constraint, International Journal of Production Economics, 66 (2000), 213-226.   Google Scholar

[23]

Y. Zhang, V. Vovk and W. G Zhang, Probability-free solutions to the non-stationary newsvendor problem, Annals of Operation Research, 223 (2014), 433-449.  doi: 10.1007/s10479-014-1620-8.  Google Scholar

Figure 1.  The gain function for Levina et al.'s multi-period newsboy problem with salvage. The slope of the graph is $p-c$ to the left of $y=d$ and $s-c$ to the right of $y=d$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Comparison of daily cumulative gain without shortage cost
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Comparison of daily cumulative gain with shortage cost
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Comparison between daily cumulative gain of DAS and ANS for trial 1
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Comparison between daily cumulative gain of DAS and ANS for trial 2
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Cumulative gains of DAS and experts without/with shortage cost
$N$ 100 200 300 400
DAS 3864/3721 6843/6211 9978/8928 12672/11339
$\theta=1$ 1520/-1966 3040/-3218 4560/-4568 6080/-5582
$\theta=2$ 2635/325 5093/1089 7678/1952 10187/3033
$\theta=3$ 3497/2223 6489/4375 9531/6507 12396/8700
$\theta=4$ 3955/3493 6923/6167 10068/9018 12733/11459
$\theta=5$ 3780/3780 6269/6269 8936/8936 10995/10995
Ratios 0.977/0.984 0.988/0.986 0.991/0.990 0.995/0.989
Table Options

Download as excel

$N$ 100 200 300 400
DAS 3864/3721 6843/6211 9978/8928 12672/11339
$\theta=1$ 1520/-1966 3040/-3218 4560/-4568 6080/-5582
$\theta=2$ 2635/325 5093/1089 7678/1952 10187/3033
$\theta=3$ 3497/2223 6489/4375 9531/6507 12396/8700
$\theta=4$ 3955/3493 6923/6167 10068/9018 12733/11459
$\theta=5$ 3780/3780 6269/6269 8936/8936 10995/10995
Ratios 0.977/0.984 0.988/0.986 0.991/0.990 0.995/0.989
Table 2.  AVEs and STDs of Ratios of cumulative gains of DAS and best expert without/with shortage cost
TN 10 20 30 40
AVE 0.9861/0.9917 0.9821/0.9904 0.9802/0.9905 0.9800/0.9910
STD 0.0152/0.0041 0.0135/0.0035 0.0147/0.0037 0.0148/0.0034
Table Options

Download as excel

TN 10 20 30 40
AVE 0.9861/0.9917 0.9821/0.9904 0.9802/0.9905 0.9800/0.9910
STD 0.0152/0.0041 0.0135/0.0035 0.0147/0.0037 0.0148/0.0034
Table 3.  Comparison between cumulative gains of DAS and ANS without shortage cost
trial 1 2 3 4 5 6 7 8 9 10
DAS 235 110 164 185 153 227 158 188 196 150
ANS 241 106 159 180 151 211 153 183 192 147
Table Options

Download as excel

trial 1 2 3 4 5 6 7 8 9 10
DAS 235 110 164 185 153 227 158 188 196 150
ANS 241 106 159 180 151 211 153 183 192 147
[1]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[2]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184
[3]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037
[4]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[5]

Jian Yang, Bendong Lou. Traveling wave solutions of competitive models with free boundaries. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 817-826. doi: 10.3934/dcdsb.2014.19.817
[6]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[7]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228
[8]

Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021017
[9]

Mingxin Wang, Qianying Zhang. Dynamics for the diffusive Leslie-Gower model with double free boundaries. Discrete & Continuous Dynamical Systems - A, 2018, 38 (5) : 2591-2607. doi: 10.3934/dcds.2018109
[10]

Yizhuo Wang, Shangjiang Guo. A SIS reaction-diffusion model with a free boundary condition and nonhomogeneous coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1627-1652. doi: 10.3934/dcdsb.2018223
[11]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067
[12]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[13]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597
[14]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[15]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[16]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[17]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137
[18]

Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021020
[19]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136
[20]

Zaihong Wang, Jin Li, Tiantian Ma. An erratum note on the paper: Positive periodic solution for Brillouin electron beam focusing system. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1995-1997. doi: 10.3934/dcdsb.2013.18.1995

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (81)
  • HTML views (411)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences