Column generation for multistage stochastic mixed-integer nonlinear programs with discrete state variables
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929748012171264 |
|---|---|
| author | Rathi, Tushar Riley, Benjamin P. Flores-Quiroz, Angela Zhang, Qi |
| author_facet | Rathi, Tushar Riley, Benjamin P. Flores-Quiroz, Angela Zhang, Qi |
| contents | Stochastic programming provides a natural framework for modeling sequential optimization problems under uncertainty; however, the efficient solution of large-scale multistage stochastic programs remains a challenge, especially in the presence of discrete decisions and nonlinearities. In this work, we consider multistage stochastic mixed-integer nonlinear programs (MINLPs) with discrete state variables, which exhibit a decomposable structure that allows its solution using a column generation approach. Following a Dantzig-Wolfe reformulation, we apply column generation such that each pricing subproblem is an MINLP of much smaller size, making it more amenable to global MINLP solvers. We further propose a method for generating additional columns that satisfy the nonanticipativity constraints, leading to significantly improved convergence and optimal or near-optimal solutions for many large-scale instances in a reasonable computation time. The effectiveness of the tailored column generation algorithm is demonstrated via computational case studies on a multistage blending problem and a problem involving the routing of mobile generators in a power distribution network. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05052 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Column generation for multistage stochastic mixed-integer nonlinear programs with discrete state variables Rathi, Tushar Riley, Benjamin P. Flores-Quiroz, Angela Zhang, Qi Optimization and Control Stochastic programming provides a natural framework for modeling sequential optimization problems under uncertainty; however, the efficient solution of large-scale multistage stochastic programs remains a challenge, especially in the presence of discrete decisions and nonlinearities. In this work, we consider multistage stochastic mixed-integer nonlinear programs (MINLPs) with discrete state variables, which exhibit a decomposable structure that allows its solution using a column generation approach. Following a Dantzig-Wolfe reformulation, we apply column generation such that each pricing subproblem is an MINLP of much smaller size, making it more amenable to global MINLP solvers. We further propose a method for generating additional columns that satisfy the nonanticipativity constraints, leading to significantly improved convergence and optimal or near-optimal solutions for many large-scale instances in a reasonable computation time. The effectiveness of the tailored column generation algorithm is demonstrated via computational case studies on a multistage blending problem and a problem involving the routing of mobile generators in a power distribution network. |
| title | Column generation for multistage stochastic mixed-integer nonlinear programs with discrete state variables |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2406.05052 |