Detailed Description

methods for Benders' decomposition cut

Author: Stephen J. Maher

Definition in file benderscut.c.

#include <assert.h>
#include <string.h>
#include "scip/def.h"
#include "scip/set.h"
#include "scip/clock.h"
#include "scip/paramset.h"
#include "scip/scip.h"
#include "scip/benderscut.h"
#include "scip/reopt.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_benders.h"
#include "scip/struct_benderscut.h"

Go to the source code of this file.

Macros
#define	BENDERSCUT_ARRAYSIZE 10

#define	SCIP_DEFAULT_ENABLED TRUE

Functions
	SCIP_DECL_SORTPTRCOMP (SCIPbenderscutComp)

	SCIP_DECL_SORTPTRCOMP (SCIPbenderscutCompName)

static	SCIP_DECL_PARAMCHGD (paramChgdBenderscutPriority)

SCIP_RETCODE	SCIPbenderscutCopyInclude (SCIP_BENDERS benders, SCIP_BENDERSCUT benderscut, SCIP_SET *set)

static SCIP_RETCODE	doBenderscutCreate (SCIP_BENDERS benders, SCIP_BENDERSCUT benderscut, SCIP_SET set, SCIP_MESSAGEHDLR messagehdlr, BMS_BLKMEM blkmem, const char name, const char desc, int priority, SCIP_Bool islpcut, SCIP_DECL_BENDERSCUTCOPY((benderscutcopy)), SCIP_DECL_BENDERSCUTFREE((benderscutfree)), SCIP_DECL_BENDERSCUTINIT((benderscutinit)), SCIP_DECL_BENDERSCUTEXIT((benderscutexit)), SCIP_DECL_BENDERSCUTINITSOL((benderscutinitsol)), SCIP_DECL_BENDERSCUTEXITSOL((benderscutexitsol)), SCIP_DECL_BENDERSCUTEXEC((benderscutexec)), SCIP_BENDERSCUTDATA benderscutdata)

SCIP_RETCODE	SCIPbenderscutCreate (SCIP_BENDERS benders, SCIP_BENDERSCUT benderscut, SCIP_SET set, SCIP_MESSAGEHDLR messagehdlr, BMS_BLKMEM blkmem, const char name, const char desc, int priority, SCIP_Bool islpcut, SCIP_DECL_BENDERSCUTCOPY((benderscutcopy)), SCIP_DECL_BENDERSCUTFREE((benderscutfree)), SCIP_DECL_BENDERSCUTINIT((benderscutinit)), SCIP_DECL_BENDERSCUTEXIT((benderscutexit)), SCIP_DECL_BENDERSCUTINITSOL((benderscutinitsol)), SCIP_DECL_BENDERSCUTEXITSOL((benderscutexitsol)), SCIP_DECL_BENDERSCUTEXEC((benderscutexec)), SCIP_BENDERSCUTDATA benderscutdata)

SCIP_RETCODE	SCIPbenderscutFree (SCIP_BENDERSCUT *benderscut, SCIP_SET set)

SCIP_RETCODE	SCIPbenderscutInit (SCIP_BENDERSCUT benderscut, SCIP_SET set)

SCIP_RETCODE	SCIPbenderscutExit (SCIP_BENDERSCUT benderscut, SCIP_SET set)

SCIP_RETCODE	SCIPbenderscutInitsol (SCIP_BENDERSCUT benderscut, SCIP_SET set)

SCIP_RETCODE	SCIPbenderscutExitsol (SCIP_BENDERSCUT benderscut, SCIP_SET set)

SCIP_RETCODE	SCIPbenderscutExec (SCIP_BENDERSCUT benderscut, SCIP_SET set, SCIP_BENDERS benders, SCIP_SOL sol, int probnumber, SCIP_BENDERSENFOTYPE type, SCIP_RESULT *result)

SCIP_BENDERSCUTDATA *	SCIPbenderscutGetData (SCIP_BENDERSCUT *benderscut)

void	SCIPbenderscutSetData (SCIP_BENDERSCUT benderscut, SCIP_BENDERSCUTDATA benderscutdata)

void	SCIPbenderscutSetCopy (SCIP_BENDERSCUT benderscut, SCIP_DECL_BENDERSCUTCOPY((benderscutcopy)))

