Processing math: 100%
Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Generates a standard Benders' decomposition optimality cut.

Author
Stephen J. Maher

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 "scip/type_exprinterpret.h"

Go to the source code of this file.

Functions

SCIP_RETCODE SCIPincludeBenderscutOpt (SCIP *scip, SCIP_BENDERS *benders)
 
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_RETCODE SCIPaddNlRowGradientBenderscutOpt (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_NLROW *nlrow, SCIP_Real mult, SCIP_Real *primalvals, SCIP_HASHMAP *var2idx, SCIP_Real *dirderiv, SCIP_VAR ***vars, SCIP_Real **vals, int *nvars, int *varssize)