Tree Bounds for Sums of Bernoulli Random Variables: A Linear Optimization Approach

References

• Ahmed S, Papageorgiou DJ (2013) Probabilistic set covering with correlations. Oper. Res. 61(2):438–452.Link, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization, vol. 6 (Athena Scientific, Belmont, MA).Google Scholar
• Billionnet A (1992) Maximizing a quadratic pseudo-boolean function with a cardinality constraint. Presentation, International Colloquium on Graphs and Optimization.Google Scholar
• Boland PJ, Proschan F (1983) The reliability of k out of n systems. Ann. Probab. 11(3):760–764.Google Scholar
• Bonami P, Günlük O, Linderoth J (2018a) Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods. Math. Programming Comput. 10(3):333–382.Google Scholar
• Bonami P, Lodi A, Zarpellon G (2018b) Learning a classification of mixed-integer quadratic programming problems. van Hoeve WJ, ed. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Lecture Notes in Computer Science, vol. 10848 (Springer, Cham, Switzerland), 595–604.Google Scholar
• Boros E, Prekopa A (1989) Closed form two-sided bounds for probabilities that at least r and exactly r out of n events occur. Math. Oper. Res. 14(2):317–342.Link, Google Scholar
• Boros E, Scozzari A, Tardella F, Veneziani P (2014) Polynomially computable bounds for the probability of the union of events. Math. Oper. Res. 39(4):1311–1329.Link, Google Scholar
• Brechmann EC, Joe H (2015) Truncation of vine copulas using fit indices. J. Multivariate Anal. 138:19–33.Google Scholar
• Brechmann EC, Czado C, Aas K (2012) Truncated regular vines in high dimensions with application to financial data. Canadian J. Statist. 40(1):68–85.Google Scholar
• Bukszár J, Szántai T (2002) Probability bounds given by hypercherry trees. Optim. Methods Software 17(3):409–422.Google Scholar
• Caprara A, Pisinger D, Toth P (1999) Exact solution of the quadratic knapsack problem. INFORMS J. Comput. 11(2):125–137.Link, Google Scholar
• Chang B, Pan S, Joe H (2019) Vine copula structure learning via Monte Carlo tree search. Proc. Machine Learn. Res. 89:353–361.Google Scholar
• Chen T (1998) Optimal lower bounds for bivariate probabilities. Adv. Appl. Probab. 30(2):476–492.Google Scholar
• Chow C, Liu C (1968) Approximating discrete probability distributions with dependence trees. IEEE Trans. Inform. Theory 14(3):462–467.Google Scholar
• Cooke RM, Joe H, Chang B (2019) Vine copula regression for observational studies. AStA Adv. Statist. Anal. 104:1–27.Google Scholar
• Dawson D, Sankoff D (1967) An inequality for probabilities. Proc. Amer. Math. Soc. 18(3):504–507.Google Scholar
• Dhara A, Das B, Natarajan K (2020) Worst-case expected shortfall with univariate and bivariate marginals. INFORMS J. Comput., ePub ahead of print July 16, https://doi.org/10.1287/ijoc.2019.0939.Google Scholar
• Dissmann J, Brechmann E, Czado C, Kurowicka D (2013) Selecting and estimating regular vine copulae and application to financial returns. Comput. Statist. Data Anal. 59(C):52–69.Google Scholar
• Embrechts P, Puccetti G (2010) Bounds for the sum of dependent risks having overlapping marginals. J. Multivariate Anal. 101(1):177–190.Google Scholar
• Fomeni FD, Letchford AN (2014) A dynamic programming heuristic for the quadratic knapsack problem. INFORMS J. Comput. 26(1):173–182.Link, Google Scholar
• Grötschel M, Lovász L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Algorithms Combinatorics 2:65–84.Google Scholar
• Hailperin T (1965) Best possible inequalities for the probability of a logical function of events. Amer. Math. Monthly 72(4):343–359.Google Scholar
• Hunter D (1976) An upper bound for the probability of a union. J. Appl. Probab. 13(3):597–603.Google Scholar
• Kounias EG (1968) Bounds for the probability of a union, with applications. Ann. Math. Statist. 39(6):2154–2158.Google Scholar
• Kounias S, Marin J (1976) Best linear Bonferroni bounds. SIAM J. Appl. Math. 30(2):307–323.Google Scholar
• Kurowicka D (2010) Optimal truncation of vines. Kurowicka D, Joe H, eds. Dependence Modeling: Vine Copula Handbook (World Scientific Publishers, Singapore), 233–247.Google Scholar
• Kwerel SM (1975) Most stringent bounds on aggregated probabilities of partially specified dependent probability systems. J. Amer. Statist. Assoc. 70(350):472–479.Google Scholar
• Lauritzen S (1996) Graphical Models, Oxford Statistical Science Series (Clarendon Press, Oxford, UK).Google Scholar
• Morgenstern D (1980) Berechnung des maximalen signifikanzniveaus des testes lehneh0 ab, wennk untern gegebenen tests zur ablehnung fuhren. Metrika 27(1):285–286.Google Scholar
• Nelsen RB (2006) An Introduction to Copulas, Springer Series in Statistics (Springer-Verlag, Berlin, Heidelberg).Google Scholar
• Nemhauser G, Wolsey L (2014) General algorithms. Graham RL, Lenstra JK, Tarjan RE, eds. Integer and Combinatorial Optimization (John Wiley and Sons, Ltd., Hoboken, NJ), 349–382.Google Scholar
• Padberg M (1989) The Boolean quadric polytope: Some characteristics, facets and relatives. Math. Programming 45(1):139–172.Google Scholar
• Pitowsky I (1991) Correlation polytopes: Their geometry and complexity. Math. Programming 50(1):395–414.Google Scholar
• Prékopa A (1988) Boole-Bonferroni inequalities and linear programming. Oper. Res. 36(1):145–162.Link, Google Scholar
• Prékopa A (1990a) The discrete moment problem and linear programming. Discrete Appl. Math. 27(3):235–254.Google Scholar
• Prékopa A (1990b) Sharp bounds on probabilities using linear programming. Oper. Res. 38(2):227–239.Link, Google Scholar
• Prékopa A (2003) Probabilistic programming. Handbook Oper. Res. Management Sci. 10:267–351.Google Scholar
• Prékopa A, Gao L (2005) Bounding the probability of the union of events by aggregation and disaggregation in linear programs. Discrete Appl. Math. 145(3):444–454.Google Scholar
• Prékopa A, Vizvári B, Regös G (1997) A Method of Disaggregation for Bounding Probabilities of Boolean Functions of Events (Rutgers Center for Operations Research, Newark, NJ).Google Scholar
• Puccetti G, Wang R (2015) Extremal dependence concepts. Statist. Sci. 30(4):485–517.Google Scholar
• Qiu F, Ahmed S, Dey SS (2016) Strengthened bounds for the probability of k-out-of-n events. Discrete Appl. Math. 198:232–240.Google Scholar
• Rader DJ Jr, Woeginger GJ (2002) The quadratic 0–1 knapsack problem with series–parallel support. Oper. Res. Lett. 30(3):159–166.Google Scholar
• Ruger B (1978) Das maximale signifikanzniveau des tests lehne ho ab, wenn k unter n gegebenen tests zur ablehnungfuhren. Metrika 25:171–178.Google Scholar
• Rüschendorf L (1991) Bounds for Distributions with Multivariate Marginals, Lecture Notes–Monograph Series, vol. 19 (Institute of Mathematical Statistics, Munster, Germany), 285–310.Google Scholar
• Saxena A, Goyal V, Lejeune MA (2009) MIP reformulations of the probabilistic set covering problem. Math. Programming 121(1):1–31.Google Scholar
• Tomescu I (1986) Hypertrees and Bonferroni inequalities. J. Combinatiorial Theory Ser. B 41(2):209–217.Google Scholar
• Vorobev N (1962) Consistent families of measures and their extensions. Theory Probab. Appl. 7(2):147–163.Google Scholar
• Wainwright MJ, Jordan MI (2008) Graphical Models, Exponential Families, and Variational Inference, Foundations and Trends in Machine Learning, vol. 1 (Now Publishers, Norwell, MA).Google Scholar
• Wang S (1998) An actuarial index of the right-tail risk. North Amer. Actuarial J. 2(2):88–101.Google Scholar
• Worsley K (1982) An improved Bonferroni inequality and applications. Biometrika 69(2):297–302.Google Scholar
• Yang J, Alajaji F, Takahara G (2016) Lower bounds on the probability of a finite union of events. SIAM J. Discrete Math. 30(3):1437–1452.Google Scholar