void	SCIPbenderscutSetFree (SCIP_BENDERSCUT benderscut, SCIP_DECL_BENDERSCUTFREE((benderscutfree)))

void	SCIPbenderscutSetInit (SCIP_BENDERSCUT benderscut, SCIP_DECL_BENDERSCUTINIT((benderscutinit)))

void	SCIPbenderscutSetExit (SCIP_BENDERSCUT benderscut, SCIP_DECL_BENDERSCUTEXIT((benderscutexit)))

void	SCIPbenderscutSetInitsol (SCIP_BENDERSCUT benderscut, SCIP_DECL_BENDERSCUTINITSOL((benderscutinitsol)))

void	SCIPbenderscutSetExitsol (SCIP_BENDERSCUT benderscut, SCIP_DECL_BENDERSCUTEXITSOL((benderscutexitsol)))

const char *	SCIPbenderscutGetName (SCIP_BENDERSCUT *benderscut)

const char *	SCIPbenderscutGetDesc (SCIP_BENDERSCUT *benderscut)

int	SCIPbenderscutGetPriority (SCIP_BENDERSCUT *benderscut)

void	SCIPbenderscutSetPriority (SCIP_BENDERSCUT *benderscut, int priority)

SCIP_Longint	SCIPbenderscutGetNCalls (SCIP_BENDERSCUT *benderscut)

SCIP_Longint	SCIPbenderscutGetNFound (SCIP_BENDERSCUT *benderscut)

SCIP_Bool	SCIPbenderscutIsInitialized (SCIP_BENDERSCUT *benderscut)

SCIP_Real	SCIPbenderscutGetSetupTime (SCIP_BENDERSCUT *benderscut)

SCIP_Real	SCIPbenderscutGetTime (SCIP_BENDERSCUT *benderscut)

int	SCIPbenderscutGetNAddedCuts (SCIP_BENDERSCUT *benderscut)

SCIP_RETCODE	SCIPbenderscutGetAddedCutData (SCIP_BENDERSCUT benderscut, int cutidx, SCIP_VAR vars, SCIP_Real vals, SCIP_Real lhs, SCIP_Real rhs, int *nvars)

SCIP_RETCODE	SCIPbenderscutStoreCut (SCIP_BENDERSCUT benderscut, SCIP_SET set, SCIP_VAR *vars, SCIP_Real vals, SCIP_Real lhs, SCIP_Real rhs, int nvars)

SCIP_Bool	SCIPbenderscutIsLPCut (SCIP_BENDERSCUT *benderscut)

void	SCIPbenderscutSetEnabled (SCIP_BENDERSCUT *benderscut, SCIP_Bool enabled)

Macro Definition Documentation

◆ BENDERSCUT_ARRAYSIZE

#define BENDERSCUT_ARRAYSIZE 10

the initial size of the added constraints/cuts arrays

Definition at line 39 of file benderscut.c.

Referenced by SCIPbenderscutInit().

◆ SCIP_DEFAULT_ENABLED

#define SCIP_DEFAULT_ENABLED TRUE

Definition at line 42 of file benderscut.c.

Referenced by doBenderscutCreate().

Function Documentation

◆ SCIP_DECL_PARAMCHGD()

static SCIP_DECL_PARAMCHGD ( paramChgdBenderscutPriority )

static

method to call, when the priority of a compression was changed

Definition at line 64 of file benderscut.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPparamGetData(), SCIPparamGetInt(), and SCIPsetBenderscutPriority().

◆ SCIPbenderscutCopyInclude()

SCIP_RETCODE SCIPbenderscutCopyInclude	(	SCIP_BENDERS *	benders,
		SCIP_BENDERSCUT *	benderscut,
		SCIP_SET *	set
	)

copies the given Benders' decomposition cut to a new scip

Parameters

benders	the Benders' decomposition that the cuts are copied to
benderscut	Benders' decomposition cut
set	SCIP_SET of SCIP to copy to

Definition at line 78 of file benderscut.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPbenderscutGetName(), and SCIPsetDebugMsg.

Referenced by SCIPbendersCopyInclude().

◆ doBenderscutCreate()

