Detailed Description

methods for storing cuts in a cut pool

Author: Tobias Achterberg; Stefan Heinz; Gerald Gamrath; Marc Pfetsch; Kati Wolter

Definition in file cutpool.c.

#include <assert.h>
#include "scip/def.h"
#include "scip/set.h"
#include "scip/stat.h"
#include "scip/clock.h"
#include "scip/lp.h"
#include "scip/cons.h"
#include "scip/sepa.h"
#include "scip/sepastore.h"
#include "scip/cutpool.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/struct_cutpool.h"

Go to the source code of this file.

Functions
static	SCIP_DECL_HASHGETKEY (hashGetKeyCut)

static	SCIP_DECL_HASHKEYEQ (hashKeyEqCut)

static	SCIP_DECL_HASHKEYVAL (hashKeyValCut)

static SCIP_RETCODE	cutpoolEnsureCutsMem (SCIP_CUTPOOL cutpool, SCIP_SET set, int num)

static SCIP_RETCODE	cutCreate (SCIP_CUT *cut, BMS_BLKMEM blkmem, SCIP_ROW *row)

static SCIP_RETCODE	cutFree (SCIP_CUT *cut, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_LP lp)

static SCIP_Bool	cutIsAged (SCIP_CUT *cut, int agelimit)

SCIP_ROW *	SCIPcutGetRow (SCIP_CUT *cut)

int	SCIPcutGetAge (SCIP_CUT *cut)

SCIP_Real	SCIPcutGetLPActivityQuot (SCIP_CUT *cut)

SCIP_RETCODE	SCIPcutpoolCreate (SCIP_CUTPOOL *cutpool, BMS_BLKMEM blkmem, SCIP_SET *set, int agelimit, SCIP_Bool globalcutpool)

SCIP_RETCODE	SCIPcutpoolFree (SCIP_CUTPOOL *cutpool, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_LP lp)

SCIP_RETCODE	SCIPcutpoolClear (SCIP_CUTPOOL cutpool, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_LP lp)

SCIP_RETCODE	SCIPcutpoolAddRow (SCIP_CUTPOOL cutpool, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_ROW row)

SCIP_RETCODE	SCIPcutpoolAddNewRow (SCIP_CUTPOOL cutpool, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_ROW row)

static SCIP_RETCODE	cutpoolDelCut (SCIP_CUTPOOL cutpool, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_STAT stat, SCIP_LP lp, SCIP_CUT cut)

SCIP_RETCODE	SCIPcutpoolDelRow (SCIP_CUTPOOL cutpool, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_STAT stat, SCIP_LP lp, SCIP_ROW row)

SCIP_RETCODE	SCIPcutpoolSeparate (SCIP_CUTPOOL cutpool, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_STAT stat, SCIP_EVENTQUEUE eventqueue, SCIP_EVENTFILTER eventfilter, SCIP_LP lp, SCIP_SEPASTORE sepastore, SCIP_SOL sol, SCIP_Bool cutpoolisdelayed, SCIP_Bool root, SCIP_RESULT result)

SCIP_CUT **	SCIPcutpoolGetCuts (SCIP_CUTPOOL *cutpool)

int	SCIPcutpoolGetNCuts (SCIP_CUTPOOL *cutpool)

int	SCIPcutpoolGetMaxNCuts (SCIP_CUTPOOL *cutpool)

SCIP_Real	SCIPcutpoolGetTime (SCIP_CUTPOOL *cutpool)

SCIP_Longint	SCIPcutpoolGetNCalls (SCIP_CUTPOOL *cutpool)

SCIP_Longint	SCIPcutpoolGetNCutsFound (SCIP_CUTPOOL *cutpool)

Function Documentation

static SCIP_DECL_HASHGETKEY ( hashGetKeyCut )

static

gets the hash key of a cut

Definition at line 51 of file cutpool.c.

References NULL, and SCIP_Cut::row.

static SCIP_DECL_HASHKEYEQ ( hashKeyEqCut )

static

returns TRUE iff both cuts are identical

Definition at line 65 of file cutpool.c.

References SCIP_Row::cols, FALSE, SCIP_Col::index, SCIP_Row::len, SCIP_Row::lhs, SCIP_Row::lpcolssorted, SCIP_Row::maxidx, SCIP_Row::maxval, SCIP_Row::minidx, SCIP_Row::nlpcols, SCIP_Row::nonlpcolssorted, NULL, SCIP_Row::nummaxval, SCIP_Row::nunlinked, REALABS, SCIP_Row::rhs, SCIP_DEFAULT_EPSILON, SCIP_DEFAULT_SUMEPSILON, SCIProwSort(), SCIP_Row::sqrnorm, SCIP_Row::sumnorm, TRUE, SCIP_Row::validminmaxidx, and SCIP_Row::vals.

static SCIP_DECL_HASHKEYVAL ( hashKeyValCut )

static

Definition at line 233 of file cutpool.c.

References SCIP_Row::len, SCIP_Row::maxidx, SCIP_Row::minidx, NULL, SCIP_Row::nummaxval, SCIP_Real, SCIProwGetMaxval(), and SCIP_Row::validminmaxidx.

