On a conservative partition refinement (CPR) method for a class of two-stage stochastic programming problems

Two-stage stochastic programming is a mathematical framework widely used in real-life applications such as power system operation planning, supply chains, logistics, inventory management, and financial planning. Since most of these problems cannot be solved analytically, decision makers make use of numerical methods to obtain a near-optimal solution. Some applications rely on the implementation of non-converged and therefore sub-optimal solutions because of computational time or power limitations. In this context, the existing partition-refinement methods provide an optimistic solution whenever convergence is not attained. Optimistic solutions often generate high disappointment levels because they consistently underestimate the actual costs in the approximate objective function. To address this issue, we developed a conservative convergent partition-refinement method for two-stage stochastic linear programming problems with a convex recourse function of the uncertainty. Given a partition of the uncertainty support, a conservative decision can be obtained by means of a distributionally robust problem whose complexity grows exponentially with the uncertainty dimensionality. We prove the convergence of the method given a refining partition sequence and propose algorithmic schemes to address the problem of dimensionality. For problems with low-dimensional uncertainty, we developed a deterministic equivalent linear programming model; whereas, for medium-sized uncertainty dimensionality, we propose a column and constraint generation algorithm. To handle high dimensional uncertainty, we propose a simplex-based heuristic method whose complexity grows linearly with the uncertainty dimension—size of the random vector. In the presence of monotone recourse functions with regard to an uncertain parameter, we prove convergence of the proposed simplex-based heuristic method. Computational experiments are presented for a farmer’s problem, an aircraft allocation problem, and a Unit Commitment problem.