Some Explicit Results for the Distribution Problem of Stochastic Linear Programming

Affiliation(s)

^{1}
Penn State University, State College, PA, USA.

^{2}
CAF Development Bank, Caracas, Venezuela.

^{3}
California State University at Long Beach, Long Beach, CA, USA.

^{4}
University of Oklahoma, Norman, OK, USA.

ABSTRACT

A technique is developed for finding a closed form expression for the cumulative distribution function of the maximum value of the objective function in a stochastic linear programming problem, where either the objective function coefficients or the right hand side coefficients are continuous random vectors with known probability distributions. This is the “wait and see” problem of stochastic linear programming. Explicit results for the distribution problem are extremely difficult to obtain; indeed, previous results are known only if the right hand side coefficients have an exponential distribution [1]. To date, no explicit results have been obtained for stochastic c, and no new results of any form have appeared since the 1970’s. In this paper, we obtain the first results for stochastic c, and new explicit results if b an c are stochastic vectors with an exponential, gamma, uniform, or triangle distribution. A transformation is utilized that greatly reduces computational time.

A technique is developed for finding a closed form expression for the cumulative distribution function of the maximum value of the objective function in a stochastic linear programming problem, where either the objective function coefficients or the right hand side coefficients are continuous random vectors with known probability distributions. This is the “wait and see” problem of stochastic linear programming. Explicit results for the distribution problem are extremely difficult to obtain; indeed, previous results are known only if the right hand side coefficients have an exponential distribution [1]. To date, no explicit results have been obtained for stochastic c, and no new results of any form have appeared since the 1970’s. In this paper, we obtain the first results for stochastic c, and new explicit results if b an c are stochastic vectors with an exponential, gamma, uniform, or triangle distribution. A transformation is utilized that greatly reduces computational time.

KEYWORDS

Stochastic Linear Programming, The Wait and See Problem, Mathematics Subject Classification

Stochastic Linear Programming, The Wait and See Problem, Mathematics Subject Classification

1. Introduction

Consider the linear programming problem,

(1)

(2)

(3)

where is an vector whose component is (where, ) and b is an vector whose component is b_{i}, is an matrix, I is an identity matrix and x is an vector. Further assume that b and c are random vectors with joint density functions and respectively. Next, consider the value of by first observing the vector b or the vector c and then solving (1)-(3). This paper is interested in finding explicit expressions for the distribution of if either b or c is random. This is called the distribution problem of stochastic linear programming.

Early work on the distribution problem can be found in Babbar [2] , Bereanu [3] [4] [5] [6] [7] , Hsia [8] , Prekopa [9] , Sengupta, Tintner, and Millham [10] , Sengupta, Tintner, and Morrison [11] , and Wets [12] . For additional references, see the bibliographies by Stancu-Minasian [13] and Van Der Vlerk [14] . Application of the distribution problem can be found in the areas of agriculture [15] and economic planning [10] , [11] . Explicit results for the distribution of are very difficult to obtain; indeed, most analyses rely on approximation techniques or simulation. (See, for example, Bracken and Soland [16] , Sarper [15] , or Dempster [17] ). Bereanu [3] discovered that under certain assumptions, the sample space of the random coefficients allows a partition into non-overlapping sets, called decision regions, such that a basis of the linear programming problem can be assigned to each of the sets, and this basis remains optimal for all of its sample points. Ewbank, et al. [1] extended this theory using a Jacobian transformation to simplify the computational analysis. To date, we believe that an explicit expression for the distribution of has only been obtained for stochastic b [1] , and no explicit results have been obtained for stochastic c. In addition, no explicit results have been obtained for non-exponential distributions. In this paper, we obtain new explicit results for exponential, uniform, gamma, and triangle distributions with b or c random. These are the first explicit results for the case in which c is random.

2. Theory

Following [1] , consider the linear programming problem (1)-(3). Let be the vector of basic variables corresponding to the ith basis, and is the basis matrix whose columns are the columns of corresponding to the elements of. Let be the vector of coefficients of the basic variables in basis and let be the column of corresponding to. Also, and. is an optimal basis if

