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{array}{ll}
\min & f(x, y) + h0(y) \\
s.t. & g(x, y) <= 0 \\
& h(y) <= 0
\end{array}\]
where y are the complicating variables. Reformulate to
\[\begin{array}{ll}
\min & h0(y) + \eta \\
s.t. & g(x, y) <= 0 \\
& f(x, y) <= \eta \\
& h(y) <= 0
\end{array}\]
Root problem must be of the form
\[\begin{array}{ll}
\min & h0(y) + \eta \\
s.t. & h(y) <= 0 \\
& \{benders\ cuts\}
\end{array}\]
where the last constraint will be generated automatically with
BendersCutGenerators. The BendersCutGenerators must be handed a
subproblem of the form
\[\begin{array}{ll}
\min & f(x, y) \\
s.t. & g(x, y) <= 0
\end{array}\]
except the constraints don’t actually have to be in this form. The
subproblem will automatically be transformed to
\[\begin{array}{lll}
\min & z & \\
s.t. & g(x, y) - z <= 0 & (\alpha) \\
& f(x, y) - \eta - z <= 0 & (\beta) \\
& y - y_k = 0 & (\gamma) \\
& \eta - \eta_k = 0 & (\delta)
\end{array}\]
Classes