Solution of Stochastic Linear Programs by Discretization Methods

Solution procedures for stochastic linear optimization problems (also called stochastic linear programs (SLP)) by means of discretization of the probability distribution of the random parameters are treated in this chapter: Given a stochastic cost vector $$c(\omega )$$ c ( ω ) , a stochastic technology matrix $$T(\omega )$$ T ( ω ) and a stochastic right-hand side, $$h(\omega )$$ h ( ω ) , consider a linear program for minimizing a linear function $$c(\omega )^Tx$$ c ( ω ) T x of the design vector x subject to the linear constraints $$T(\omega )x = h(\omega )$$ T ( ω ) x = h ( ω ) , $$x \ge 0$$ x ≥ 0 . Due to the stochastic variations of the data $$(c,T,h)=(c(\omega ),T(\omega ),h(\omega ))$$ ( c , T , h ) = ( c ( ω ) , T ( ω ) , h ( ω ) ) , for the selection of an optimal decision vector $$x^*$$ x ∗ , an appropriate deterministic substitute problem has to be chosen. Here, we look for optimal decision vectors $$x^* \ge 0$$ x ∗ ≥ 0 minimizing the expected total cost defined by the sum of the primal costs $$c(\omega )^Tx$$ c ( ω ) T x and the costs $$p(T(\omega )x-h(\omega ))$$ p ( T ( ω ) x - h ( ω ) ) caused by the violation of the equality constraints $$T(\omega )x = h(\omega )$$ T ( ω ) x = h ( ω ) . These costs are determined here by means of sublinear functions $$p=p(z)$$ p = p ( z ) , involving, e.g., the class of norms for an error vector z. Moreover, several sublinear cost functions can be represented by the value function of an optimization problem, as, e.g., a Minkowski functional, see Chap. 11 . Then, error estimates are given, and a priori bounds for the approximation error are derived. Furthermore, exploiting invariance properties of the probability distribution of the random parameters, problem-oriented discretizations are derived which simplify then the computation of admissible descent directions at non-stationary points.