For all

(4)

and is feasible if

(5)

For the case in which the b vector is random, let the probability space be defined by the m-tuple. Bereanu discovered that there exist non-overlapping regions

(6)

where

(7)

Thus,

(8)

Now, let

Since

(9)

Then

(10)

(11)

(12)

Thus,

(13)

Now, consider the case in which only the c vector is random. Let the probability space C be defined by the n-tuple. Bereanu [3] found that the space C is partitioned by the sets:

(14)

where refers to the basis. Further the set of points is of probability measure zero if the joint density function of is continuous. Points in this set are such that alternate optimal basis give the same value of. Also,

(15)

Thus,

(16)

where is an arbitrary constant.

To evaluate the right-hand side of equation Equation (15) let. By definition

(17)

Since

(18)

Then

(19)

where

(20)

Thus, if only the c vector is random the distribution function of can be found, in theory, by evaluating the integral in equation Equation (20). Given a basis Bi and sets and, the limits of the integral in Equation (12) and Equation (20) are the intersection of m or n hyperplanes (depending on whether the b vector or the c vector is stochastic). These limits are extremely difficult to obtain if the probability space has dimension greater than 3. Ewbank, et al., [1] developed a Jacobian transformation that greatly simplifies the computation of the integrals.

In the case of stochastic b, Let

(21)

By substituting for b we have:

(22)

The probability that a basis G remains feasible is

(23)

where is the set of b’s defined in Equation (20), and by substituting Equation (21) in Equation (22), we have:

(24)

where is the Jacobian

Because and, this implies

(25)

Note that since

3. Computational Results

The problems were run using the Mathematica software version 8.0.1.0 utilizing the supercomputer at the University of Oklahoma.

CPUs: All compute nodes have dual Intel Xeon E5-2650 “Sandy Bridge” oct core 2.0 GHz CPUs; there is also one “fat node” with quad Intel Xeon E7-4830 “Westmere” oct core 2.13 GHz CPUs.

RAM: Most of the compute nodes have 32 GB of 1333 MHz RAM and 23 with 64 GB of 1333 MHz RAM; the one “fat node” has 1 TB of 1066 MHz RAM, which is called large memory.

Accelerators: There are 18 NVIDIA Tesla M2075 cards, for an aggregate of an additional approximately 9 TFLOPs double precision.

In order to compare the run times, four types of distributions were considered as shown in Table 1. The coefficients were randomly generated in small interval, because large intervals led to computational results that had results with coefficients of the orders of 1020 or larger.

3.1. Results for Stochastic b with Exponential Distribution

3.1.1. Problem 1

Table 1. Equations of distribution.

3.1.2. Problem 2

3.1.3. Problem 3

3.2. Results for Stochastic b with Uniform Distribution

3.2.1. Problem 1

3.2.2. Problem 2

3.2.3. Problem 3

3.3. Results for Stochastic b with Gamma Distribution

3.3.1. Problem 1

3.3.2. Problem 2

3.4. Results for Stochastic b with Triangle Distribution

Problem 1

3.5. Results for Stochastic c with Exponential Distribution

3.5.1. Problem 1

3.5.2. Problem 2

3.6. Results for Stochastic c with Uniform Distribution

3.6.1. Problem 1

3.6.2. Problem 2

3.7. Results for Stochastic c with Gamma Distribution

3.7.1. Problem 1

3.7.2. Problem 2

3.8. Results for Stochastic c with Triangle Distribution

3.8.1. Problem 1

3.8.2. Problem 2

4. Computational Time Comparisons

The different distributions were solved using both Bereanu’s method and the Ewbank, Foote and Kumin transformation method to compare the two. Table 2 and Table 3 compare the run times for both methods for case I and case II. The results show that

Table 2. Comparison between Bereanu and EFK method for case I.

Table 3. Comparison between Bereanu and EFK method for case II.

the EFK method substantially reduces the computational time. In addition, Bereanu’s method is not able to solve some larger sizes of the problem. All times are measured in seconds.

