Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Standard feasibility cuts for Benders' decomposition.

Author
Stephen J. Maher

Definition in file benderscut_feas.c.

#include "nlpi/exprinterpret.h"
#include "nlpi/pub_expr.h"
#include "scip/benderscut_feas.h"
#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_nlp.h"
#include "scip/pub_var.h"
#include "scip/scip_benders.h"
#include "scip/scip_cons.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_nlp.h"
#include "scip/scip_numerics.h"
#include "scip/scip_prob.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_var.h"

Go to the source code of this file.

Macros

#define BENDERSCUT_NAME   "feas"
 
#define BENDERSCUT_DESC   "Standard feasibility cuts for Benders' decomposition"
 
#define BENDERSCUT_PRIORITY   10000
 
#define BENDERSCUT_LPCUT   TRUE
 

Functions

static SCIP_RETCODE addVariableToArray (SCIP *masterprob, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_VAR *addvar, SCIP_Real addval, int *nvars, int *varssize)
 
static SCIP_RETCODE computeStandardLPFeasibilityCut (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, int *nvars, int *varssize, SCIP_Bool *success)
 
static SCIP_RETCODE computeStandardNLPFeasibilityCut (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_VAR ***vars, SCIP_Real **vals, SCIP_Real *lhs, int *nvars, int *varssize, SCIP_Bool *success)
 
static SCIP_RETCODE generateAndApplyBendersCuts (SCIP *masterprob, SCIP *subproblem, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_RESULT *result)
 
static SCIP_DECL_BENDERSCUTEXEC (benderscutExecFeas)
 
SCIP_RETCODE SCIPincludeBenderscutFeas (SCIP *scip, SCIP_BENDERS *benders)
 

Macro Definition Documentation

◆ BENDERSCUT_NAME

#define BENDERSCUT_NAME   "feas"

Definition at line 49 of file benderscut_feas.c.

Referenced by SCIP_DECL_BENDERSCUTEXEC(), and SCIPincludeBenderscutFeas().

◆ BENDERSCUT_DESC

#define BENDERSCUT_DESC   "Standard feasibility cuts for Benders' decomposition"

Definition at line 50 of file benderscut_feas.c.

Referenced by SCIPincludeBenderscutFeas().

◆ BENDERSCUT_PRIORITY

#define BENDERSCUT_PRIORITY   10000

Definition at line 51 of file benderscut_feas.c.

Referenced by SCIPincludeBenderscutFeas().

◆ BENDERSCUT_LPCUT

#define BENDERSCUT_LPCUT   TRUE

Definition at line 52 of file benderscut_feas.c.

Referenced by SCIPincludeBenderscutFeas().

Function Documentation

◆ addVariableToArray()

static SCIP_RETCODE addVariableToArray ( SCIP masterprob,
SCIP_VAR ***  vars,
SCIP_Real **  vals,
SCIP_VAR addvar,
SCIP_Real  addval,
int *  nvars,
int *  varssize 
)
static

adds a variable and value to the constraint/row arrays

Parameters
masterprobthe SCIP instance of the master problem
varspointer to array of variables in the generated cut with non-zero coefficient
valspointer to array of coefficients of the variables in the generated cut
addvarthe variable that will be added to the array
addvalthe value that will be added to the array
nvarsthe number of variables in the variable array
varssizethe length of the variable size

Definition at line 60 of file benderscut_feas.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBufferArray.

Referenced by computeStandardLPFeasibilityCut(), and computeStandardNLPFeasibilityCut().

◆ computeStandardLPFeasibilityCut()

static SCIP_RETCODE computeStandardLPFeasibilityCut ( SCIP masterprob,
SCIP subproblem,
SCIP_BENDERS benders,
SCIP_VAR ***  vars,
SCIP_Real **  vals,
SCIP_Real lhs,
int *  nvars,
int *  varssize,
SCIP_Bool success 
)
static

computing as standard Benders' feasibility cut from the dual solutions of the LP

Parameters
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the pricing problem
bendersthe benders' decomposition structure
varspointer to array of variables in the generated cut with non-zero coefficient
valspointer to array of coefficients of the variables in the generated cut
lhsthe left hand side of the cut
nvarsthe number of variables in the cut
varssizethe number of variables in the array
successwas the cut generation successful?

