Scippy

SCIP

Solving Constraint Integer Programs

benderscut_opt.c File Reference

Detailed Description

Generates a standard Benders' decomposition optimality cut.

Author
Stephen J. Maher

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 SCIP_RETCODE polishSolution ( SCIP subproblem,
SCIP_Bool success 
)
static

in the case of numerical troubles, the LP is resolved with solution polishing activated

Parameters
subproblemthe SCIP data structure
successTRUE 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 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

computes a standard Benders' optimality cut from the dual solutions of the LP

Parameters
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the subproblem
bendersthe benders' decomposition structure
varsthe variables in the generated cut with non-zero coefficient
valsthe coefficients of the variables in the generated cut
lhsthe left hand side of the cut
rhsthe right hand side of the cut
nvarsthe number of variables in the cut
checkobjstores the objective function computed from the dual solution
successwas 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 SCIP_RETCODE addAuxiliaryVariableToCut ( SCIP masterprob,
SCIP_BENDERS benders,
SCIP_VAR **  vars,
SCIP_Real vals,
int *  nvars,
int  probnumber 
)
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
masterprobthe SCIP instance of the master problem
bendersthe benders' decomposition structure
varsthe variables in the generated cut with non-zero coefficient
valsthe coefficients of the variables in the generated cut
nvarsthe number of variables in the cut
probnumberthe 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 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

generates and applies Benders' cuts

Parameters
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the pricing problem
bendersthe benders' decomposition
benderscutthe benders' decomposition cut method
solprimal CIP solution
probnumberthe number of the pricing problem
typethe enforcement type calling this function
resultthe 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 SCIP_DECL_BENDERSCUTFREE ( benderscutFreeOpt  )
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()