static SCIP_RETCODE cutpoolEnsureCutsMem	(	SCIP_CUTPOOL *	cutpool,
		SCIP_SET *	set,
		int	num
	)

static

resizes cuts array to be able to store at least num entries

Parameters

cutpool	cut pool
set	global SCIP settings
num	minimal number of slots in array

Definition at line 269 of file cutpool.c.

References BMSreallocMemoryArray, SCIP_Cutpool::cuts, SCIP_Cutpool::cutssize, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIPsetCalcMemGrowSize().

Referenced by SCIPcutpoolAddNewRow().

static SCIP_RETCODE cutCreate	(	SCIP_CUT **	cut,
		BMS_BLKMEM *	blkmem,
		SCIP_ROW *	row
	)

static

creates a cut and captures the row

Parameters

cut	pointer to store the cut
blkmem	block memory
row	row this cut represents

Definition at line 299 of file cutpool.c.

References SCIP_Row::age, BMSallocBlockMemory, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIProwCapture().

Referenced by SCIPcutpoolAddNewRow().

static SCIP_RETCODE cutFree	(	SCIP_CUT **	cut,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_LP *	lp
	)

static

frees a cut and releases the row

Parameters

cut	pointer to store the cut
blkmem	block memory
set	global SCIP settings
lp	current LP data

Definition at line 325 of file cutpool.c.

References BMSfreeBlockMemory, NULL, SCIP_CALL, SCIP_OKAY, and SCIProwRelease().

Referenced by cutpoolDelCut(), and SCIPcutpoolClear().

static SCIP_Bool cutIsAged	(	SCIP_CUT *	cut,
		int	agelimit
	)

static

returns whether the cut's age exceeds the age limit

Parameters

cut	cut to check
agelimit	maximum age a cut can reach before it is deleted from the pool, or -1

Definition at line 348 of file cutpool.c.

References SCIP_Cut::age, and NULL.

Referenced by SCIPcutpoolSeparate().

SCIP_ROW* SCIPcutGetRow ( SCIP_CUT * cut )

gets the row of the cut

Parameters

cut cut

Definition at line 359 of file cutpool.c.

References NULL, and SCIP_Cut::row.

Referenced by copyCuts(), and takeCut().

int SCIPcutGetAge ( SCIP_CUT * cut )

gets the age of the cut: the number of consecutive cut pool separation rounds where the cut was neither in the LP nor violated

Parameters

cut cut

Definition at line 369 of file cutpool.c.

References SCIP_Cut::age, and NULL.

Referenced by takeCut().

SCIP_Real SCIPcutGetLPActivityQuot ( SCIP_CUT * cut )

returns the ratio of LPs where the row belonging to this cut was active in an LP solution, i.e. where the age of its row has not been increased

See also: SCIPcutGetAge() to get the age of a cut

Parameters

cut cut

Definition at line 383 of file cutpool.c.

References NULL, SCIP_Cut::row, SCIP_Longint, SCIP_Real, SCIProwGetActiveLPCount(), and SCIProwGetNLPsAfterCreation().

Referenced by takeCut().

SCIP_RETCODE SCIPcutpoolCreate	(	SCIP_CUTPOOL **	cutpool,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		int	agelimit,
		SCIP_Bool	globalcutpool
	)

creates cut pool

Parameters

cutpool	pointer to store cut pool
blkmem	block memory
set	global SCIP settings
agelimit	maximum age a cut can reach before it is deleted from the pool
globalcutpool	is this the global cut pool of SCIP?

Definition at line 404 of file cutpool.c.

References BMSallocMemory, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_CLOCKTYPE_DEFAULT, SCIP_HASHSIZE_CUTPOOLS, SCIP_HASHSIZE_CUTPOOLS_SMALL, SCIP_OKAY, SCIPclockCreate(), and SCIPhashtableCreate().

Referenced by initSolve(), and SCIPcreateCutpool().

SCIP_RETCODE SCIPcutpoolFree	(	SCIP_CUTPOOL **	cutpool,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_LP *	lp
	)

frees cut pool

Parameters

cutpool	pointer to store cut pool
blkmem	block memory
set	global SCIP settings
lp	current LP data

Definition at line 441 of file cutpool.c.

References BMSfreeMemory, BMSfreeMemoryArrayNull, NULL, SCIP_CALL, SCIP_OKAY, SCIPclockFree(), SCIPcutpoolClear(), and SCIPhashtableFree().

Referenced by freeSolve(), and SCIPfreeCutpool().

SCIP_RETCODE SCIPcutpoolClear	(	SCIP_CUTPOOL *	cutpool,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_LP *	lp
	)

removes all rows from the cut pool

Parameters

cutpool	cut pool
blkmem	block memory
set	global SCIP settings
lp	current LP data

Definition at line 467 of file cutpool.c.

