SCIP
Solving Constraint Integer Programs
Detailed Description
Generates a standard Benders' decomposition optimality cut.
Definition in file benderscut_opt.c.
#include "scip/benderscut_opt.h"#include "scip/cons_linear.h"#include "scip/pub_benderscut.h"#include "scip/pub_benders.h"#include "scip/pub_lp.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_misc_linear.h"#include "scip/pub_var.h"#include "scip/scip_benders.h"#include "scip/scip_cons.h"#include "scip/scip_cut.h"#include "scip/scip_general.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_prob.h"#include "scip/scip_probing.h"#include "scip/scip_var.h"#include <string.h>Go to the source code of this file.
Macros | |
| #define | BENDERSCUT_NAME "optimality" |
| #define | BENDERSCUT_DESC "Standard Benders' decomposition optimality cut" |
| #define | BENDERSCUT_PRIORITY 5000 |
| #define | BENDERSCUT_LPCUT TRUE |
| #define | SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */ |
Functions | |
| static SCIP_RETCODE | polishSolution (SCIP *subproblem, SCIP_Bool *success) |
| static SCIP_RETCODE | computeStandardOptimalityCut (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real *lhs, SCIP_Real *rhs, int *nvars, SCIP_Real *checkobj, SCIP_Bool *success) |
| static SCIP_RETCODE | addAuxiliaryVariableToCut (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_VAR **vars, SCIP_Real *vals, int *nvars, int probnumber) |
| static SCIP_RETCODE | generateAndApplyBendersCuts (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result) |
| static | SCIP_DECL_BENDERSCUTFREE (benderscutFreeOpt) |
| static | SCIP_DECL_BENDERSCUTEXEC (benderscutExecOpt) |
| SCIP_RETCODE | SCIPincludeBenderscutOpt (SCIP *scip, SCIP_BENDERS *benders) |
Macro Definition Documentation
◆ BENDERSCUT_NAME
| #define BENDERSCUT_NAME "optimality" |
Definition at line 46 of file benderscut_opt.c.
Referenced by SCIP_DECL_BENDERSCUTFREE(), and SCIPincludeBenderscutOpt().
◆ BENDERSCUT_DESC
| #define BENDERSCUT_DESC "Standard Benders' decomposition optimality cut" |
Definition at line 47 of file benderscut_opt.c.
Referenced by SCIPincludeBenderscutOpt().
◆ BENDERSCUT_PRIORITY
| #define BENDERSCUT_PRIORITY 5000 |
Definition at line 48 of file benderscut_opt.c.
Referenced by SCIPincludeBenderscutOpt().
◆ BENDERSCUT_LPCUT
| #define BENDERSCUT_LPCUT TRUE |
Definition at line 49 of file benderscut_opt.c.
Referenced by SCIPincludeBenderscutOpt().
◆ SCIP_DEFAULT_ADDCUTS
| #define SCIP_DEFAULT_ADDCUTS FALSE /** Should cuts be generated, instead of constraints */ |
Definition at line 51 of file benderscut_opt.c.
Referenced by SCIPincludeBenderscutOpt().
Function Documentation
◆ polishSolution()
|
static |
in the case of numerical troubles, the LP is resolved with solution polishing activated
- Parameters
-
subproblem the SCIP data structure success TRUE is the resolving of the LP was successful
Definition at line 70 of file benderscut_opt.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIPgetIntParam(), SCIPgetLPSolstat(), SCIPinProbing(), SCIPsetIntParam(), SCIPsolveProbingLP(), and TRUE.
Referenced by SCIP_DECL_BENDERSCUTEXEC().
◆ computeStandardOptimalityCut()
|
static |
computes a standard Benders' optimality cut from the dual solutions of the LP
- Parameters
-
masterprob the SCIP instance of the master problem subproblem the SCIP instance of the subproblem benders the benders' decomposition structure vars the variables in the generated cut with non-zero coefficient vals the coefficients of the variables in the generated cut lhs the left hand side of the cut rhs the right hand side of the cut nvars the number of variables in the cut checkobj stores the objective function computed from the dual solution success was the cut generation successful?
Definition at line 102 of file benderscut_opt.c.
References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetDualsol(), SCIPconsGetLhs(), SCIPconsGetRhs(), SCIPdebugMsg, SCIPgetBendersMasterVar(), SCIPgetConss(), SCIPgetFixedVars(), SCIPgetNConss(), SCIPgetNFixedVars(), SCIPgetNVars(), SCIPgetVarRedcost(), SCIPgetVars(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetObj(), SCIPvarGetSol(), SCIPvarGetUbLocal(), SCIPvarGetUnchangedObj(), and TRUE.
Referenced by generateAndApplyBendersCuts().
◆ addAuxiliaryVariableToCut()
|
static |
Adds the auxiliary variable to the generated cut. If this is the first optimality cut for the subproblem, then the auxiliary variable is first created and added to the master problem.
- Parameters
-
masterprob the SCIP instance of the master problem benders the benders' decomposition structure vars the variables in the generated cut with non-zero coefficient vals the coefficients of the variables in the generated cut nvars the number of variables in the cut probnumber the number of the pricing problem
Definition at line 263 of file benderscut_opt.c.
References NULL, SCIP_OKAY, and SCIPbendersGetAuxiliaryVar().
Referenced by generateAndApplyBendersCuts().
◆ generateAndApplyBendersCuts()
|
static |
generates and applies Benders' cuts
- Parameters
-
masterprob the SCIP instance of the master problem subproblem the SCIP instance of the pricing problem benders the benders' decomposition benderscut the benders' decomposition cut method sol primal CIP solution probnumber the number of the pricing problem type the enforcement type calling this function result the result from solving the subproblems
Definition at line 291 of file benderscut_opt.c.
References addAuxiliaryVariableToCut(), computeStandardOptimalityCut(), FALSE, NULL, SCIP_BENDERSENFOTYPE_CHECK, SCIP_BENDERSENFOTYPE_LP, SCIP_BENDERSENFOTYPE_PSEUDO, SCIP_BENDERSENFOTYPE_RELAX, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_STAGE_INITSOLVE, SCIP_STATUS_OPTIMAL, SCIPABORT, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarsToRow(), SCIPaddVarToRow(), SCIPallocClearBufferArray, SCIPbenderscutGetData(), SCIPbenderscutGetNFound(), SCIPcheckBendersSubproblemOptimality(), SCIPcreateConsBasicLinear(), SCIPcreateEmptyRowCons(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetActivityLinear(), SCIPgetLhsLinear(), SCIPgetLPSolstat(), SCIPgetNFixedVars(), SCIPgetNVars(), SCIPgetRowSolActivity(), SCIPgetStage(), SCIPgetStatus(), SCIPinfinity(), SCIPisFeasEQ(), SCIPreleaseCons(), SCIPreleaseRow(), SCIProwGetLhs(), SCIPsetConsDynamic(), SCIPsetConsRemovable(), SCIPsnprintf(), SCIPstoreBenderscutCut(), and TRUE.
Referenced by SCIP_DECL_BENDERSCUTEXEC().
◆ SCIP_DECL_BENDERSCUTFREE()
|
static |
destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting)
Definition at line 486 of file benderscut_opt.c.
References BENDERSCUT_NAME, NULL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPbenderscutGetName(), SCIPbenderscutSetData(), and SCIPfreeBlockMemory.
◆ SCIP_DECL_BENDERSCUTEXEC()
|
static |
execution method of Benders' decomposition cuts
Definition at line 507 of file benderscut_opt.c.
References generateAndApplyBendersCuts(), NULL, polishSolution(), SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIP_STATUS_OPTIMAL, SCIPbendersGetNSubproblems(), SCIPbendersSubproblem(), SCIPgetLPSolstat(), SCIPgetStage(), SCIPgetStatus(), and SCIPinfoMessage().