Cite this paper

Ansaripour, A. , Mata, A. , Nourazari, S. and Kumin, H. (2016) Some Explicit Results for the Distribution Problem of Stochastic Linear Programming.*Open Journal of Optimization*, **5**, 140-162. doi: 10.4236/ojop.2016.54014.

Ansaripour, A. , Mata, A. , Nourazari, S. and Kumin, H. (2016) Some Explicit Results for the Distribution Problem of Stochastic Linear Programming.

References

[1] Ewbank, J., Foote, B. and Kumin, H.A. (1974) Method for the Solution of the Distribution Problem of Stochastic Linear Programming. SIAM Journal on Applied Mathematics, 26, 225-238.

https://doi.org/10.1137/0126020

[2] Babbar, M.M. (1975) Distribution of Solutions of a Set of Linear Equation with an Application to Linear Programming. Journal of the American Statistical Association, 50, 854-869.

https://doi.org/10.1080/01621459.1955.10501971

[3] Bereanu, B. (1963) On Stochastic Linear Programming I. Distribution Problems: A Single Random Variable. Revue Roumaine de Mathématique Pures et Appliquées, 8, 683-697.

[4] Bereanu, B. (1966) On Stochastic Linear Programming. The Laplace Transform of the Distribution of the Optimum and Applications. Journal of Mathematical Analysis and Applications, 15, 280-294.

https://doi.org/10.1016/0022-247X(66)90120-X

[5] Bereanu, B. (1966) On Stochastic Linear Programming II. Distribution Problems. Nonstochastic Technological Matrix. Revue Roumaine de Mathématique Pures et Appliquées, 11, 713-725.

[6] Bereanu, B. (1967) On Stochastic Linear Programming Distribution Problems, Stochastic Technology Matrix. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 8, 148-152.

https://doi.org/10.1007/BF00536917

[7] Bereanu, B. (1971) The Distribution Problem in Stochastic Linear Programming. The Cartesian Integration Method. Reprint No. 7103, Center of Mathematical Statistics of the Academy of the Socialist Republic of Romania, Bucharest.

[8] Hsia, W.S. (1977) Probability Density Funaction of a Stochastic Linear Programming Problem. Naval Research Logistics Quarterly, 24, 417-424.

https://doi.org/10.1002/nav.3800240304

[9] Prekopa, A. (1966) On the Probability Distribution of the Optimum of a Random Linear Program. SIAM Journal on Control, 4, 211-222.

https://doi.org/10.1137/0304020

[10] Sengupta, J.K., Tintner, G. and Millham, C. (1963) On Some Theorems of Stochastic Linear Programming with Application. Management Science, 10, 143-159.

https://doi.org/10.1287/mnsc.10.1.143

[11] Sengupta, J.K., Tintner, G. and Morrison, B. (1963) Stochastic Linear Programming with Application to Economic models. Economica, 30, 262-276.

https://doi.org/10.2307/2601546

[12] Wets, R.J.-B. (1980) The Distribution Problem and Its Relation to Other Problems in Stochastic Programming. In: Dempster, M., Ed., Stochastic Programming, Academic Press, London, 245-262.

[13] Stancu-Minasian, I. and Wets, R.J.-B. (1976) A Research Bibliography in Stochastic Programming, 1955-1975. Operations Research, 24, 1078-1119.

https://doi.org/10.1287/opre.24.6.1078

[14] Van Der Vlerk, H.M. (1996) Stochastic Integer Programming Bibliography.

http://mally.Eco.Rug.Nl/index.html

[15] Sarper, H. (1993) Monte Carlo Simulation for Analysis of the Optimum Value Distribution in Stochastic Mathematical Programs. Mathematics and Computers in Simulation, 35, 469-480. https://doi.org/10.1016/0378-4754(93)90065-3

[16] Bracken, J. and Soland, R.M. (1966) Statistical Decision Analysis of Stochastic Linear Programming Problems. Naval Research Logistics Quarterly, 13, 205-225.

https://doi.org/10.1002/nav.3800130302

