-

 

 

 




Optimization Online





 

A conservative convergent solution for continuously distributed two-stage stochastic optimization problems

Carlos Gamboa (caagamboaro***at***unal.edu.co)
Davi Valladão (davimv***at***puc-rio.br)
Alexandre Street (street***at***ele.puc-rio.br)

Abstract: 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 applica- tions 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 solu- tions often generate high disappointment levels because they consistently underestimate the actual costs in the approximate objective function. To address this issue, we developed a con- servative 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 con- vergence 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. 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 and an aircraft allocation problem.

Keywords: two-stage stochastic programming, exact bound partition methods, conservative solution

Category 1: Stochastic Programming

Citation:

Download: [PDF]

Entry Submitted: 07/29/2019
Entry Accepted: 07/30/2019
Entry Last Modified: 10/28/2019

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society