Name: Andras Prékopa
University: Rutgers Center for Operations Research, University of New Jersey
Date: Friday, April 21, 2006
Time: 1:30 to 3:00 pm
Location: Simon Auditorium
Title of Seminar: On the Relationship Between Probabilistic Constrained Stochastic,
Disjunctive and Miltiobjective Programming
Abstract:
The probabilistic constraint stochastic programming problem can be identified as a special disjunctive programming problem, where, however, the alternative constraints are not given in the same form as the others. The p-efficient points of a multivariate c.d.f. have to be identified and each of them determines an alternative constraint. If the distribution is discrete, then the set of p-efficient points is finite. If it is continuous, then the problem is a semi-infinite disjunctive problem but general theorems ensure the convexity of the set of feasible solutions.
For the discrete case we introduce a multiobjective term into the objective function, by taking the maximum of a finite number of linear functions of a subset of variables, while the entire objective function is to be minimized. Then, if the p-efficient points are known, we convexify the alternative constraints and arrive to a problem such that its dual is of the same type. A duality theorem can be obtained also for the case of a continuous distribution by the use of a limiting procedure or direct reasoning, using nonlinear duality theory.
The numerical solution of problems of this type will be discussed. In both the discrete and continuous distribution cases the duality theorems provide us with the possibility to choose between the primal and dual problems to solve. For the discrete case a cutting plane procedure is available that assumes the knowledge of the p-efficient points. If, however, the components of the random vector in the probabilistic constraint are independent, then a cone generation algorithm creates the p-efficient points and solves the problem simultaneously. For the continuous case a new algorithm is developed, a combination of a cutting plane and a supporting hyperplane algorithms. Its advantage is that in each iteration we obtain lower and upper bounds for the optimum value of the original problem and the difference between the bounds vanishes if we pass to the limit. Below is a list of those papers, that are important sources of information for our theoretical and algorithmic developments.
E. Balas, Disjunctive Programming. Annals of Discrete Math. 5 (1979) 3-51.
E. Balas, Disjunctive programming: Properties of the Convex Hull of Feasible Points.
D. Dentcheva, A. Prékopa, A. Ruszczynski, Concavity and Efficient Points of Discrete
Distributions in Probabilistic Programming. Math. Prog. Ser. A. 89 (2000) 55-77.
L. Khachiyan, E. Boros, K. Elbassioni, V. Gurvich, K. Makino, Dual-Bounded Generating
Problems: Efficient and Inefficient Points for Discrete Probability Distributions and Sparse
Boxes for Multidimensional Data. Discrete Applied Math. To appear.
É. Komáromi, Duality in Probabilistic Constrained Linear Programming. In: Lecture Notes in
Control and Inf. Sci. 84 (1986) 423-429.
A. Prékopa, B. Vízvári, T. Badics, Programming under Probabilistic Constraint with Discrete
Random Variable. New Trends in Math. Prog. (F. Giovannessi et. al. eds.), Kluwer, 1988. 235-255.
A. Prékopa, Stochastic Programming. Kluwer, 1995.
Copies of the paper will be available at the seminar.
