  # SCIP

Solving Constraint Integer Programs

benderscut_opt.h File Reference

## Detailed Description

Generates a standard Benders' decomposition optimality cut.

The classical Benders' decomposition optimality cuts arise from a feasible instance of the Benders' decomposition subproblem. The optimality cuts are an underestimator of the subproblem objective function value. Auxiliary variables, $$\varphi$$ are added to the master problem as a lower bound on the subproblem objective function value.

Consider a linear Benders' decomposition subproblem that takes the master problem solution $$\bar{x}$$ as input:

$z(\bar{x}) = \min\{d^{T}y : Ty \geq h - H\bar{x}, y \geq 0\}$

If the subproblem is feasible, and $$z(\bar{x}) > \varphi$$ (indicating that the current underestimators are not optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the subproblem. Let $$w$$ be the vector corresponding to the optimal dual solution of the Benders' decomposition subproblem. The resulting cut is:

$\varphi \geq w^{T}(h - Hx)$

Next, consider a nonlinear Benders' decomposition subproblem that takes the master problem solution $$\bar{x}$$ as input:

$z(\bar{x}) = \min\{d^{T}y : g(\bar{x},y) \leq 0, y \geq 0\}$

If the subproblem is feasible, and $$z(\bar{x}) > \varphi$$ (indicating that the current underestimators are not optimal) then the Benders' decomposition optimality cut can be generated from the optimal dual solution of the subproblem. Let $$w$$ be the vector corresponding to the optimal dual solution of the Benders' decomposition subproblem. The resulting cut is:

$\varphi \geq z(\bar{x}) + w^{T} \nabla_x g(\bar{x}, y) (x-\bar{x})$

Definition in file benderscut_opt.h.

#include "scip/def.h"
#include "scip/type_benders.h"
#include "scip/type_benderscut.h"
#include "scip/type_cons.h"
#include "scip/type_lp.h"
#include "scip/type_misc.h"
#include "scip/type_nlp.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "nlpi/type_exprinterpret.h"

Go to the source code of this file.

## Functions

SCIP_EXPORT SCIP_RETCODE SCIPincludeBenderscutOpt (SCIP *scip, SCIP_BENDERS *benders)

SCIP_EXPORT SCIP_RETCODE SCIPgenerateAndApplyBendersOptCut (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, char *cutname, SCIP_Real objective, SCIP_Real *primalvals, SCIP_Real *consdualvals, SCIP_Real *varlbdualvals, SCIP_Real *varubdualvals, SCIP_HASHMAP *row2idx, SCIP_HASHMAP *var2idx, SCIP_BENDERSENFOTYPE type, SCIP_Bool addcut, SCIP_Bool feasibilitycut, SCIP_RESULT *result)

SCIP_EXPORT SCIP_RETCODE SCIPaddNlRowGradientBenderscutOpt (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_NLROW *nlrow, SCIP_EXPRINT *exprint, SCIP_Real mult, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx, SCIP_Real *dirderiv, SCIP_VAR ***vars, SCIP_Real **vals, int *nvars, int *varssize)