We consider the problem of finding upper and lower bounds for the probability of the union of events when the probabilities of the single events and the probabilities of the intersections of up to m events are given. It is known that the best possible bounds can be obtained by solving linear programming problems with a number of variables that is exponential in the number of events. Because of their size and structure, these large linear programs are known to be very hard to solve. In the literature simpler, polynomially sized aggregations are considered and numerous closed form or polynomially computable bounds are derived from those. We present here a new approach that introduces additional constraints to the dual linear programming problems in such a way that those become polynomially solvable. By using different sets of additional constraints, we introduce three new classes of polynomially computable upper and lower bounds. We show that they dominate almost all efficiently computable bounds known in the literature. Furthermore, by characterizing the vertices of two new classes of polyhedra, we can show that in two cases our bounds coincide with classical bounds, proving new extremal properties for those well-known bounds. Finally, we provide extensive numerical results comparing the average tightness of the various bounds on a large number of instances.

Polynomially Computable Bounds for the Probability of the Union of Events / E. Boros; A. Scozzari; TARDELLA, Fabio; P. Veneziani. - In: MATHEMATICS OF OPERATIONS RESEARCH. - ISSN 0364-765X. - STAMPA. - 39:(2014), pp. 1311-1329. [10.1287/moor.2014.0657]

Polynomially Computable Bounds for the Probability of the Union of Events

TARDELLA, Fabio;
2014

Abstract

We consider the problem of finding upper and lower bounds for the probability of the union of events when the probabilities of the single events and the probabilities of the intersections of up to m events are given. It is known that the best possible bounds can be obtained by solving linear programming problems with a number of variables that is exponential in the number of events. Because of their size and structure, these large linear programs are known to be very hard to solve. In the literature simpler, polynomially sized aggregations are considered and numerous closed form or polynomially computable bounds are derived from those. We present here a new approach that introduces additional constraints to the dual linear programming problems in such a way that those become polynomially solvable. By using different sets of additional constraints, we introduce three new classes of polynomially computable upper and lower bounds. We show that they dominate almost all efficiently computable bounds known in the literature. Furthermore, by characterizing the vertices of two new classes of polyhedra, we can show that in two cases our bounds coincide with classical bounds, proving new extremal properties for those well-known bounds. Finally, we provide extensive numerical results comparing the average tightness of the various bounds on a large number of instances.
2014
39
1311
1329
E. Boros; A. Scozzari; TARDELLA, Fabio; P. Veneziani
File in questo prodotto:
File Dimensione Formato  
Boros Scozzari Tardella Veneziani - Polynomially Computable Bounds for the Probability of the Union of Events.pdf

Accesso chiuso

Dimensione 383.4 kB
Formato Adobe PDF
383.4 kB Adobe PDF   Richiedi una copia

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1247724
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 15
social impact