The research objective of this project is to develop new models and methods to find sharp bounds in a numerically stable and computationally efficient manner, under the knowledge of the support of the discrete random variables involved and partial knowledge of their distribution. In many cases this means the knowledge of a finite number of moments, including in the multivariate case problems where the univariate marginals and some of the moments are known. These type of problems, including the Boolean Probabillity Bounding Problem, Discrete Moment Problems and Multivariate Discrete Moment Problems, are notoriously difficult computationally, and can equivalently be viewed as very large scale (typically exponentially large in the number of random variables) linear programming problems. Linear programming will be the basic methodology of the proposed research focusing on the special combinatorial structure of the arising linear programs. In addition, multivariate Lagrange interpolation and graph theoretical tools will be used and further developed. The linear programs arising in this research area are either of exponential size or numerically unstable. New constraint generation techniques, aggregation and disaggregation procedures, as well as special arithmetic procedures will be used to come up with sharp and efficiently computable bounds.
If successful, the results of this research will lead to new and computationally efficient methods to derive sharp probability bounds. The quality and computational complexity of such bounds is the bottleneck in numerous applications, including communication/transportation/electric network reliability analysis, financial engineering, risk analysis, as well as stochastic optimization problems. In particular, the improved methodology will allow better planning for extreme events in large stochastic networks, such as evaluating emergency evacuation plans in transportation networks, preparing for heat events in electric networks, etc. The proposed work will also contribute to the theory and computational methodology of linear programming.
