RCADT - Benders Decomposition Using Graph Modeling and Multi-Parametric Programming

Benders Decomposition Using Graph Modeling and Multi-Parametric Programming

Benders Decomposition, BD, is a widely used method for solving large, structured optimization problems, but its performance is affected by repeated subproblem solving.

A flexible and modular algorithm to accelerate BD is proposed, which will be called BD-GM.

The structure of the problem is expressed by a modeling abstraction in graph theory, in which the nodes represent optimization subproblems and the edges represent the connectivity between subproblems.

A key innovation is that it incorporates Multiparametric Programming substitutes (MP) for subproblems in the nodes, which exactly map the analytical map of the subproblem-solving space.

The use of MP surrogates allows us to replace subproblem solves with fast look-ups and function evaluations, for primal and dual variables during the iterative BD process.

BD-GM is equivalent between the classic BD cuts and those derived from the MP.

https://youtu.be/pN5W1-Inso4

Видео RCADT - Benders Decomposition Using Graph Modeling and Multi-Parametric Programming канала HYPOTHALAMUS Ai