A Successive Refinement for Solving Stochastic Programs with Decision-Dependent Random Capacities
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910602071375872 |
|---|---|
| author | Medal, Hugh Affar, Samuel |
| author_facet | Medal, Hugh Affar, Samuel |
| contents | We study a class of two-stage stochastic programs in which the second stage includes a set of components with uncertain capacity, and the expression for the distribution function of the uncertain capacity includes first-stage variables. Thus, this class of problems has the characteristics of a stochastic program with decision-dependent uncertainty. A natural way to formulate this class of problems is to enumerate the scenarios and express the probability of each scenario as a product of the first-stage decision variables; unfortunately, this formulation results in an intractable model with a large number of variable products with high-degree. After identifying structural results related to upper and lower bounds and how to improve these bounds, we present a successive refinement algorithm that successively and dynamically tightens these bounds. Implementing the algorithm within a branch-and-cut method, we report the results of computational experiments that indicate that the successive refinement algorithm significantly outperforms a benchmark approach. Specifically, results show that the algorithm finds an optimal solution before the refined state space become too large. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08403 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Successive Refinement for Solving Stochastic Programs with Decision-Dependent Random Capacities Medal, Hugh Affar, Samuel Optimization and Control 90B08, 90B10, 90C08, 90C10 We study a class of two-stage stochastic programs in which the second stage includes a set of components with uncertain capacity, and the expression for the distribution function of the uncertain capacity includes first-stage variables. Thus, this class of problems has the characteristics of a stochastic program with decision-dependent uncertainty. A natural way to formulate this class of problems is to enumerate the scenarios and express the probability of each scenario as a product of the first-stage decision variables; unfortunately, this formulation results in an intractable model with a large number of variable products with high-degree. After identifying structural results related to upper and lower bounds and how to improve these bounds, we present a successive refinement algorithm that successively and dynamically tightens these bounds. Implementing the algorithm within a branch-and-cut method, we report the results of computational experiments that indicate that the successive refinement algorithm significantly outperforms a benchmark approach. Specifically, results show that the algorithm finds an optimal solution before the refined state space become too large. |
| title | A Successive Refinement for Solving Stochastic Programs with Decision-Dependent Random Capacities |
| topic | Optimization and Control 90B08, 90B10, 90C08, 90C10 |
| url | https://arxiv.org/abs/2409.08403 |