Definition at line 96 of file benderscut_feas.c.

References addVariableToArray(), FALSE, NULL, SCIP_CALL, SCIP_LPSOLSTAT_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPgetBendersMasterVar(), SCIPgetLPRows(), SCIPgetLPSolstat(), SCIPgetNLPRows(), SCIPgetNVars(), SCIPgetVarFarkasCoef(), SCIPgetVars(), SCIPisDualfeasZero(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisZero(), SCIProwGetDualfarkas(), SCIProwGetLhs(), SCIProwGetRhs(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by generateAndApplyBendersCuts().

◆ computeStandardNLPFeasibilityCut()

static SCIP_RETCODE computeStandardNLPFeasibilityCut ( SCIP masterprob,
SCIP subproblem,
SCIP_BENDERS benders,
SCIP_VAR ***  vars,
SCIP_Real **  vals,
SCIP_Real lhs,
int *  nvars,
int *  varssize,
SCIP_Bool success 
)
static

computing as standard Benders' feasibility cut from the dual solutions of the NLP

NOTE: The cut must be created before being passed to this function

Parameters
masterprobthe SCIP instance of the master problem
subproblemthe SCIP instance of the pricing problem
bendersthe benders' decomposition structure
varspointer to array of variables in the generated cut with non-zero coefficient
valspointer to array of coefficients of the variables in the generated cut
lhsthe left hand side of the cut
nvarsthe number of variables in the cut
varssizethe number of variables in the array
successwas the cut generation successful?

Definition at line 217 of file benderscut_feas.c.

References addVariableToArray(), FALSE, NULL, SCIP_CALL, SCIP_NLPSOLSTAT_GLOBINFEASIBLE, SCIP_NLPSOLSTAT_LOCINFEASIBLE, SCIP_OKAY, SCIP_Real, SCIPaddNlRowGradientBenderscutOpt(), SCIPblkmem(), SCIPdebugMsg, SCIPexprintCreate(), SCIPexprintFree(), SCIPgetBendersMasterVar(), SCIPgetNLPNlRows(), SCIPgetNLPSolstat(), SCIPgetNLPVars(), SCIPgetNLPVarsLbDualsol(), SCIPgetNLPVarsUbDualsol(), SCIPgetNlRowActivity(), SCIPgetNNLPNlRows(), SCIPgetNNLPVars(), SCIPisInfinity(), SCIPisNLPConstructed(), SCIPisZero(), SCIPnlrowGetDualsol(), SCIPnlrowGetLhs(), SCIPnlrowGetRhs(), SCIPvarGetNLPSol(), and TRUE.

Referenced by generateAndApplyBendersCuts().

◆ generateAndApplyBendersCuts()

static SCIP_RETCODE generateAndApplyBendersCuts ( SCIP masterprob,
SCIP subproblem,
SCIP_BENDERS benders,
SCIP_BENDERSCUT benderscut,
SCIP_SOL sol,
int  probnumber,
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
resultthe result from solving the subproblems

Definition at line 332 of file benderscut_feas.c.

References computeStandardLPFeasibilityCut(), computeStandardNLPFeasibilityCut(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_FULL, SCIPABORT, SCIPaddCons(), SCIPallocClearBufferArray, SCIPbenderscutGetNFound(), SCIPcreateConsBasicLinear(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfreeBufferArray, SCIPgetActivityLinear(), SCIPgetLhsLinear(), SCIPgetNFixedVars(), SCIPgetNLPIterations(), SCIPgetNNlpis(), SCIPgetNVars(), SCIPgetRhsLinear(), SCIPinfinity(), SCIPisGE(), SCIPisInfinity(), SCIPisNLPConstructed(), SCIPreleaseCons(), SCIPsetConsDynamic(), SCIPsetConsRemovable(), SCIPsnprintf(), SCIPverbMessage(), and TRUE.

Referenced by SCIP_DECL_BENDERSCUTEXEC().

◆ SCIP_DECL_BENDERSCUTEXEC()