Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

Generates a Laporte and Louveaux Benders' decomposition integer cut.

Author
Stephen J. Maher

Definition in file benderscut_int.c.

#include "scip/benderscut_int.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_paramset.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_sol.h"
#include <string.h>

Go to the source code of this file.

Macros

#define BENDERSCUT_NAME   "integer"
 
#define BENDERSCUT_DESC   "Laporte and Louveaux Benders' decomposition integer cut"
 
#define BENDERSCUT_PRIORITY   0
 
#define BENDERSCUT_LPCUT   FALSE
 
#define SCIP_DEFAULT_ADDCUTS   FALSE /** Should cuts be generated, instead of constraints */
 
#define SCIP_DEFAULT_CUTCONSTANT   -10000.0
 

Functions

static SCIP_DECL_PARAMCHGD (paramChgdBenderscutintConstant)
 
static SCIP_RETCODE createBenderscutData (SCIP *scip, SCIP_BENDERSCUTDATA *benderscutdata)
 
static void updateSubproblemCutConstant (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUTDATA *benderscutdata, int probnumber)
 
static SCIP_RETCODE computeStandardIntegerOptCut (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_SOL *sol, SCIP_CONS *cons, SCIP_ROW *row, SCIP_Real cutconstant, int probnumber, SCIP_Bool addcut, SCIP_Bool *success)
 
static SCIP_RETCODE addAuxiliaryVariableToCut (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_CONS *cons, SCIP_ROW *row, int probnumber, SCIP_Bool addcut)
 
static SCIP_RETCODE generateAndApplyBendersIntegerCuts (SCIP *masterprob, SCIP_BENDERS *benders, SCIP_BENDERSCUT *benderscut, SCIP_SOL *sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result, SCIP_Bool initcons)
 
static SCIP_DECL_BENDERSCUTFREE (benderscutFreeInt)
 
static SCIP_DECL_BENDERSCUTINIT (benderscutInitInt)
 
static SCIP_DECL_BENDERSCUTEXIT (benderscutExitInt)
 
static SCIP_DECL_BENDERSCUTEXEC (benderscutExecInt)
 
SCIP_RETCODE SCIPincludeBenderscutInt (SCIP *scip, SCIP_BENDERS *benders)
 

Macro Definition Documentation

◆ BENDERSCUT_NAME

◆ BENDERSCUT_DESC

#define BENDERSCUT_DESC   "Laporte and Louveaux Benders' decomposition integer cut"

Definition at line 56 of file benderscut_int.c.

Referenced by SCIPincludeBenderscutInt().

◆ BENDERSCUT_PRIORITY

#define BENDERSCUT_PRIORITY   0

Definition at line 57 of file benderscut_int.c.

Referenced by SCIPincludeBenderscutInt().

◆ BENDERSCUT_LPCUT

#define BENDERSCUT_LPCUT   FALSE

Definition at line 58 of file benderscut_int.c.

Referenced by SCIPincludeBenderscutInt().

◆ SCIP_DEFAULT_ADDCUTS

#define SCIP_DEFAULT_ADDCUTS   FALSE /** Should cuts be generated, instead of constraints */

Definition at line 60 of file benderscut_int.c.

Referenced by SCIPincludeBenderscutInt().

◆ SCIP_DEFAULT_CUTCONSTANT

#define SCIP_DEFAULT_CUTCONSTANT   -10000.0

Definition at line 61 of file benderscut_int.c.

Referenced by SCIPincludeBenderscutInt().

Function Documentation

◆ SCIP_DECL_PARAMCHGD()

static SCIP_DECL_PARAMCHGD ( paramChgdBenderscutintConstant  )
static

method to call, when the priority of a Benders' decomposition was changed

Definition at line 80 of file benderscut_int.c.

References NULL, SCIP_OKAY, and SCIPparamGetData().

◆ createBenderscutData()

static SCIP_RETCODE createBenderscutData ( SCIP scip,
SCIP_BENDERSCUTDATA benderscutdata 
)
static

creates the Benders' decomposition cut data

Parameters
scipthe SCIP data structure
benderscutdatathe Benders' cut data

Definition at line 97 of file benderscut_int.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and TRUE.

Referenced by SCIP_DECL_BENDERSCUTINIT().

◆ updateSubproblemCutConstant()

static void updateSubproblemCutConstant ( SCIP masterprob,
SCIP_BENDERS benders,
SCIP_BENDERSCUTDATA benderscutdata,
int  probnumber 
)
static

updates the cut constant for the given subproblem based upon the global bounds of the associated auxiliary variable

Parameters
masterprobthe SCIP instance of the master problem
bendersthe benders' decomposition structure
benderscutdatathe Benders' decomposition cut data
probnumberthe index for the subproblem

Definition at line 126 of file benderscut_int.c.

References NULL, SCIPbendersGetAuxiliaryVar(), SCIPbendersGetSubproblemLowerbound(), SCIPisGT(), SCIPvarGetLbGlobal(), and TRUE.

Referenced by generateAndApplyBendersIntegerCuts().

◆ computeStandardIntegerOptCut()

