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 <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

#define BENDERSCUT_NAME "integer"

Definition at line 55 of file benderscut_int.c.

Referenced by generateAndApplyBendersIntegerCuts(), SCIP_DECL_BENDERSCUTEXEC(), SCIP_DECL_BENDERSCUTEXIT(), SCIP_DECL_BENDERSCUTFREE(), SCIP_DECL_BENDERSCUTINIT(), and SCIPincludeBenderscutInt().

◆ 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

scip	the SCIP data structure
benderscutdata	the 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

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 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

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 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

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 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

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 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_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()

static SCIP_DECL_BENDERSCUTEXEC ( benderscutExecInt )

static

execution method of Benders' decomposition cuts

Definition at line 567 of file benderscut_int.c.

References BENDERSCUT_NAME, FALSE, generateAndApplyBendersIntegerCuts(), NULL, SCIP_CALL, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_STATUS_OPTIMAL, SCIPbenderscutSetEnabled(), SCIPbendersGetNSubproblems(), SCIPbendersMasterIsNonlinear(), SCIPbendersSubproblem(), SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNVars(), SCIPgetStatus(), and SCIPinfoMessage().

SCIP

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_BENDERSCUTINIT()

◆ SCIP_DECL_BENDERSCUTEXIT()

◆ SCIP_DECL_BENDERSCUTEXEC()