Benders playgroundLaboratorio di Benders

A two-stage problem with three scenarios: the first-stage variable \(y\), and in each scenario a recourse LP whose dual polygon is the same for all of them. The expected recourse is convex and piecewise linear, one piece per vertex of that polygon, and every Benders cut is a vertex, chosen by the direction \(h - T y\) of the scenario. The master takes either a single cut or one cut per scenario, with or without a trust region, as in BendersDecompositionSolver of SMS++.

Un problema a due stadi con tre scenari: la variabile di primo stadio \(y\), e in ogni scenario un LP di ricorso il cui poligono duale è lo stesso per tutti. Il ricorso atteso è convesso e lineare a tratti, un tratto per vertice di quel poligono, e ogni taglio di Benders è un vertice, scelto dalla direzione \(h - T y\) dello scenario. Il master riceve un solo taglio o un taglio per scenario, con o senza una regione di fiducia, come in BendersDecompositionSolver di SMS++.

The master: the true objective \(c\,y + \mathbb{E}[Q(y)]\) (dashed), the model of the cuts (violet), the iterates, the trust region and its center.Il problema master: il vero obiettivo \(c\,y + \mathbb{E}[Q(y)]\) (tratteggiato), il modello dei tagli (viola), gli iterati, la regione di fiducia e il suo centro.
upper boundlimitazione superiore
lower boundlimitazione inferiore
cutstagli
The dual polygon of the recourse: each ring is a vertex used as a cut by a scenario (violet, gold, teal; bright at the last iteration), the arrows the directions \(h - T y\) at the last \(y\).Il poligono duale del ricorso: ogni anello è un vertice usato come taglio da uno scenario (viola, oro, verde acqua; acceso all'ultima iterazione), le frecce le direzioni \(h - T y\) all'ultimo \(y\).