static SCIP_RETCODE computeStandardIntegerOptCut ( SCIP masterprob,
SCIP_BENDERS benders,
SCIP_SOL sol,
SCIP_CONS cons,
SCIP_ROW row,
SCIP_Real  cutconstant,
int  probnumber,
SCIP_Bool  addcut,
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
bendersthe benders' decomposition structure
solprimal CIP solution
consthe constraint for the generated cut, can be NULL
rowthe row for the generated cut, can be NULL
cutconstantthe constant value in the integer optimality cut
probnumberthe number of the pricing problem
addcutindicates whether a cut is created instead of a constraint
successwas the cut generation successful?

Definition at line 158 of file benderscut_int.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCoefLinear(), SCIPaddVarToRow(), SCIPbendersGetSubproblemObjval(), SCIPbendersSubproblem(), SCIPchgLhsLinear(), SCIPchgRowLhs(), SCIPdebug, SCIPdebugMsg, SCIPgetActivityLinear(), SCIPgetBendersSubproblemVar(), SCIPgetBestSol(), SCIPgetLhsLinear(), SCIPgetNVars(), SCIPgetObjsense(), SCIPgetRowSolActivity(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPgetVars(), SCIPisFeasEQ(), SCIPisInfinity(), SCIProwGetLhs(), and TRUE.

Referenced by generateAndApplyBendersIntegerCuts().

◆ addAuxiliaryVariableToCut()

static SCIP_RETCODE addAuxiliaryVariableToCut ( SCIP masterprob,
SCIP_BENDERS benders,
SCIP_CONS cons,
SCIP_ROW row,
int  probnumber,
SCIP_Bool  addcut 
)
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
consthe constraint for the generated cut, can be NULL
rowthe row for the generated cut, can be NULL
probnumberthe number of the pricing problem
addcutindicates whether a cut is created instead of a constraint

Definition at line 283 of file benderscut_int.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPaddCoefLinear(), SCIPaddVarToRow(), and SCIPbendersGetAuxiliaryVar().

Referenced by generateAndApplyBendersIntegerCuts().

◆ generateAndApplyBendersIntegerCuts()

static SCIP_RETCODE generateAndApplyBendersIntegerCuts ( SCIP masterprob,
SCIP_BENDERS benders,
SCIP_BENDERSCUT benderscut,
SCIP_SOL sol,
int  probnumber,
SCIP_BENDERSENFOTYPE  type,
SCIP_RESULT result,
SCIP_Bool  initcons 
)
static

generates and applies Benders' cuts

Parameters
masterprobthe SCIP instance of the master 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
initconsis this function called to generate the initial constraint

Definition at line 317 of file benderscut_int.c.

References addAuxiliaryVariableToCut(), BENDERSCUT_NAME, computeStandardIntegerOptCut(), 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_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_STAGE_INITSOLVE, SCIPaddCons(), SCIPaddPoolCut(), SCIPaddRow(), SCIPbenderscutGetData(), SCIPbenderscutGetNFound(), SCIPbendersGetAuxiliaryVar(), SCIPcheckBendersSubproblemOptimality(), SCIPchgLhsLinear(), SCIPchgRowLhs(), SCIPcreateConsBasicLinear(), SCIPcreateEmptyRowConshdlr(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPfindConshdlr(), SCIPgetLhsLinear(), SCIPgetObjsense(), SCIPgetSolOrigObj(), SCIPgetStage(), SCIPinfinity(), SCIPinfoMessage(), SCIPisInfinity(), SCIPprintRow(), SCIPreleaseCons(), SCIPreleaseRow(), SCIProwGetLhs(), SCIPsetConsDynamic(), SCIPsetConsRemovable(), SCIPsnprintf(), SCIPvarGetLbGlobal(), TRUE, and updateSubproblemCutConstant().

Referenced by SCIP_DECL_BENDERSCUTEXEC().

◆ SCIP_DECL_BENDERSCUTFREE()

static SCIP_DECL_BENDERSCUTFREE ( benderscutFreeInt  )
static

destructor of Benders' decomposition cuts to free user data (called when SCIP is exiting)

Definition at line 508 of file benderscut_int.c.

References BENDERSCUT_NAME, NULL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPbenderscutGetName(), SCIPbenderscutSetData(), and SCIPfreeBlockMemory.

◆ SCIP_DECL_BENDERSCUTINIT()

static SCIP_DECL_BENDERSCUTINIT ( benderscutInitInt  )
static

initialization method of Benders' decomposition cuts (called after problem was transformed)

Definition at line 529 of file benderscut_int.c.

References BENDERSCUT_NAME, createBenderscutData(), NULL, SCIP_CALL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPbenderscutGetName(), and SCIPbendersGetNSubproblems().

◆ SCIP_DECL_BENDERSCUTEXIT()

static SCIP_DECL_BENDERSCUTEXIT ( benderscutExitInt  )
static

deinitialization method of Benders' decomposition cuts (called before transformed problem is freed)

Definition at line 548 of file benderscut_int.c.

References BENDERSCUT_NAME, NULL, SCIP_OKAY, SCIPbenderscutGetData(), SCIPbenderscutGetName(), and SCIPfreeBlockMemoryArray.

◆ SCIP_DECL_BENDERSCUTEXEC()