static SCIP_RETCODE doBenderscutCreate	(	SCIP_BENDERS *	benders,
		SCIP_BENDERSCUT **	benderscut,
		SCIP_SET *	set,
		SCIP_MESSAGEHDLR *	messagehdlr,
		BMS_BLKMEM *	blkmem,
		const char *	name,
		const char *	desc,
		int	priority,
		SCIP_Bool	islpcut,
		SCIP_DECL_BENDERSCUTCOPY((*benderscutcopy))	,
		SCIP_DECL_BENDERSCUTFREE((*benderscutfree))	,
		SCIP_DECL_BENDERSCUTINIT((*benderscutinit))	,
		SCIP_DECL_BENDERSCUTEXIT((*benderscutexit))	,
		SCIP_DECL_BENDERSCUTINITSOL((*benderscutinitsol))	,
		SCIP_DECL_BENDERSCUTEXITSOL((*benderscutexitsol))	,
		SCIP_DECL_BENDERSCUTEXEC((*benderscutexec))	,
		SCIP_BENDERSCUTDATA *	benderscutdata
	)

static

internal method for creating a Benders' decomposition structure

Parameters

benders	Benders' decomposition
benderscut	pointer to the Benders' decomposition cut data structure
set	global SCIP settings
messagehdlr	message handler
blkmem	block memory for parameter settings
name	name of the Benders' decomposition cut
desc	description of the Benders' decomposition cut
priority	priority of the the Benders' decomposition cut
islpcut	indicates whether the cut is generated from the LP solution
benderscutdata	Benders' decomposition cut data

Definition at line 99 of file benderscut.c.

References BMSallocMemory, BMSduplicateMemoryArray, FALSE, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_CLOCKTYPE_DEFAULT, SCIP_DEFAULT_ENABLED, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPbendersGetName(), SCIPclockCreate(), SCIPsetAddBoolParam(), SCIPsetAddIntParam(), SCIPsnprintf(), and TRUE.

Referenced by SCIPbenderscutCreate().

◆ SCIPbenderscutCreate()

SCIP_RETCODE SCIPbenderscutCreate	(	SCIP_BENDERS *	benders,
		SCIP_BENDERSCUT **	benderscut,
		SCIP_SET *	set,
		SCIP_MESSAGEHDLR *	messagehdlr,
		BMS_BLKMEM *	blkmem,
		const char *	name,
		const char *	desc,
		int	priority,
		SCIP_Bool	islpcut,
		SCIP_DECL_BENDERSCUTCOPY((*benderscutcopy))	,
		SCIP_DECL_BENDERSCUTFREE((*benderscutfree))	,
		SCIP_DECL_BENDERSCUTINIT((*benderscutinit))	,
		SCIP_DECL_BENDERSCUTEXIT((*benderscutexit))	,
		SCIP_DECL_BENDERSCUTINITSOL((*benderscutinitsol))	,
		SCIP_DECL_BENDERSCUTEXITSOL((*benderscutexitsol))	,
		SCIP_DECL_BENDERSCUTEXEC((*benderscutexec))	,
		SCIP_BENDERSCUTDATA *	benderscutdata
	)

creates a Benders' decomposition cut

Parameters

benders	Benders' decomposition
benderscut	pointer to the Benders' decomposition cut data structure
set	global SCIP settings
messagehdlr	message handler
blkmem	block memory for parameter settings
name	name of the Benders' decomposition cut
desc	description of the Benders' decomposition cut
priority	priority of the the Benders' decomposition cut
islpcut	indicates whether the cut is generated from the LP solution
benderscutdata	Benders' decomposition cut data

Definition at line 165 of file benderscut.c.

References doBenderscutCreate(), NULL, SCIP_CALL_FINALLY, SCIP_OKAY, and SCIPbenderscutFree().

Referenced by SCIPincludeBenderscut(), and SCIPincludeBenderscutBasic().

◆ SCIPbenderscutFree()

SCIP_RETCODE SCIPbenderscutFree	(	SCIP_BENDERSCUT **	benderscut,
		SCIP_SET *	set
	)

calls destructor and frees memory of the Benders' decomposition cut

Parameters

benderscut	pointer to the Benders' decomposition cut data structure
set	global SCIP settings

Definition at line 198 of file benderscut.c.

References BMSfreeMemory, BMSfreeMemoryArray, NULL, SCIP_CALL, SCIP_OKAY, and SCIPclockFree().

Referenced by SCIPbenderscutCreate(), and SCIPbendersFree().

