Bi-Parameterized Two-Stage Stochastic Min-Max and Min-Min Mixed Integer Programs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912674449719296 |
|---|---|
| author | Kang, Sumin Bansal, Manish |
| author_facet | Kang, Sumin Bansal, Manish |
| contents | We introduce two-stage stochastic min-max and min-min integer programs with bi-parameterized recourse (BTSPs), where the first-stage decisions affect both the objective function and the feasible region of the second-stage problem. To solve these programs efficiently, we introduce Lagrangian-integrated $L$-shaped ($L^2$) methods, which guarantee exact solutions when the first-stage decisions are pure binary. For mixed-binary first-stage programs, we present a regularization-augmented variant of this method. Our computational results for a stochastic network interdiction problem show that the $L^2$ method outperforms a benchmark method, solving all instances in 23 seconds on average, while the benchmark method failed to solve any instance within 3600 seconds. The $L^2$ method also achieves optimal solutions, on average, 18.4 times faster for a stochastic facility location problem. Furthermore, we show that the $L^2$ method can effectively address distributionally robust optimization problems with decision-dependent ambiguity sets that may be empty for some first-stage decisions, achieving optimal solutions, on average, 5.3 times faster than existing methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_01081 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bi-Parameterized Two-Stage Stochastic Min-Max and Min-Min Mixed Integer Programs Kang, Sumin Bansal, Manish Optimization and Control 90C11, 90C15 We introduce two-stage stochastic min-max and min-min integer programs with bi-parameterized recourse (BTSPs), where the first-stage decisions affect both the objective function and the feasible region of the second-stage problem. To solve these programs efficiently, we introduce Lagrangian-integrated $L$-shaped ($L^2$) methods, which guarantee exact solutions when the first-stage decisions are pure binary. For mixed-binary first-stage programs, we present a regularization-augmented variant of this method. Our computational results for a stochastic network interdiction problem show that the $L^2$ method outperforms a benchmark method, solving all instances in 23 seconds on average, while the benchmark method failed to solve any instance within 3600 seconds. The $L^2$ method also achieves optimal solutions, on average, 18.4 times faster for a stochastic facility location problem. Furthermore, we show that the $L^2$ method can effectively address distributionally robust optimization problems with decision-dependent ambiguity sets that may be empty for some first-stage decisions, achieving optimal solutions, on average, 5.3 times faster than existing methods. |
| title | Bi-Parameterized Two-Stage Stochastic Min-Max and Min-Min Mixed Integer Programs |
| topic | Optimization and Control 90C11, 90C15 |
| url | https://arxiv.org/abs/2501.01081 |