×

Threshold Boolean form for joint probabilistic constraints with random technology matrix. (English) Zbl 1297.90101

Math. Program. 147, No. 1-2 (A), 391-427 (2014); erratum ibid. 155, No. 1–2 (A), 617-620 (2016).
Summary: We develop a new modeling and solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint. We then construct a tight threshold Boolean minorant for the pdBf. Any separating structure of the tight threshold Boolean minorant defines sufficient conditions for the satisfaction of the probabilistic constraint and takes the form of a system of linear constraints. We use the separating structure to derive three new deterministic formulations for the studied stochastic problem, and we derive a set of strengthening valid inequalities. A crucial feature of the new integer formulations is that the number of integer variables does not depend on the number of scenarios used to represent uncertainty. The computational study, based on instances of the stochastic capital rationing problem, shows that the mixed-integer linear programming formulations are orders of magnitude faster to solve than the mixed-integer nonlinear programming formulation. The method integrating the valid inequalities in a branch-and-bound algorithm has the best performance.

MSC:

90C15 Stochastic programming
90C09 Boolean programming
06E30 Boolean functions
90C06 Large-scale problems in mathematical programming

Software:

Couenne; JBool
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Glover, F.: Improved linear integer programming formulations of nonlinear integer problems. Manag. Sci. 22(4), 455-460 (1975) · Zbl 0318.90044 · doi:10.1287/mnsc.22.4.455
[2] Gurgur, C.Z., Luxhoj, J.T.: Application of chance-constrained programming to capital rationing problems with asymmetrically distributed cash flows and available budgets. Eng. Econ. 48(3), 241-258 (2003) · doi:10.1080/00137910308965064
[3] Henrion, R.: Structural properties of linear probabilistic constraints. Optimization 56(4), 425-440 (2007) · Zbl 1149.90110 · doi:10.1080/02331930701421046
[4] Henrion, R., Strugarek, C.: Convexity of chance constraints with independent random variables. Comput. Optim. Appli. 41(2), 263-276 (2008) · Zbl 1168.90568 · doi:10.1007/s10589-007-9105-1
[5] Kataoka, S.: A stochastic programming model. Econometrica 31(1-2), 181-196 (1963) · Zbl 0125.09601 · doi:10.2307/1910956
[6] Khan, A.: Capital budgeting under capital rationing: an analytical overview of optimization models for government. Int. J. Public Adm. 31(2), 168-194 (2008) · doi:10.1080/01900690701411016
[7] Lejeune, M.A.: A VaR Black-Litterman model for the construction of absolute return fund-of-funds. Quant. Financ. 11(10), 639-664 (2011) · Zbl 1258.91200 · doi:10.1080/14697680903121018
[8] Lejeune, M.A.: Pattern-based modeling and solution of probabilistically constrained optimization problems. Oper. Res. 60(6), 1356-1372 (2012) · Zbl 1269.90071 · doi:10.1287/opre.1120.1120
[9] Lejeune, M.A.: Pattern definition of the \[p\] p-efficiency concept. Ann. Oper. Res. 200(1), 23-36 (2012) · Zbl 1261.90032 · doi:10.1007/s10479-010-0803-1
[10] Lorie, J.H., Savage, L.J.: Three problems in rationing capital. J. Bus. 28(2), 229-239 (1955) · doi:10.1086/294081
[11] Luedtke, J., Ahmed, S.: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2), 674-699 (2008) · Zbl 1177.90301 · doi:10.1137/070702928
[12] Mukherjee, T., Hingorani, V.: Capital-rationing decisions of fortune 500 firms: a survey. Financ. Pract. Educ. 9(1), 7-15 (1999)
[13] Muroga, S.: Threshold Logic and Its Applications. Wiley, New York, NY (1971) · Zbl 0243.94014
[14] Naslund, B.: A model of capital budgeting under risk. J. Bus. 39(2), 257-271 (1966) · doi:10.1086/294851
[15] Prékopa, A.: Programming under probabilistic constraints with a random technology matrix. Math. Oper. Stat. 5(2), 109-116 (1974) · Zbl 0302.90043
[16] Prékopa, A.: Stochastic Programming. Kluwer, Boston, MA (1995) · doi:10.1007/978-94-017-3087-7
[17] Prékopa, A.: Probabilistic programming models. Chapter 5. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming: Handbook in Operations Research and Management Science, vol. 10, pp. 267-351. Elsevier, Amsterdam (2003)
[18] Prékopa, A., Yoda, K., Subasi, M.: Uniform quasi-concavity in probabilistic constrained stochastic programming. Oper. Res. Lett. 39(3), 188-192 (2011) · Zbl 1219.90114 · doi:10.1016/j.orl.2011.03.007
[19] Ruszczyński, A.: Probabilistic programming with discrete distribution and precedence constrained knapsack polyhedra. Math. Program. 93(2), 195-215 (2002) · Zbl 1065.90058 · doi:10.1007/s10107-002-0337-7
[20] Sarper, H.: Capital rationing under risk: a chance-constrained approach using uniformly distributed cash flows and available budgets. Eng. Econ. 39(1), 49-76 (1993) · doi:10.1080/00137919308903112
[21] Tanner, M.W., Ntaimo, L.: IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation. Eur. J. Oper. Res. 207(1), 290-296 (2010) · Zbl 1205.90211 · doi:10.1016/j.ejor.2010.04.019
[22] van Ackooij, W., Henrion, R., Moller, A., Zorgati, R.: On joint probabilistic constraints with Gaussian coefficient matrix. Oper. Res. Lett. 39(2), 99-102 (2011) · Zbl 1218.90147 · doi:10.1016/j.orl.2011.01.005
[23] van de Panne, C., Popp, W.: Minimum-cost cattle feed under probabilistic constraints. Manag. Sci. 9(3), 405-430 (1963) · doi:10.1287/mnsc.9.3.405
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.