Random Procedures for Nonredundant Constraint Identification in Stochastic Linear Programs

SYNOPTIC ABSTRACT

Many problems involving uncertainty can be formulated as large-scale stochastic linear programs. Standard solution techniques are, however, severely limited by problem size. The programs do, nevertheless, possess special structure that often includes a large proportion of redundant constraints. We present procedures for exploiting this structure by efficiently identifying nonredundant constraints, thereby resulting in a decrease in effective problem size. Our procedures are based on recursively generating random search directions from points within the feasible region.

Key Words and Phrases:

• redundant constraints
• Monte Carlo
• linear programming