MINIMAL FORECASE HORIZONS THROUGH MONOTONICITY OF OPTIMAL SOLUTIONS ALFRED GARCIA Department of Industrial and Operations engineering University of Michigan, Ann Arbor, MI 48109, USA ROBERT L. SMITH Department of Industrial and Operations engineering University of Michigan, Ann Arbor, MI 48109, USA Technical Report 97-16 November 24, 1997

Minimal Forecast Horizons through Monotonicity of Optimal Solutions* Alfredo Garcia and Robert L. Smith Department of Industrial and Operations Engineering University of Michigan, Ann Arbor MI 48109 November 24, 1997 Abstract Monotonicity of optimal solutions to finite horizon dynamic optimization problems is used to prove the existence of a forecast horizon, i.e a long enough planning horizon that ensures that a first period optimal action for the infinite horizon and the finite horizon problem agree, regardless of problem parameter changes in the tail. The existence of extremal monotone optimal solutions, as in the context of production planning with convex costs, motivates a stopping rule to detect the minimal forecast horizon. 1 Introduction. Infinite Horizon planning models are motivated by the difficulty in establishing a rationale for can a priori fixed study horizon. If an arbitrarily chosen finite horizon is used, end of lhorizon effects can alter the validity of the model in question. Hence, it has been argued that tan infinite horizon is a better way to model instances in which, for dynamic optimization problems, the decision makers do not have a clear and prespecified ending date. Hlowever. the gains in modeling accuracy afforded by an infinite horizon model are severely copllronmised by the technical difficulties that render intractable the analysis. This is partic(llarlv troublesome in instances in which the parameters are not known precisely and are iLasslllned to possibly vary in time. In other words, the case with nonstationary parameters. This last consideration motivates the problem of finding a finite horizon such that the first optimal decision for such a horizon coincides with the infinite horizon counterpart. If sd(i ]a1 horizon exists (wlhich is called a solution horizon), it not only provides a rationale ito of(fer such a horizon as the decision makers planning horizon, but interestingly enough motin(l vai es a finite algorithm to solve an infinite problem via a rolling horizon procedure. Noetlhelel.ss. tile solution horizon concept is of little practical interest, for its computation mav p)otentiallv require an infinite forecast of data. Thus, the concept of a forecast horizon '*Ihi.s work \was supported in part by NSF grants DDM-9214894 and DMI-9713723. 1

(see for example, Bes and Sethi (1987) and Haurie and Sethi (1988)), that is, a long enough planning horizon that entails the insensitivity of first period optimal actions with respect to parameter changes in the tail, is very attractive to practitioners. In brief, in order to compute the first period optimal action, the planner need only forecast a finite amount of data, regardless of tail variations. In this paper we make use of monotonicity of optimal solutions to prove the existence of forecast horizons for a general class of dynamic optimization problems. Such monotonicity is a pervasive feature of many applications (see for example, Heyman and Sobel (1984)). We build on the work by Morton (1978) who exploited monotonicity in the context of the nonstationary periodic review inventory model with stationary linear costs to obtain upper and lower bounds for first period optimal decisions that are monotone in planning horizon. We extend Morton's work to cover any dynamic optimization problem with the property that optimal solutions that are monotone to parametrized variations in the state transition function exist. Such a property together with the principle of optimality allow to optimally embed the finite horizon problem in the infinite horizon setting as a parametric variation at the tail. In other words, finite horizon optimal solutions can be seen as infinite horizon optimal solutions to problem with a stationary trivial tail of parameters. This focus on early decision monotonicity has also been recently exploited by Smith and Zhang (1997) in the context of production planning with convex costs to develop a closed form formula for a forecast horizon under more restrictive monotonicity assumptions. We close our paper by presenting a stopping rule to yield optimal early production decisions for the infinite horizon production planning problem with convex costs that is guaranteed to detect the minimal forecast horizon. The existence of extremal monotone optimal solutions (see Topkis (1978)) is the key to this result. 2 Preliminaries. 2.1 Framework for parametric analysis of Dynamic Optimization Problems. As in Bes and Sethi(1991). we define a parametrized family of discrete time dynamic optiinization problems as follows: (Canonical Four-tuple (,4 S,. c(. ft)) At time period t E K, At C R+ is the compact set of all possible actions where / = {0 1,2,...} and R+ stands for the nonnegTative real line. St C R+ is the set of attainable states, and finally At(st) C At is the nonemptv closed subset of feasible actions given current state st. If an action a, E At(st) C At is taken given state st E St, a cost ct(st,at) E R+ is incurred and the next state to be attained is st+l = ft(st, at) where the state dynamics Ilapping ft: St x At - S,1+ and the cost function ct: St x At -* R+ are assumed (conItilnuouls. 2

* (Forecasts Ft) We denote by Ft, the set of all possible forecasts for time period t; that is for every element p e t, there exists a unique four-tuple of the form (At(-; p) C A (p) St,, ct(-,; p): St x At - R,t(,; p): St x At -+ St+l) associated with forecast p, where At(; p), St(p), ct(e,; p), ft(,; p) stand for time period t feasible action correspondence, set of attainable states, cost and transition functions, respectively'. * (Null Parameter 0)We convene to define the null parameter, 0 E Ft to which we associate for all t E KX the four-tuple: (At(.; ) = {O}, Stt(,;0) - 0, fot,; ) = 0) * We assume that each.t is a finite set endowed with a partial ordering " 't", according to which there is a "minimum" say P, and a "maximum" forecast Pt. * We denote by F(T) and F7, the set of T-horizon forecast and the set of infinite horizon forecasts, respectively, i.e: T-1 F(T) = I Ft F n= H t t=O t=o * (Forecast Metric Space (F, d))We endow each Ft with the discrete topology by means of the metric pt: T, x F {0, 1 } defined as follows, for Pt, Qt E t: 1 if pt = qt pt (pt.qt) = p 0 otherwise DB means of this metric. we define a metric d: xF yxT 1-, on T as follow, for P = (po, pi...,),q= (qo qi. -) E T: d(p.q) = E (p,qt) t=O We remark that this metric induces the product topology and that by Tychonoff's Theoremn the space (F. d) is compact. (liven forecast p E F, the T-long horizon optimization problem induced by it, for a rivenl initial state sois T- I min Z Ct(st.aip) t=O s.t St+l = ft(st.at;p) at e At(st; p) C t t 0, 1,2...,T - 1 ] Motie that the set of assumptions on the canonical four-tuple must hold for every indexed four-tuple. 3

Moreover, we shall denote by CT(p) and AT(p), the optimal value and optimal solution set for this problem when data follows forecast p for the first T- 1 periods. Similarly, the Infinite Horizon Problem according to forecast p E F is: T-1 min limsupT_. E ct(st, at;p) t=O s.t st+l = ft(st, at;p) at E At(st;p) C At t = 0, 1,2,... As above, we shall denote by C*(p) and A*(p), the optimal value and optimal solution set for the infinite horizon problem as prescribed by forecast p E F. 2.2 Standing Assumption. Throughout our analysis we will assume that the limit of a converging sequence of finite horizon optimal solutions is an optimal solution for the infinite horizon problem: Assumption 1 For every p E F and every indexed collection {aT}TErL such that aT E A*(p) for each T and lim aT = a we have a E A*(p). T —oo For a thorough study of sufficient conditions that imply Assumption 1, the reader is refered to Flam and Fougeres (1992) and Schochetman and Smith (1989) and (1992). 3 Examples. In, this section we give two classes of dynamic optimization problems that belong to the flillilv introduced in the previous section, with suggestions on how to apply the abstract l)ramnetric framework above presented. 3.1 Production Planning. i'lhe T-long horizon time varying production planning problem, with given initial inventory leve l o. is to find a production schedule that satisfies demand at minimum cost. T-1 min E at(Ct(xt) + hl(Il+l)) t=O s.t It+l = It + Xt - dt Aft > Xt > O, It > 0 xt. It integer t = 0,1,2,...,T- 1 lwhere x, is the production level at time period t, It is the inventory level at hand at htie start of time period t, Ct(xt) is the t-th-period production cost function and ht(It+l) is tI i islve torv holding cost, Ant is the maximal production capacity at time period t and (0(. 1) is tlhe discount factor. 4

Now let us assume that for any time period, demands can take integer values in the range d, d + 1,..., d} and that cost functions do not vary in time. As an illustration of parametric analysis, we can define our parameter set to be.t = {d,d + 1,...,d}. With this convention, an element p E F is simply an infinite sequence of demands which take values on the defined range. In this context, the null parameter can be interpreted as zero demand. Notice, without loss of optimality that for a T-planning horizon, one must end with zero inventory. If we append to the T-long production plan an infinite tail of zero production, this would be an optimal solution to the Infinite Horizon Production Planning Problem with demand (do, dl..., dT-l,, 0,...) 3.2 Optimal Exploitation of Renewable Natural Resources. We are given an initial stock so of a natural resource. We have to choose a consumption level Ct at time period t, from which we experience a net reward rt(ct). The remaining stock, if the available amount of resource is st, is then st - ct which shall renew at a pace ft(st - ct) (with the convention that ft(0) = 0). The T-Planning Horizon problem is to choose exploitation levels so to maximize total discounted reward: T-1 max E rt(Ct). t t=O s.t St+i = ft(St - Ct) ct E [0, st] t = 0, 1,2,...,T- 1 where 3 E (0, 1) is the discount factor. As an illustration of the parametric analysis, let us assume that the stock renewal dynamics ft(.) can take any of the forms described in the finite set {f0() = 0, f'(.),.., fm(-)}, vwhere by f0 we denote the no-renewal function. Intuitively, stock renewal dynamics can vary in time due to seasonality patterns, pollution, technological improvements etc... With this convention our parameter set is it = {0. 1,2,.., m and to any element p E F there is associated an infinite trend of stock dynamics. Here again, any finite horizon optimal consumption plan. can be trivially extended with an infinite tail of zero consumption so that it is an optimal solution of the infinite horizon problem with no-renewal dynamics at the tail. 4 Existence of Solution Horizon. Withl a slight abuse of notation let us write p E F(T) to mean that we are only concerned witli the first T parameters in the infinite vector p E F. Let us assume now that for every T-period horizon optimization problem there exists an optimal solution such that the first period decision behaves monotonically with respect to parameters p E F(T). A straightforwxard btut verv useful existence of solution horizon result follows: 5

Theorem 1: (Solution Horizon Existence) Under assumption 1 and assuming that there exist a doubly indexed collection: {aTP E A (p)}TEN,PE. such that the first time period actions are monotonically increasing in p E F(T) i.e: p > q ~= aoTP aoTq then there exists an infinite horizon optimal solution aP E A*(p) such that for every E > 0, there exist a planning horizon T, such that for T > Te we have: aTP - aO < E Such horizon is called a "solution" horizon. Proof: Without loss of generality let us assume that p = 0 for all t E KA. If not, one can always add the null parameter to Ft and monotonicity still holds since associated to the null parameter one can only have zero action. Let us now append the null action to aT'p at period T, and denote it by aT+'i.e: a (+ (aT, aT..., a-, o) By the Principle of Optimality, we have that aT+1must be an optimal solution to the T + I-planning horizon problem with parameters (PoPi,,...,p-,0), formally: aT+ A1 +(Po, i,...,PTr-,0) and by definition of the null parameter (po, Pi.... P-1 0) < (Po, pi., PT-1, PT) HenceI. by monotonicitv it follows that: T,p T+1 T+l,p In words. the first period optimal action sequence for forecast p E F is monotonically increasing.' Recall that A C n At, the subset of infinite feasible sequences of actions is assumed closed t=O oc anId by T vchonoffs theorem in At is compact in the product topology, hence A is compact. t=O,Let us Inow embed every element in the collection {aTzP E A p)}TEg into A as follows: aT^p(n p T.p ~p 0 def TP a - X ( pial....... _T, o,..., ) - a 3By Assuiliption 1, we know that using this embedding: (ao'T. aT'P......a 0,0....,) A (p,P2,...,PT-I, O,...) 0 ~ 1...... T -( 6

By compactness the collection {aT'P}TE has a converging subsequence, let us denote by aP the limit of such subsequence: lim aTkp = aP k —oo By assumption 1, aP E A*(p). By monotonicity of first period decision and compactness, the sequence {ao"} converges, moreover, since convergence in the product topology is componentwise convergence: lim a? = ao T ---o Or equivalently; for any E > 0, there exist a planning horizon Te such that for T > TE we have: aT,p < E In the proof of the above theorem we have constructed a well defined function a4: F -4 R+, the next corollary establishes that when action spaces are finite, this function inherits the monotonicity property. Corollary: Under the same assumptions of the previous theorem and assumming that action sets are finite, there exists an infinite horizon optimal solution aP E A*(p) such that the first period action is monotone and continuous in F, i.e for p, q E 7F: p >- q = a. > a. Proof: By the Solution Horizon Existence Theorem, for every E > 0, there exist a planning horizon T1 such that for T > TP we have: Tp - < Simiilarly. there exist a planning horizon Tq such that for T > Tq we have: a0 -ao < ILet us pick. - < 1 and T > max{7T. Tq}. By this choice we have that for T > T: T,p p Tq Q a0 =aO a = ao But y n monotonicity hypothesis: aQ > aq Moreover. since: lag -agl < ao - aTop + 4 Tp aT, + aoT'9- a 1 t n,1 > 0. by continuit02bf ao0'in p E F and the sequential construction of ap there.xislt - > ()0 nd T such that if d(p. q) < - then ql < Tp T T Tq a1- - a T+ to - aao aa ~ + aa a- ag < ll('nc. tle Illmap a F: T'.- R+ is continuous. * 'Thlls is due to the finiteness of ((T). 7

5 Existence of Forecast Horizons. In this section we prove the existence of Forecast Horizons for the class of dynamic optimization problems considered by exploiting the monotonicity properties of optimal solutions. It is worth emphasizing that these monotonicity properties are a a pervasive feature of many applications of the class of problems we study. To reader is referred to Heyman and Sobel's (1984) chapter 8. Let us now state and prove the most important result: Theorem 2: (Forecast Horizon Existence) Under Assumption 1 and assuming that action sets are finite and that there exists a doubly indexed collection: {aTp E A*(Tp) }TE,pEF such that first period actions are monotonically increasing in p E 'F(T), i.e: p q = aT > ao then there exists an infinite horizon optimal solution ap E A*(p) and a finite planning horizon T such that for T > T and for every q E F such that pt = qt, for 0 < t < T we have: T,q ap a0 =a0 Such horizon is called a "forecast horizon". Proof: Let us construct a sequence of forecasts based on p E T as follows; we append I'- to the T-truncation of p E F we obtain the forecast: u(T) = (pP1....-PT-l1 TT+1....) whelre c(learlvy we have u(T) - p asT -oc IBlt by tlhe Solution Horizon Existence theoren. we know that: T.p 71 a0 - a, cT- x (1) and by Corollary 1 the sequence { (7' } is mlonlotonically decreasing in T, i.e: u(T+l, u(T) a( _< ao I (copllllactness of the first period action set and continuity of the map a": F R+: u(T ^ a -- aa as T- oc. (2) 8

So the results (1) and (2) ensure the existence of a large enough horizon such that T such that for T > T: T,p u(T)ao ao' = Now let us consider q E F such that pt = qt, for 0 < t < T, by monotonicity it follows that and the choice of T, for every T > T: au(T) > a" > aT'P Hence, ap = ag; in words, infinite horizon first period optimal solution a~ is insensitive to parameter changes after time period T.. 6 Detection of Minimal Forecast Horizons. The proof of existence of a forecast horizon provides a few clues on how to effectively compute it, by means of a stopping rule. For the sake of concreteness we shall illustrate the suggested stopping rule in the context of production planning with convex production and inventory holding costs. 6.1 Application to Production Planning with Convex Costs. In Smith and Zhang (1997) a closed form formula is developed for the production planning problem with convex production and inventory holding costs, by exploiting the monotonicity properties of production plans with respect to demand, a result due to Veinnot(1964). -As an application of the theory above presented, we propose a stopping rule for the same prol)lemr structure. Moreover, we show that it detects the minimal forecast horizon and thle reader should note that it requires less restrictive monotonicity properties than those re 4quiired in Smith and Zhang's paper in that it is only assumed that first and not all periods ol)ti al decisions are monotone. Noiletheless, the minimality of the Forecast Horizon detected through the Stopping Rule Tsuggested is not evident. The reason being that in the construction carried out in the Solution I orizon Existence Theorem of an infinite horizon optimal solution whose first period action \\wais ionotone we selected for the finite horizon approximates any optimal monotone solution. 1T'lis is not enough to ensure that the Forecast Horizon effectively computed through the iabove Irocedure is minimal. For that purpose. we need to select for the finite horizon apIproxiniates the smallest monotone optimal solution. Here we digress a bit from Veinnott's resullt ill that it does not ensure the existence of such object. However, Topkis(1978) and iiiore recently Mlilgrom and Shannon(1994) have developed a general monotonicity theory of op)tillal solutions using lattice programming techniques that not surprisingly apply for il( produlction planning problemn with conivex costs. This theory ensures the existence of a.rrlnl(lc.1 an(l a largest optimal solutions that are monotone. 9

6.2 The Stopping Rule Assuming costs are uniformly bounded as follows: supt Ct() < C(.) suptht(') < h(.) One can construct a pessimistic scenario, in which demand, production and inventory holding costs are at their maximal levels, namely: N-I min lim sup E at(C(xt) + h(It+l)) N —oo t=O s.t It+l = It+ Xt- d M > xt >,It > 0 xt, It integer t =0,1,2,... The above problem is very easy to solve by means of the functional equation: (DP) V(I)= min {C(x) + h(x + I - d) + aV(x + I - d)} y i e h p M>x>0 Let us now consider the quasi-nonstationary infinite horizon production planning problem: NVmin lim sup E t(Ct(xt) + ht(It+l)) N ---oo t=O s.t It+l = It + xt - dt dt d M > xt > 0, It > 0 integer t>T t = 0, 1,2,... 'Which can be solved by the next simpler finite dimensional problem: T min ZE t(C(Xt) + h(It+1)) + Tl V(IT) t=O (PT) s.t =J rXT) s.t+ It + xt - dt xt > 0, It > 0 integer t - oil),...) T - 1 B3 the Corollary to Solution Horizon Existence Theorem there exists a optimal solution to thll problem (PT) such that its first period action is monotone in the demand parameters, say a1 and aT > a+'. Moreover. by the smallest monotone selection rule that we discussed ia)o\e. we know that ad is the smallest optimal solution to the above stated problem. Siiiilarlv. if we solve: T min E /'(Ct(xt) + hr(It+l)) (PT). t=0 ) s. It+l = It + xt - dt 11 > xt > O. t > 0 integer t = 0, 1,..., T- 1 e kilow tihat there exist and optimal solution such that its first period action say, T is iilontolli(callv increasing in T. i.e j+1 > - ao 10

Let us set aT to be the largest optimal solution. By the Forecast Horizon Existence Theorem, we know that these sequences must meet, in other words the algorithm we are to describe below must stop after a finite number of steps. Step 1. Solve Functional Equation (DP). T=1 Step 2. Solve (PT) and (PT) for aT and aoT Step 3. If aT = oT then Stop. Else T=T+1; Go to Step 2. Proposition 1 Let T* be the Forecast Horizon detected by the above procedure, T* is also the minimal Forecast Horizon. Proof: By contradiction, let us assume there exists T < T* such that T is the minimal Forecast Horizon. By hypothesis: -T T a0 > go But since aT is the first period action of the smallest optimal solution to problem (PT) and oT is the first period action of the largest optimal solution to problem (PT), this implies that the above inequality is valid for any chosen pair of optimal solutions to the problems (PT) and (PT), but this contradicts T being a Forecast Horizon. * 7 Conclusion. We have presented strong existence and computational results for forecast horizons in a large class of dynamic optimization problems. These results depend critically upon the inonotoniciti properties of optimal solutions, which is a rather natural and pervasive feature of these models. We are currently exploring the extension of this approach to infinite horizoin stochastic dynamic optimization problems which also posess monotonicity properties of optimIal early decisions. 11

References [1] Bes C. and Sethi S. "Concepts of forecast and decision horizons: applications to dynamic stochastic optimization problems" Mathematics of Operations Research 13 pp 295-310 [2] Flam, S and Fougeres A. "Infinite horizon programs: convergence of approximate solutions" Annals of Operations Research 29 (1991) pp 333-350 [3] Haurie A. and Sethi S. "Decisions and forecast horizons, agreeable plans and the maximum principle for infinite horizon control problems" Operations Research Letters Vol 3 (5) (1984) pp 261-266 [4] Heyman D. and Sobel M. "Stochastic Models in Operations Research" Vol II" McGraw Hill N. Y,1984 [5] Milgrom P. and Shannon C. "Monotone comparative statics" Econometrica 62 (1994) pp 157-180 [6] Morton, T. "The nonstationarv infinite horizon inventory problem" Management Science Vol 24 No. 14 1978 [7] Schochetman I. and Smith R.L "Infinite horizon optimization" Mathematics of Operations Research Vol 14 No. 3 1989 pp 559-554 [8] Schochetman I. and Smith R. L. "Finite dimensional approximation in infinite dimensional mathematical programming". Mathematical Programming 54(1992) 307-333 [9] Smith R.L.and Zhang R. "Infinite horizon production planning in time varying systems with convex production and inventory Costs" Management Science (in press) [10] Topkis D. "Minimizing a submodular function on a lattice" Operations Research Vol. 26 No.2 1978. p.p 305-321 [11] Veinnott A. "Production planning with convex costs: a parametric study" Management Science 10 441-460 (1964) 12