benders_cuts
General purpose Benders Cut Generator.
It is easier to understand this code after reading Grothey, Leyffer, and McKinnon “A note on feasibility in Benders Decomposition” [GLM99]
Original problem:
\[\begin{split}\min\ & f(x, y) + h0(y) \\
s.t.\ & g(x, y) <= 0 \\
& h(y) <= 0\end{split}\]
where y are the complicating variables. Reformulate to
\[\begin{split}\min\ & h0(y) + \eta \\
s.t.\ & g(x, y) <= 0 \\
& f(x, y) <= \eta \\
& h(y) <= 0\end{split}\]
Root problem must be of the form
\[\begin{split}\min\ & h0(y) + \eta \\
s.t.\ & h(y) <= 0 \\
& benders\ cuts\end{split}\]
where the last constraint will be generated automatically with BendersCutGenerators. The BendersCutGenerators must be handed a subproblem of the form
\[\begin{split}\min\ & f(x, y) \\
s.t.\ & g(x, y) <= 0\end{split}\]
except the constraints don’t actually have to be in this form. The subproblem will automatically be transformed to
\[\begin{split}\min\ & _z & \\
s.t.\ & g(x, y) - z <= 0 & \quad (\alpha) \\
& f(x, y) - \eta - z <= 0 & \quad (\beta) \\
& y - y_k = 0 & \quad (\gamma) \\
& \eta - \eta_k = 0 & \quad (\delta) \\\end{split}\]
Classes
|
|
|
|
|
|
|