Constrained Generalized Medians and Hypermedians as Deterministic Equivalents for Two-Stage Linear Programs under Uncertainty

Abstract

In linear programming under uncertainty the two-stage problem is handled by assuming that one chooses a first set of constrained decision variables; this is followed by observations of certain random variables after which another set of decisions must be made to adjust for any constraint violations. The objective is to optimize an expected value functional defined relative to the indicated choices. This paper shows how such problems may always be replaced with either constrained generalized medians or hypermedians in which all random elements appear only in the functional. The resulting problem is called a deterministic equivalent for the original problem since (a) the originally defined objective replaces all random variables by corresponding expected values and (b) the remaining constraints do not contain any random terms. Significant classes of cases are singled out and special attention is devoted to the structure of the constraint matrices for these purposes. Numerical examples are supplied and related to the previous literature. Other properties of these models are also examined and related to types of problems which are often of interest. For instance the hypermedian and generalized median formulations involve minimizations over absolute value terms in the functional. These, in turn, are developed for their possible pertinence in problems where minimizations are to be over the maximum of a set of functions under inequality constraints. Utilizing Moore-Penrose (generalized) inverses, other characterizations are also secured in which all relevant weights and coefficients are stated explicitly in terms of original data.