◆ SCIPbenderscutInit()

SCIP_RETCODE SCIPbenderscutInit	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_SET *	set
	)

initializes the Benders' decomposition cut

Parameters

benderscut	Benders' decomposition cut
set	global SCIP settings

Definition at line 224 of file benderscut.c.

References SCIP_Benderscut::addedcuts, SCIP_Benderscut::addedcutssize, BENDERSCUT_ARRAYSIZE, SCIP_Benderscut::benderscutclock, BMSallocBlockMemoryArray, SCIP_Benderscut::initialized, SCIP_Benderscut::name, SCIP_Benderscut::ncalls, SCIP_Benderscut::nfound, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPblkmem(), SCIPclockReset(), SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, SCIP_Benderscut::setuptime, and TRUE.

Referenced by SCIPbendersInit().

◆ SCIPbenderscutExit()

SCIP_RETCODE SCIPbenderscutExit	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_SET *	set
	)

calls exit method of the Benders' decomposition cut

Parameters

benderscut	Benders' decomposition cut
set	global SCIP settings

Definition at line 270 of file benderscut.c.

References SCIP_Benderscut::addedcuts, SCIP_Benderscut::addedcutssize, BMSfreeBlockMemoryArray, FALSE, SCIP_Benderscut::initialized, SCIP_Benderscut::naddedcuts, SCIP_Benderscut::name, NULL, SCIP_BenderscutCut::nvars, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPblkmem(), SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIP_Benderscut::setuptime, SCIP_BenderscutCut::vals, and SCIP_BenderscutCut::vars.

Referenced by SCIPbendersExit().

◆ SCIPbenderscutInitsol()

SCIP_RETCODE SCIPbenderscutInitsol	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_SET *	set
	)

informs Benders' cut that the branch and bound process is being started

Parameters

benderscut	Benders' decomposition cut
set	global SCIP settings

Definition at line 314 of file benderscut.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Benderscut::setuptime.

Referenced by SCIPbendersInitsol().

◆ SCIPbenderscutExitsol()

SCIP_RETCODE SCIPbenderscutExitsol	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_SET *	set
	)

informs Benders' decomposition that the branch and bound process data is being freed

Parameters

benderscut	Benders' decomposition
set	global SCIP settings

Definition at line 338 of file benderscut.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPclockStart(), SCIPclockStop(), and SCIP_Benderscut::setuptime.

Referenced by SCIPbendersExitsol().

◆ SCIPbenderscutExec()

SCIP_RETCODE SCIPbenderscutExec	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_SET *	set,
		SCIP_BENDERS *	benders,
		SCIP_SOL *	sol,
		int	probnumber,
		SCIP_BENDERSENFOTYPE	type,
		SCIP_RESULT *	result
	)

calls execution method of the Benders' decomposition cut

Parameters

benderscut	Benders' decomposition cut
set	global SCIP settings
benders	Benders' decomposition
sol	primal CIP solution
probnumber	the number of the subproblem for which the cut is generated
type	the enforcement type calling this function
result	pointer to store the result of the callback method

Definition at line 362 of file benderscut.c.

References SCIP_Benderscut::benderscutclock, SCIP_Benderscut::enabled, SCIP_Benderscut::name, SCIP_Benderscut::ncalls, SCIP_Benderscut::nfound, NULL, SCIP_CALL, SCIP_CONSADDED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_INVALIDRESULT, SCIP_OKAY, SCIP_SEPARATED, SCIPclockStart(), SCIPclockStop(), SCIPerrorMessage, and SCIPsetDebugMsg.

Referenced by generateBendersCuts().

◆ SCIPbenderscutSetCopy()

void SCIPbenderscutSetCopy	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_DECL_BENDERSCUTCOPY((*benderscutcopy))
	)

sets copy callback of the Benders' decomposition cut

Parameters

benderscut Benders' decomposition cut

Definition at line 442 of file benderscut.c.

References NULL.

Referenced by SCIPsetBenderscutCopy().

◆ SCIPbenderscutSetFree()

void SCIPbenderscutSetFree	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_DECL_BENDERSCUTFREE((*benderscutfree))
	)

sets destructor callback of the Benders' decomposition cut

Parameters

benderscut Benders' decomposition cut

Definition at line 453 of file benderscut.c.

