Benders Decomposition using Graph Modeling and Multi-Parametric Programming
Parth Brahmbhatt, David L. Cole, Victor M. Zavala, Styliani Avraamidou · 2025
Read Benders Decomposition using Graph Modeling and Multi-Parametric Programming by Parth Brahmbhatt, David L. Cole, Victor M. Zavala, Styliani Avraamidou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-01100.txt.
Description
Splitting a huge optimization problem into a master problem and smaller subproblems is the idea behind Benders decomposition. A master proposes, the smaller problems critique, and the loop repeats — but solving them again and again is the bottleneck. Parth Brahmbhatt, David Cole, Victor Zavala, and Styliani Avraamidou propose in 2025 to solve each one once, in advance. Their tool is multi-parametric programming, which yields explicit formulas mapping inputs to optimal decisions.
Built on graph modeling software, the framework swaps repeated solves for quick lookups during the loop. The authors prove the resulting cuts match the classical ones. On a two-stage planning problem — expanding capacity under uncertain demand, prices, and raw material supply — the approach cut solve time sharply while keeping its convergence guarantees. The formulas also make solutions easier to inspect. The software is open source.
Catalog record
| CREATOR | Parth Brahmbhatt, David L. Cole, Victor M. Zavala, Styliani Avraamidou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-01100