[17] Dempster, M.A.H. and Papagaki-Papoulias, A. (1980) Computational Experience with an Approximate Method for the Distribution Problem. In: Dempster, M., Ed., Stochastic Programming, Academic Press, London, 223-243.

[1] Ewbank, J., Foote, B. and Kumin, H.A. (1974) Method for the Solution of the Distribution Problem of Stochastic Linear Programming. SIAM Journal on Applied Mathematics, 26, 225-238.

https://doi.org/10.1137/0126020

[2] Babbar, M.M. (1975) Distribution of Solutions of a Set of Linear Equation with an Application to Linear Programming. Journal of the American Statistical Association, 50, 854-869.

https://doi.org/10.1080/01621459.1955.10501971

[3] Bereanu, B. (1963) On Stochastic Linear Programming I. Distribution Problems: A Single Random Variable. Revue Roumaine de Mathématique Pures et Appliquées, 8, 683-697.

[4] Bereanu, B. (1966) On Stochastic Linear Programming. The Laplace Transform of the Distribution of the Optimum and Applications. Journal of Mathematical Analysis and Applications, 15, 280-294.

https://doi.org/10.1016/0022-247X(66)90120-X

[5] Bereanu, B. (1966) On Stochastic Linear Programming II. Distribution Problems. Nonstochastic Technological Matrix. Revue Roumaine de Mathématique Pures et Appliquées, 11, 713-725.

[6] Bereanu, B. (1967) On Stochastic Linear Programming Distribution Problems, Stochastic Technology Matrix. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 8, 148-152.

https://doi.org/10.1007/BF00536917

[7] Bereanu, B. (1971) The Distribution Problem in Stochastic Linear Programming. The Cartesian Integration Method. Reprint No. 7103, Center of Mathematical Statistics of the Academy of the Socialist Republic of Romania, Bucharest.

[8] Hsia, W.S. (1977) Probability Density Funaction of a Stochastic Linear Programming Problem. Naval Research Logistics Quarterly, 24, 417-424.

https://doi.org/10.1002/nav.3800240304

[9] Prekopa, A. (1966) On the Probability Distribution of the Optimum of a Random Linear Program. SIAM Journal on Control, 4, 211-222.

https://doi.org/10.1137/0304020

[10] Sengupta, J.K., Tintner, G. and Millham, C. (1963) On Some Theorems of Stochastic Linear Programming with Application. Management Science, 10, 143-159.

https://doi.org/10.1287/mnsc.10.1.143

[11] Sengupta, J.K., Tintner, G. and Morrison, B. (1963) Stochastic Linear Programming with Application to Economic models. Economica, 30, 262-276.

https://doi.org/10.2307/2601546

[12] Wets, R.J.-B. (1980) The Distribution Problem and Its Relation to Other Problems in Stochastic Programming. In: Dempster, M., Ed., Stochastic Programming, Academic Press, London, 245-262.

[13] Stancu-Minasian, I. and Wets, R.J.-B. (1976) A Research Bibliography in Stochastic Programming, 1955-1975. Operations Research, 24, 1078-1119.

https://doi.org/10.1287/opre.24.6.1078

[14] Van Der Vlerk, H.M. (1996) Stochastic Integer Programming Bibliography.

http://mally.Eco.Rug.Nl/index.html

[15] Sarper, H. (1993) Monte Carlo Simulation for Analysis of the Optimum Value Distribution in Stochastic Mathematical Programs. Mathematics and Computers in Simulation, 35, 469-480. https://doi.org/10.1016/0378-4754(93)90065-3

[16] Bracken, J. and Soland, R.M. (1966) Statistical Decision Analysis of Stochastic Linear Programming Problems. Naval Research Logistics Quarterly, 13, 205-225.

https://doi.org/10.1002/nav.3800130302

[17] Dempster, M.A.H. and Papagaki-Papoulias, A. (1980) Computational Experience with an Approximate Method for the Distribution Problem. In: Dempster, M., Ed., Stochastic Programming, Academic Press, London, 223-243.