References NULL.

Referenced by SCIPsetBenderscutFree().

◆ SCIPbenderscutSetInit()

void SCIPbenderscutSetInit	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_DECL_BENDERSCUTINIT((*benderscutinit))
	)

sets initialization callback of the Benders' decomposition cut

Parameters

benderscut Benders' decomposition cut

Definition at line 464 of file benderscut.c.

References NULL.

Referenced by SCIPsetBenderscutInit().

◆ SCIPbenderscutSetExit()

void SCIPbenderscutSetExit	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_DECL_BENDERSCUTEXIT((*benderscutexit))
	)

sets deinitialization callback of the Benders' decomposition cut

Parameters

benderscut Benders' decomposition cut

Definition at line 475 of file benderscut.c.

References NULL.

Referenced by SCIPsetBenderscutExit().

◆ SCIPbenderscutSetInitsol()

void SCIPbenderscutSetInitsol	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_DECL_BENDERSCUTINITSOL((*benderscutinitsol))
	)

sets solving process initialization callback of the Benders' decomposition cut

Parameters

benderscut Benders' decomposition cut

Definition at line 486 of file benderscut.c.

References NULL.

Referenced by SCIPsetBenderscutInitsol().

◆ SCIPbenderscutSetExitsol()

void SCIPbenderscutSetExitsol	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_DECL_BENDERSCUTEXITSOL((*benderscutexitsol))
	)

sets solving process deinitialization callback of Benders' decomposition cut

Parameters

benderscut Benders' decomposition cut

Definition at line 497 of file benderscut.c.

References NULL.

Referenced by SCIPsetBenderscutExitsol().

◆ SCIPbenderscutSetPriority()

void SCIPbenderscutSetPriority	(	SCIP_BENDERSCUT *	benderscut,
		int	priority
	)

sets priority of the Benders' decomposition cut

Parameters

benderscut	Benders' decomposition cut
priority	new priority of the Benders' decomposition cut

Definition at line 538 of file benderscut.c.

References NULL, and SCIP_Benderscut::priority.

Referenced by SCIPsetBenderscutPriority().

◆ SCIPbenderscutStoreCut()

SCIP_RETCODE SCIPbenderscutStoreCut	(	SCIP_BENDERSCUT *	benderscut,
		SCIP_SET *	set,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		SCIP_Real	lhs,
		SCIP_Real	rhs,
		int	nvars
	)

adds the data for the generated cuts to the Benders' cut storage

Parameters

benderscut	Benders' decomposition cut
set	global SCIP settings
vars	the variables that have non-zero coefficients in the cut
vals	the coefficients of the variables in the cut
lhs	the left hand side of the cut
rhs	the right hand side of the cut
nvars	the number of variables with non-zero coefficients in the cut

Definition at line 637 of file benderscut.c.

References SCIP_Benderscut::addedcuts, SCIP_Benderscut::addedcutssize, BMSreallocBlockMemoryArray, SCIP_BenderscutCut::lhs, SCIP_Benderscut::naddedcuts, NULL, SCIP_BenderscutCut::nvars, SCIP_BenderscutCut::rhs, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPblkmem(), SCIPduplicateBlockMemoryArray, SCIPsetCalcMemGrowSize(), SCIP_BenderscutCut::vals, and SCIP_BenderscutCut::vars.

Referenced by SCIPstoreBenderscutCut().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ BENDERSCUT_ARRAYSIZE

◆ SCIP_DEFAULT_ENABLED

Function Documentation

◆ SCIP_DECL_PARAMCHGD()

◆ SCIPbenderscutCopyInclude()

◆ doBenderscutCreate()

◆ SCIPbenderscutCreate()

◆ SCIPbenderscutFree()

◆ SCIPbenderscutInit()

◆ SCIPbenderscutExit()

◆ SCIPbenderscutInitsol()

◆ SCIPbenderscutExitsol()

◆ SCIPbenderscutExec()

◆ SCIPbenderscutSetCopy()

◆ SCIPbenderscutSetFree()

◆ SCIPbenderscutSetInit()

◆ SCIPbenderscutSetExit()

◆ SCIPbenderscutSetInitsol()

◆ SCIPbenderscutSetExitsol()

◆ SCIPbenderscutSetPriority()

◆ SCIPbenderscutStoreCut()