Lagrangian cuts generated by batch to efficiently solve two-stage stochastic mixed-integer program
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913213341237248 |
|---|---|
| author | Xiaoyu, Luo Chuanhou, Gao |
| author_facet | Xiaoyu, Luo Chuanhou, Gao |
| contents | We propose to generate Lagrangian cut for two-stage stochastic integer program by batch, in contrast to the existing methods which solve each Lagrangian subproblem at every iteration. We establish two convergence properties of the proposed algorithm. Then we demonstrate that the improvement in the lower bound achieved by incorporating the Lagrangian cut adheres to the `triangle inequality', thereby showcasing the superiority of our proposed method over existing approaches. Moreover, we suggest acquiring Lagrangian cuts for unresolved scenarios by averaging the coefficients of the acquired Lagrangian cuts, ensuring the quality of this cut with a certain probability. Computational study demonstrates that our proposed algorithm can significantly improve the lower bound of the linear relaxation of the Bender master problem more quickly with much fewer Lagrangian cuts. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15901 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lagrangian cuts generated by batch to efficiently solve two-stage stochastic mixed-integer program Xiaoyu, Luo Chuanhou, Gao Optimization and Control 90C06, 90C11, 90C15 We propose to generate Lagrangian cut for two-stage stochastic integer program by batch, in contrast to the existing methods which solve each Lagrangian subproblem at every iteration. We establish two convergence properties of the proposed algorithm. Then we demonstrate that the improvement in the lower bound achieved by incorporating the Lagrangian cut adheres to the `triangle inequality', thereby showcasing the superiority of our proposed method over existing approaches. Moreover, we suggest acquiring Lagrangian cuts for unresolved scenarios by averaging the coefficients of the acquired Lagrangian cuts, ensuring the quality of this cut with a certain probability. Computational study demonstrates that our proposed algorithm can significantly improve the lower bound of the linear relaxation of the Bender master problem more quickly with much fewer Lagrangian cuts. |
| title | Lagrangian cuts generated by batch to efficiently solve two-stage stochastic mixed-integer program |
| topic | Optimization and Control 90C06, 90C11, 90C15 |
| url | https://arxiv.org/abs/2401.15901 |