References cutFree(), SCIP_Cutpool::cuts, FALSE, SCIP_Cutpool::globalcutpool, SCIP_Row::inglobalcutpool, SCIP_Cutpool::ncuts, SCIP_Cutpool::nremovablecuts, NULL, SCIP_Cut::row, SCIP_CALL, SCIP_OKAY, and SCIProwUnlock().

Referenced by freeSolve(), and SCIPcutpoolFree().

SCIP_RETCODE SCIPcutpoolAddRow	(	SCIP_CUTPOOL *	cutpool,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_ROW *	row
	)

if not already existing, adds row to cut pool and captures it

Parameters

cutpool	cut pool
blkmem	block memory
set	global SCIP settings
row	cutting plane to add

Definition at line 493 of file cutpool.c.

References SCIP_Cutpool::hashtable, NULL, SCIP_CALL, SCIP_OKAY, SCIPcutpoolAddNewRow(), SCIPhashtableRetrieve(), SCIProwGetMaxidx(), and SCIP_Row::validminmaxidx.

Referenced by SCIPaddDelayedPoolCut(), SCIPaddPoolCut(), and SCIPaddRowCutpool().

SCIP_RETCODE SCIPcutpoolAddNewRow	(	SCIP_CUTPOOL *	cutpool,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_ROW *	row
	)

adds row to cut pool and captures it; doesn't check for multiple cuts

Parameters

cutpool	cut pool
blkmem	block memory
set	global SCIP settings
row	cutting plane to add

Definition at line 517 of file cutpool.c.

References cutCreate(), cutpoolEnsureCutsMem(), SCIP_Cutpool::cuts, SCIP_Cutpool::globalcutpool, SCIP_Cutpool::hashtable, SCIP_Row::inglobalcutpool, MAX, SCIP_Cutpool::maxncuts, SCIP_Cutpool::ncuts, SCIP_Cutpool::nremovablecuts, NULL, SCIP_Cut::pos, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPerrorMessage, SCIPhashtableInsert(), SCIProwGetMaxidx(), SCIProwGetName(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIProwIsRemovable(), SCIProwLock(), TRUE, and SCIP_Row::validminmaxidx.

Referenced by SCIPaddNewRowCutpool(), and SCIPcutpoolAddRow().

static SCIP_RETCODE cutpoolDelCut	(	SCIP_CUTPOOL *	cutpool,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_LP *	lp,
		SCIP_CUT *	cut
	)

static

removes the cut from the cut pool

Parameters

cutpool	cut pool
blkmem	block memory
set	global SCIP settings
stat	problem statistics data
lp	current LP data
cut	cut to remove

Definition at line 572 of file cutpool.c.

References cutFree(), SCIP_Cutpool::cuts, FALSE, SCIP_Cutpool::firstunprocessed, SCIP_Cutpool::firstunprocessedsol, SCIP_Cutpool::globalcutpool, SCIP_Cutpool::hashtable, SCIP_Row::inglobalcutpool, SCIP_Stat::lpcount, MIN, SCIP_Cutpool::ncuts, SCIP_Cutpool::nremovablecuts, NULL, SCIP_Cut::pos, SCIP_Cut::processedlp, SCIP_Cutpool::processedlp, SCIP_Cut::processedlpsol, SCIP_Cutpool::processedlpsol, SCIP_Cut::row, SCIP_CALL, SCIP_OKAY, SCIPhashtableExists(), SCIPhashtableRemove(), SCIProwIsRemovable(), and SCIProwUnlock().

Referenced by SCIPcutpoolDelRow(), and SCIPcutpoolSeparate().

SCIP_RETCODE SCIPcutpoolDelRow	(	SCIP_CUTPOOL *	cutpool,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_LP *	lp,
		SCIP_ROW *	row
	)

removes the LP row from the cut pool

Parameters

cutpool	cut pool
blkmem	block memory
set	global SCIP settings
stat	problem statistics data
lp	current LP data
row	row to remove

Definition at line 641 of file cutpool.c.

References cutpoolDelCut(), SCIP_Cutpool::hashtable, NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPerrorMessage, SCIPhashtableRetrieve(), and SCIProwGetName().

Referenced by SCIPdelDelayedPoolCut(), SCIPdelPoolCut(), and SCIPdelRowCutpool().

SCIP_RETCODE SCIPcutpoolSeparate	(	SCIP_CUTPOOL *	cutpool,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_EVENTQUEUE *	eventqueue,
		SCIP_EVENTFILTER *	eventfilter,
		SCIP_LP *	lp,
		SCIP_SEPASTORE *	sepastore,
		SCIP_SOL *	sol,
		SCIP_Bool	cutpoolisdelayed,
		SCIP_Bool	root,
		SCIP_RESULT *	result
	)

separates cuts of the cut pool

Parameters

cutpool	cut pool
blkmem	block memory
set	global SCIP settings
stat	problem statistics data
eventqueue	event queue
eventfilter	event filter for global events
lp	current LP data
sepastore	separation storage
sol	solution to be separated (or NULL for LP-solution)
cutpoolisdelayed	is the cutpool delayed (count cuts found)?
root	are we at the root node?
result	pointer to store the result of the separation call