Detailed Description

Generates a Laporte and Louveaux Benders' decomposition integer cut.

Author: Stephen J. Maher

#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 "scip/type_message.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_BENDERSCUTEXIT (benderscutExitInt)
static	SCIP_DECL_BENDERSCUTEXEC (benderscutExecInt)
SCIP_RETCODE	SCIPincludeBenderscutInt (SCIP scip, SCIP_BENDERS benders)

Macro Definition Documentation

◆ BENDERSCUT_NAME

#define BENDERSCUT_NAME "integer"

Definition at line 56 of file benderscut_int.c.

◆ BENDERSCUT_DESC

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

Definition at line 57 of file benderscut_int.c.

◆ BENDERSCUT_PRIORITY

#define BENDERSCUT_PRIORITY 0

Definition at line 58 of file benderscut_int.c.

◆ BENDERSCUT_LPCUT

#define BENDERSCUT_LPCUT FALSE

Definition at line 59 of file benderscut_int.c.

◆ SCIP_DEFAULT_ADDCUTS

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

Definition at line 61 of file benderscut_int.c.

Referenced by SCIPincludeBenderscutInt(), SCIPincludeBenderscutNogood(), and SCIPincludeBenderscutOpt().

◆ SCIP_DEFAULT_CUTCONSTANT

#define SCIP_DEFAULT_CUTCONSTANT -10000.0

Definition at line 62 of file benderscut_int.c.

Referenced by SCIPincludeBenderscutInt().

Function Documentation

◆ SCIP_DECL_PARAMCHGD()

SCIP_DECL_PARAMCHGD ( paramChgdBenderscutintConstant )

static

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

Definition at line 83 of file benderscut_int.c.

References assert(), i, NULL, SCIP_OKAY, and SCIPparamGetData().

◆ createBenderscutData()

SCIP_RETCODE createBenderscutData	(	SCIP *	scip,
		SCIP_BENDERSCUTDATA *	benderscutdata )

static

creates the Benders' decomposition cut data

Parameters

scip	the SCIP data structure
benderscutdata	the Benders' cut data

Definition at line 100 of file benderscut_int.c.

References assert(), FALSE, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPbendersGetNSubproblems(), SCIPbendersGetSubproblemMasterVarsData(), and TRUE.

Referenced by SCIP_DECL_BENDERSCUTEXEC().

◆ updateSubproblemCutConstant()

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

masterprob	the SCIP instance of the master problem
benders	the benders' decomposition structure
benderscutdata	the Benders' decomposition cut data
probnumber	the index for the subproblem

Definition at line 144 of file benderscut_int.c.

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

Referenced by generateAndApplyBendersIntegerCuts().

◆ computeStandardIntegerOptCut()

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

masterprob	the SCIP instance of the master problem
benders	the benders' decomposition structure
sol	primal CIP solution
cons	the constraint for the generated cut, can be NULL
row	the row for the generated cut, can be NULL
cutconstant	the constant value in the integer optimality cut
probnumber	the number of the pricing problem
addcut	indicates whether a cut is created instead of a constraint
success	was the cut generation successful?

Definition at line 176 of file benderscut_int.c.

References assert(), FALSE, i, NULL, nvars, SCIP_Bool, 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(), sol, TRUE, and vars.

Referenced by generateAndApplyBendersIntegerCuts().

◆ addAuxiliaryVariableToCut()

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

masterprob	the SCIP instance of the master problem
benders	the benders' decomposition structure
cons	the constraint for the generated cut, can be NULL
row	the row for the generated cut, can be NULL
probnumber	the number of the pricing problem
addcut	indicates whether a cut is created instead of a constraint

Definition at line 301 of file benderscut_int.c.

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

Referenced by generateAndApplyBendersIntegerCuts().

◆ generateAndApplyBendersIntegerCuts()

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

masterprob	the SCIP instance of the master 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
initcons	is this function called to generate the initial constraint

Definition at line 335 of file benderscut_int.c.

References addAuxiliaryVariableToCut(), assert(), BENDERSCUT_NAME, computeStandardIntegerOptCut(), FALSE, generateAndApplyBendersIntegerCuts(), NULL, result, 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(), sol, TRUE, and updateSubproblemCutConstant().

Referenced by generateAndApplyBendersIntegerCuts(), and SCIP_DECL_BENDERSCUTEXEC().

◆ SCIP_DECL_BENDERSCUTFREE()

SCIP_DECL_BENDERSCUTFREE ( benderscutFreeInt )

static

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

Definition at line 526 of file benderscut_int.c.

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

◆ SCIP_DECL_BENDERSCUTEXIT()

SCIP_DECL_BENDERSCUTEXIT ( benderscutExitInt )

static

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

Definition at line 547 of file benderscut_int.c.

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

◆ SCIP_DECL_BENDERSCUTEXEC()

SCIP_DECL_BENDERSCUTEXEC ( benderscutExecInt )

static

execution method of Benders' decomposition cuts

Definition at line 569 of file benderscut_int.c.

References assert(), BENDERSCUT_NAME, createBenderscutData(), FALSE, generateAndApplyBendersIntegerCuts(), NULL, result, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_STATUS_OPTIMAL, SCIPbenderscutGetData(), SCIPbenderscutSetEnabled(), SCIPbendersSubproblem(), SCIPdebugMsg, SCIPgetStatus(), SCIPwarningMessage(), and sol.

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BENDERSCUT_NAME

◆ BENDERSCUT_DESC

◆ BENDERSCUT_PRIORITY

◆ BENDERSCUT_LPCUT

◆ SCIP_DEFAULT_ADDCUTS

◆ SCIP_DEFAULT_CUTCONSTANT

Function Documentation

◆ SCIP_DECL_PARAMCHGD()

◆ createBenderscutData()

◆ updateSubproblemCutConstant()

◆ computeStandardIntegerOptCut()

◆ addAuxiliaryVariableToCut()

◆ generateAndApplyBendersIntegerCuts()

◆ SCIP_DECL_BENDERSCUTFREE()

◆ SCIP_DECL_BENDERSCUTEXIT()

◆ SCIP_DECL_BENDERSCUTEXEC()