Detailed Description

methods for implications, variable bounds, and clique tables

Author: Tobias Achterberg

Definition in file implics.c.

#include "scip/event.h"
#include "scip/implics.h"
#include "scip/misc.h"
#include "scip/pub_implics.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_var.h"
#include "scip/set.h"
#include "scip/struct_implics.h"
#include "scip/struct_set.h"
#include "scip/struct_stat.h"
#include "scip/var.h"

Go to the source code of this file.

Macros
#define	cliqueCheck(clique)

#define	HASHTABLE_CLIQUETABLE_SIZE 100

#define	checkNEntries(cliquetable) TRUE

Functions
static SCIP_RETCODE	vboundsCreate (SCIP_VBOUNDS *vbounds, BMS_BLKMEM blkmem)

void	SCIPvboundsFree (SCIP_VBOUNDS *vbounds, BMS_BLKMEM blkmem)

static SCIP_RETCODE	vboundsEnsureSize (SCIP_VBOUNDS *vbounds, BMS_BLKMEM blkmem, SCIP_SET *set, int num)

static SCIP_RETCODE	vboundsSearchPos (SCIP_VBOUNDS vbounds, SCIP_VAR var, SCIP_Bool negativecoef, int insertpos, SCIP_Bool found)

SCIP_RETCODE	SCIPvboundsAdd (SCIP_VBOUNDS *vbounds, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_BOUNDTYPE vboundtype, SCIP_VAR var, SCIP_Real coef, SCIP_Real constant, SCIP_Bool *added)

SCIP_RETCODE	SCIPvboundsDel (SCIP_VBOUNDS *vbounds, BMS_BLKMEM blkmem, SCIP_VAR *vbdvar, SCIP_Bool negativecoef)

void	SCIPvboundsShrink (SCIP_VBOUNDS *vbounds, BMS_BLKMEM blkmem, int newnvbds)

static	SCIP_DECL_SORTPTRCOMP (compVars)

static void	checkImplics (SCIP_IMPLICS *implics)

static SCIP_RETCODE	implicsCreate (SCIP_IMPLICS *implics, BMS_BLKMEM blkmem)

void	SCIPimplicsFree (SCIP_IMPLICS *implics, BMS_BLKMEM blkmem)

static SCIP_RETCODE	implicsEnsureSize (SCIP_IMPLICS *implics, BMS_BLKMEM blkmem, SCIP_SET *set, SCIP_Bool varfixing, int num)

static void	implicsSearchVar (SCIP_IMPLICS implics, SCIP_Bool varfixing, SCIP_VAR implvar, int poslower, int posupper, int *posadd)

static SCIP_Bool	implicsSearchImplic (SCIP_IMPLICS implics, SCIP_Bool varfixing, SCIP_VAR implvar, SCIP_BOUNDTYPE impltype, int poslower, int posupper, int *posadd)

SCIP_RETCODE	SCIPimplicsAdd (SCIP_IMPLICS *implics, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_STAT stat, SCIP_Bool varfixing, SCIP_VAR implvar, SCIP_BOUNDTYPE impltype, SCIP_Real implbound, SCIP_Bool isshortcut, SCIP_Bool conflict, SCIP_Bool *added)

SCIP_RETCODE	SCIPimplicsDel (SCIP_IMPLICS *implics, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_Bool varfixing, SCIP_VAR implvar, SCIP_BOUNDTYPE impltype)

void	SCIPimplicsGetVarImplics (SCIP_IMPLICS implics, SCIP_Bool varfixing, SCIP_VAR implvar, SCIP_Bool haslowerimplic, SCIP_Bool hasupperimplic)

SCIP_Bool	SCIPimplicsContainsImpl (SCIP_IMPLICS implics, SCIP_Bool varfixing, SCIP_VAR implvar, SCIP_BOUNDTYPE impltype)

static void	cliquetableSwapCliques (SCIP_CLIQUETABLE *cliquetable, int first, int second)

static void	cliquetableMarkCliqueForCleanup (SCIP_CLIQUETABLE cliquetable, SCIP_CLIQUE clique)

static SCIP_RETCODE	cliqueCreateWithData (SCIP_CLIQUE *clique, BMS_BLKMEM blkmem, int size, SCIP_VAR *vars, SCIP_Bool values, int nvars, int id, SCIP_Bool isequation)

static void	cliqueFree (SCIP_CLIQUE *clique, BMS_BLKMEM blkmem)

static SCIP_RETCODE	cliqueEnsureSize (SCIP_CLIQUE clique, BMS_BLKMEM blkmem, SCIP_SET *set, int num)

int	SCIPcliqueSearchVar (SCIP_CLIQUE clique, SCIP_VAR var, SCIP_Bool value)

SCIP_Bool	SCIPcliqueHasVar (SCIP_CLIQUE clique, SCIP_VAR var, SCIP_Bool value)

SCIP_RETCODE	SCIPcliqueAddVar (SCIP_CLIQUE clique, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_VAR var, SCIP_Bool value, SCIP_Bool doubleentry, SCIP_Bool oppositeentry)

void	SCIPcliqueDelVar (SCIP_CLIQUE clique, SCIP_CLIQUETABLE cliquetable, SCIP_VAR *var, SCIP_Bool value)

static int	cliquesSearchClique (SCIP_CLIQUE *cliques, int ncliques, SCIP_CLIQUE clique)

static SCIP_RETCODE	cliquelistCreate (SCIP_CLIQUELIST *cliquelist, BMS_BLKMEM blkmem)

void	SCIPcliquelistFree (SCIP_CLIQUELIST *cliquelist, BMS_BLKMEM blkmem)

static SCIP_RETCODE	cliquelistEnsureSize (SCIP_CLIQUELIST cliquelist, BMS_BLKMEM blkmem, SCIP_SET *set, SCIP_Bool value, int num)

SCIP_RETCODE	SCIPcliquelistAdd (SCIP_CLIQUELIST *cliquelist, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_Bool value, SCIP_CLIQUE clique)

SCIP_RETCODE	SCIPcliquelistDel (SCIP_CLIQUELIST *cliquelist, BMS_BLKMEM blkmem, SCIP_Bool value, SCIP_CLIQUE *clique)

SCIP_Bool	SCIPcliquelistsHaveCommonClique (SCIP_CLIQUELIST cliquelist1, SCIP_Bool value1, SCIP_CLIQUELIST cliquelist2, SCIP_Bool value2)

void	SCIPcliquelistRemoveFromCliques (SCIP_CLIQUELIST cliquelist, SCIP_CLIQUETABLE cliquetable, SCIP_VAR *var, SCIP_Bool irrelevantvar)

static	SCIP_DECL_HASHGETKEY (hashgetkeyClique)

static	SCIP_DECL_HASHKEYEQ (hashkeyeqClique)

static	SCIP_DECL_HASHKEYVAL (hashkeyvalClique)

SCIP_RETCODE	SCIPcliquetableCreate (SCIP_CLIQUETABLE *cliquetable, SCIP_SET set, BMS_BLKMEM *blkmem)

SCIP_RETCODE	SCIPcliquetableFree (SCIP_CLIQUETABLE *cliquetable, BMS_BLKMEM blkmem)

static SCIP_RETCODE	cliquetableEnsureSize (SCIP_CLIQUETABLE cliquetable, SCIP_SET set, int num)

static SCIP_RETCODE	sortAndMergeClique (SCIP_VAR *clqvars, SCIP_Bool clqvalues, int nclqvars, SCIP_Bool isequation, SCIP_CLIQUE clique, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_STAT stat, SCIP_PROB transprob, SCIP_PROB origprob, SCIP_TREE tree, SCIP_REOPT reopt, SCIP_LP lp, SCIP_BRANCHCAND branchcand, SCIP_EVENTQUEUE eventqueue, SCIP_CLIQUETABLE cliquetable, int nbdchgs, SCIP_Bool infeasible)

static int	cliquetableGetNodeIndexBinvar (SCIP_CLIQUETABLE cliquetable, SCIP_VAR binvar)

static void	cliquetableUpdateConnectednessClique (SCIP_CLIQUETABLE cliquetable, SCIP_CLIQUE clique)

int	SCIPcliquetableGetVarComponentIdx (SCIP_CLIQUETABLE cliquetable, SCIP_VAR var)

SCIP_RETCODE	SCIPcliquetableAdd (SCIP_CLIQUETABLE cliquetable, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_STAT stat, SCIP_PROB transprob, SCIP_PROB origprob, SCIP_TREE tree, SCIP_REOPT reopt, SCIP_LP lp, SCIP_BRANCHCAND branchcand, SCIP_EVENTQUEUE eventqueue, SCIP_VAR vars, SCIP_Bool values, int nvars, SCIP_Bool isequation, SCIP_Bool infeasible, int nbdchgs)

static SCIP_RETCODE	cliqueCleanup (SCIP_CLIQUE clique, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_STAT stat, SCIP_PROB transprob, SCIP_PROB origprob, SCIP_TREE tree, SCIP_REOPT reopt, SCIP_LP lp, SCIP_BRANCHCAND branchcand, SCIP_EVENTQUEUE eventqueue, SCIP_CLIQUETABLE cliquetable, int nchgbds, SCIP_Bool infeasible)

SCIP_RETCODE	SCIPcliquetableCleanup (SCIP_CLIQUETABLE cliquetable, BMS_BLKMEM blkmem, SCIP_SET set, SCIP_STAT stat, SCIP_PROB transprob, SCIP_PROB origprob, SCIP_TREE tree, SCIP_REOPT reopt, SCIP_LP lp, SCIP_BRANCHCAND branchcand, SCIP_EVENTQUEUE eventqueue, int nchgbds, SCIP_Bool *infeasible)

SCIP_RETCODE	SCIPcliquetableComputeCliqueComponents (SCIP_CLIQUETABLE cliquetable, SCIP_SET set, BMS_BLKMEM blkmem, SCIP_VAR *vars, int nbinvars, int nintvars, int nimplvars)

int	SCIPvboundsGetNVbds (SCIP_VBOUNDS *vbounds)

SCIP_VAR **	SCIPvboundsGetVars (SCIP_VBOUNDS *vbounds)

SCIP_Real *	SCIPvboundsGetCoefs (SCIP_VBOUNDS *vbounds)

SCIP_Real *	SCIPvboundsGetConstants (SCIP_VBOUNDS *vbounds)

int	SCIPimplicsGetNImpls (SCIP_IMPLICS *implics, SCIP_Bool varfixing)

SCIP_VAR **	SCIPimplicsGetVars (SCIP_IMPLICS *implics, SCIP_Bool varfixing)

SCIP_BOUNDTYPE *	SCIPimplicsGetTypes (SCIP_IMPLICS *implics, SCIP_Bool varfixing)

SCIP_Real *	SCIPimplicsGetBounds (SCIP_IMPLICS *implics, SCIP_Bool varfixing)

int *	SCIPimplicsGetIds (SCIP_IMPLICS *implics, SCIP_Bool varfixing)

int	SCIPcliqueGetNVars (SCIP_CLIQUE *clique)

SCIP_VAR **	SCIPcliqueGetVars (SCIP_CLIQUE *clique)

SCIP_Bool *	SCIPcliqueGetValues (SCIP_CLIQUE *clique)

unsigned int	SCIPcliqueGetId (SCIP_CLIQUE *clique)

int	SCIPcliqueGetIndex (SCIP_CLIQUE *clique)

SCIP_Bool	SCIPcliqueIsCleanedUp (SCIP_CLIQUE *clique)

SCIP_Bool	SCIPcliqueIsEquation (SCIP_CLIQUE *clique)

int	SCIPcliquelistGetNCliques (SCIP_CLIQUELIST *cliquelist, SCIP_Bool value)

SCIP_CLIQUE **	SCIPcliquelistGetCliques (SCIP_CLIQUELIST *cliquelist, SCIP_Bool value)

void	SCIPcliquelistCheck (SCIP_CLIQUELIST cliquelist, SCIP_VAR var)

int	SCIPcliquetableGetNCliques (SCIP_CLIQUETABLE *cliquetable)

int	SCIPcliquetableGetNCliquesCreated (SCIP_CLIQUETABLE *cliquetable)

SCIP_CLIQUE **	SCIPcliquetableGetCliques (SCIP_CLIQUETABLE *cliquetable)

SCIP_Longint	SCIPcliquetableGetNEntries (SCIP_CLIQUETABLE *cliquetable)

int	SCIPcliquetableGetNCliqueComponents (SCIP_CLIQUETABLE *cliquetable)

SCIP_Bool	SCIPcliquetableNeedsComponentUpdate (SCIP_CLIQUETABLE *cliquetable)

Macro Definition Documentation

◆ cliqueCheck

#define cliqueCheck ( clique )

Definition at line 1390 of file implics.c.

Referenced by cliquesSearchClique(), SCIPcliquelistRemoveFromCliques(), SCIPcliquetableAdd(), and SCIPcliquetableCleanup().

◆ HASHTABLE_CLIQUETABLE_SIZE

#define HASHTABLE_CLIQUETABLE_SIZE 100

Definition at line 1758 of file implics.c.

Referenced by SCIPcliquetableCreate().

◆ checkNEntries

#define checkNEntries ( cliquetable ) TRUE

Definition at line 2874 of file implics.c.

Referenced by cliqueCleanup(), and SCIPcliquetableCleanup().

Function Documentation

◆ vboundsCreate()

static SCIP_RETCODE vboundsCreate	(	SCIP_VBOUNDS **	vbounds,
		BMS_BLKMEM *	blkmem
	)

static

creates a variable bounds data structure

Parameters

vbounds	pointer to store variable bounds data structure
blkmem	block memory

Definition at line 45 of file implics.c.

References BMSallocBlockMemory, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by vboundsEnsureSize().

◆ SCIPvboundsFree()

void SCIPvboundsFree	(	SCIP_VBOUNDS **	vbounds,
		BMS_BLKMEM *	blkmem
	)

frees a variable bounds data structure

Parameters

vbounds	pointer to store variable bounds data structure
blkmem	block memory

Definition at line 63 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

Referenced by SCIPvarAggregate(), SCIPvarRemove(), SCIPvboundsDel(), SCIPvboundsShrink(), and varFree().

◆ vboundsEnsureSize()

static SCIP_RETCODE vboundsEnsureSize	(	SCIP_VBOUNDS **	vbounds,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		int	num
	)

static

ensures, that variable bounds arrays can store at least num entries

Parameters

vbounds	pointer to variable bounds data structure
blkmem	block memory
set	global SCIP settings
num	minimum number of entries to store

Definition at line 81 of file implics.c.

References BMSreallocBlockMemoryArray, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIPsetCalcMemGrowSize(), and vboundsCreate().

Referenced by SCIPvboundsAdd().

◆ vboundsSearchPos()

static SCIP_RETCODE vboundsSearchPos	(	SCIP_VBOUNDS *	vbounds,
		SCIP_VAR *	var,
		SCIP_Bool	negativecoef,
		int *	insertpos,
		SCIP_Bool *	found
	)

static

binary searches the insertion position of the given variable in the vbounds data structure

Parameters

vbounds	variable bounds data structure, or NULL
var	variable to search in vbounds data structure
negativecoef	is coefficient b negative?
insertpos	pointer to store position where to insert new entry
found	pointer to store whether the same variable was found at the returned pos

Definition at line 115 of file implics.c.

References SCIP_VBounds::coefs, FALSE, SCIP_VBounds::len, NULL, SCIP_Bool, SCIP_OKAY, SCIPsortedvecFindPtr(), TRUE, and SCIP_VBounds::vars.

Referenced by SCIPvboundsAdd(), and SCIPvboundsDel().

◆ SCIPvboundsAdd()

SCIP_RETCODE SCIPvboundsAdd	(	SCIP_VBOUNDS **	vbounds,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_BOUNDTYPE	vboundtype,
		SCIP_VAR *	var,
		SCIP_Real	coef,
		SCIP_Real	constant,
		SCIP_Bool *	added
	)

adds a variable bound to the variable bounds data structure

Parameters

vbounds	pointer to variable bounds data structure
blkmem	block memory
set	global SCIP settings
vboundtype	type of variable bound (LOWER or UPPER)
var	variable z in x <= bz + d or x >= bz + d
coef	coefficient b in x <= bz + d or x >= bz + d
constant	constant d in x <= bz + d or x >= bz + d
added	pointer to store whether the variable bound was added

Definition at line 196 of file implics.c.

References FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIP_VARTYPE_CONTINUOUS, SCIPsetIsZero(), SCIPvarGetStatus(), SCIPvarGetType(), TRUE, vboundsEnsureSize(), and vboundsSearchPos().

Referenced by varAddVbound().

◆ SCIPvboundsDel()

SCIP_RETCODE SCIPvboundsDel	(	SCIP_VBOUNDS **	vbounds,
		BMS_BLKMEM *	blkmem,
		SCIP_VAR *	vbdvar,
		SCIP_Bool	negativecoef
	)

removes from variable x a variable bound x >=/<= b*z + d with binary or integer z

Parameters

vbounds	pointer to variable bounds data structure
blkmem	block memory
vbdvar	variable z in x >=/<= b*z + d
negativecoef	is coefficient b negative?

Definition at line 278 of file implics.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPvboundsFree(), and vboundsSearchPos().

Referenced by SCIPvarRemoveCliquesImplicsVbs().

◆ SCIPvboundsShrink()

void SCIPvboundsShrink	(	SCIP_VBOUNDS **	vbounds,
		BMS_BLKMEM *	blkmem,
		int	newnvbds
	)

reduces the number of variable bounds stored in the given variable bounds data structure

Parameters

vbounds	pointer to variable bounds data structure
blkmem	block memory
newnvbds	new number of variable bounds

Definition at line 323 of file implics.c.

References NULL, and SCIPvboundsFree().

Referenced by SCIPvarRemoveCliquesImplicsVbs().

◆ SCIP_DECL_SORTPTRCOMP()

static SCIP_DECL_SORTPTRCOMP ( compVars )

static

comparator function for implication variables in the implication data structure

Definition at line 349 of file implics.c.

References NULL, and SCIPvarGetIndex().

◆ checkImplics()

static void checkImplics ( SCIP_IMPLICS * implics )

static

performs integrity check on implications data structure

Parameters

implics implications data structure

Definition at line 373 of file implics.c.

References FALSE, SCIP_Implics::nimpls, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, TRUE, SCIP_Implics::types, and SCIP_Implics::vars.

Referenced by SCIPimplicsAdd(), and SCIPimplicsDel().

◆ implicsCreate()

static SCIP_RETCODE implicsCreate	(	SCIP_IMPLICS **	implics,
		BMS_BLKMEM *	blkmem
	)

static

creates an implications data structure

Parameters

implics	pointer to store implications data structure
blkmem	block memory

Definition at line 415 of file implics.c.

References BMSallocBlockMemory, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by implicsEnsureSize().

◆ SCIPimplicsFree()

void SCIPimplicsFree	(	SCIP_IMPLICS **	implics,
		BMS_BLKMEM *	blkmem
	)

frees an implications data structure

Parameters

implics	pointer of implications data structure to free
blkmem	block memory

Definition at line 441 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

Referenced by SCIPimplicsDel(), SCIPvarAggregate(), SCIPvarRemove(), SCIPvarRemoveCliquesImplicsVbs(), and varFree().

◆ implicsEnsureSize()

static SCIP_RETCODE implicsEnsureSize	(	SCIP_IMPLICS **	implics,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_Bool	varfixing,
		int	num
	)

static

ensures, that arrays for x == 0 or x == 1 in implications data structure can store at least num entries

Parameters

implics	pointer to implications data structure
blkmem	block memory
set	global SCIP settings
varfixing	FALSE if size of arrays for x == 0 has to be ensured, TRUE for x == 1
num	minimum number of entries to store

Definition at line 464 of file implics.c.

References BMSreallocBlockMemoryArray, implicsCreate(), NULL, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, and SCIPsetCalcMemGrowSize().

Referenced by SCIPimplicsAdd().

◆ implicsSearchVar()

static void implicsSearchVar	(	SCIP_IMPLICS *	implics,
		SCIP_Bool	varfixing,
		SCIP_VAR *	implvar,
		int *	poslower,
		int *	posupper,
		int *	posadd
	)

static

gets the positions of the implications y >= l and y <= u in the implications data structure; if no lower or upper bound implication for y was found, -1 is returned

Parameters

implics	implications data structure
varfixing	FALSE if y is searched in implications for x == 0, TRUE for x == 1
implvar	variable y to search for
poslower	pointer to store position of y_lower (-1 if not found)
posupper	pointer to store position of y_upper (-1 if not found)
posadd	pointer to store position of first y entry, or where a new y entry should be placed

Definition at line 502 of file implics.c.

References SCIP_Implics::nimpls, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIPsortedvecFindPtr(), SCIP_Implics::types, and SCIP_Implics::vars.

Referenced by implicsSearchImplic(), and SCIPimplicsGetVarImplics().

◆ implicsSearchImplic()

static SCIP_Bool implicsSearchImplic	(	SCIP_IMPLICS *	implics,
		SCIP_Bool	varfixing,
		SCIP_VAR *	implvar,
		SCIP_BOUNDTYPE	impltype,
		int *	poslower,
		int *	posupper,
		int *	posadd
	)

static

returns whether variable y is already contained in implications for x == 0 or x == 1 with the given impltype y can be contained in structure with y >= b (y_lower) and y <= b (y_upper)

Parameters

implics	implications data structure
varfixing	FALSE if y is searched in implications for x == 0, TRUE for x == 1
implvar	variable y to search for
impltype	type of implication y <=/>= b to search for
poslower	pointer to store position of y_lower (inf if not found)
posupper	pointer to store position of y_upper (inf if not found)
posadd	pointer to store correct position (with respect to impltype) to add y

Definition at line 586 of file implics.c.

References implicsSearchVar(), NULL, and SCIP_BOUNDTYPE_LOWER.

Referenced by SCIPimplicsAdd(), SCIPimplicsContainsImpl(), and SCIPimplicsDel().

◆ SCIPimplicsAdd()

SCIP_RETCODE SCIPimplicsAdd	(	SCIP_IMPLICS **	implics,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_Bool	varfixing,
		SCIP_VAR *	implvar,
		SCIP_BOUNDTYPE	impltype,
		SCIP_Real	implbound,
		SCIP_Bool	isshortcut,
		SCIP_Bool *	conflict,
		SCIP_Bool *	added
	)

adds an implication x == 0/1 -> y <= b or y >= b to the implications data structure; the implication must be non-redundant

Parameters

implics	pointer to implications data structure
blkmem	block memory
set	global SCIP settings
stat	problem statistics
varfixing	FALSE if implication for x == 0 has to be added, TRUE for x == 1
implvar	variable y in implication y <= b or y >= b
impltype	type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER)
implbound	bound b in implication y <= b or y >= b
isshortcut	is the implication a shortcut, i.e., added as part of the transitive closure of another implication?
conflict	pointer to store whether implication causes a conflict for variable x
added	pointer to store whether the implication was added

Definition at line 623 of file implics.c.

References BMSmoveMemoryArray, checkImplics(), FALSE, implicsEnsureSize(), implicsSearchImplic(), SCIP_Stat::nimplications, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIPsetDebugMsg, SCIPsetIsFeasGE(), SCIPsetIsFeasGT(), SCIPsetIsFeasLE(), SCIPsetIsFeasLT(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), and TRUE.

Referenced by varAddImplic().

◆ SCIPimplicsDel()

SCIP_RETCODE SCIPimplicsDel	(	SCIP_IMPLICS **	implics,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_Bool	varfixing,
		SCIP_VAR *	implvar,
		SCIP_BOUNDTYPE	impltype
	)

removes the implication x <= 0 or x >= 1 ==> y <= b or y >= b from the implications data structure

Parameters

implics	pointer to implications data structure
blkmem	block memory
set	global SCIP settings
varfixing	FALSE if y should be removed from implications for x <= 0, TRUE for x >= 1
implvar	variable y in implication y <= b or y >= b
impltype	type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER)

Definition at line 826 of file implics.c.

References BMSmoveMemoryArray, checkImplics(), implicsSearchImplic(), NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_OKAY, SCIPimplicsFree(), SCIPsetDebugMsg, and SCIPvarGetName().

Referenced by SCIPvarRemoveCliquesImplicsVbs().

◆ SCIPimplicsGetVarImplics()

void SCIPimplicsGetVarImplics	(	SCIP_IMPLICS *	implics,
		SCIP_Bool	varfixing,
		SCIP_VAR *	implvar,
		SCIP_Bool *	haslowerimplic,
		SCIP_Bool *	hasupperimplic
	)

returns which implications on given variable y are contained in implications for x == 0 or x == 1

Parameters

implics	implications data structure
varfixing	FALSE if y should be searched in implications for x == 0, TRUE for x == 1
implvar	variable y to search for
haslowerimplic	pointer to store whether there exists an implication y >= l
hasupperimplic	pointer to store whether there exists an implication y <= u

Definition at line 884 of file implics.c.

References implicsSearchVar(), and NULL.

◆ SCIPimplicsContainsImpl()

SCIP_Bool SCIPimplicsContainsImpl	(	SCIP_IMPLICS *	implics,
		SCIP_Bool	varfixing,
		SCIP_VAR *	implvar,
		SCIP_BOUNDTYPE	impltype
	)

returns whether an implication y <= b or y >= b is contained in implications for x == 0 or x == 1

Parameters

implics	implications data structure
varfixing	FALSE if y should be searched in implications for x == 0, TRUE for x == 1
implvar	variable y to search for
impltype	type of implication y <=/>= b to search for

Definition at line 906 of file implics.c.

References implicsSearchImplic().

Referenced by SCIPvarHasImplic().

◆ cliquetableSwapCliques()

static void cliquetableSwapCliques	(	SCIP_CLIQUETABLE *	cliquetable,
		int	first,
		int	second
	)

static

Parameters

cliquetable	clique table data structure
first	first index
second	second index

Definition at line 929 of file implics.c.

References SCIP_CliqueTable::cliques, and SCIP_Clique::index.

Referenced by cliquetableMarkCliqueForCleanup(), and SCIPcliquetableCleanup().

◆ cliquetableMarkCliqueForCleanup()

static void cliquetableMarkCliqueForCleanup	(	SCIP_CLIQUETABLE *	cliquetable,
		SCIP_CLIQUE *	clique
	)

static

Parameters

cliquetable	clique table data structure
clique	clique data structure

Definition at line 955 of file implics.c.

References SCIP_CliqueTable::cliques, cliquetableSwapCliques(), SCIP_Clique::index, SCIP_CliqueTable::ncliques, SCIP_CliqueTable::ndirtycliques, and SCIPcliqueIsCleanedUp().

Referenced by SCIPcliqueDelVar().

◆ cliqueCreateWithData()

static SCIP_RETCODE cliqueCreateWithData	(	SCIP_CLIQUE **	clique,
		BMS_BLKMEM *	blkmem,
		int	size,
		SCIP_VAR **	vars,
		SCIP_Bool *	values,
		int	nvars,
		int	id,
		SCIP_Bool	isequation
	)

static

creates a clique data structure with already created variables and values arrays in the size of 'size'

Parameters

clique	pointer to store clique data structure
blkmem	block memory
size	initial size of clique
vars	binary variables in the clique: at most one can be set to the given value
values	values of the variables in the clique
nvars	number of variables in the clique
id	unique identifier of the clique
isequation	is the clique an equation or an inequality?

Definition at line 977 of file implics.c.

References BMSallocBlockMemory, BMSduplicateBlockMemoryArray, FALSE, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by SCIPcliquetableAdd().

◆ cliqueFree()

static void cliqueFree	(	SCIP_CLIQUE **	clique,
		BMS_BLKMEM *	blkmem
	)

static

frees a clique data structure

Parameters

clique	pointer to store clique data structure
blkmem	block memory

Definition at line 1011 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

Referenced by SCIPcliquetableAdd(), SCIPcliquetableCleanup(), and SCIPcliquetableFree().

◆ cliqueEnsureSize()

static SCIP_RETCODE cliqueEnsureSize	(	SCIP_CLIQUE *	clique,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		int	num
	)

static

ensures, that clique arrays can store at least num entries

Parameters

clique	clique data structure
blkmem	block memory
set	global SCIP settings
num	minimum number of entries to store

Definition at line 1028 of file implics.c.

References BMSreallocBlockMemoryArray, NULL, SCIP_ALLOC, SCIP_OKAY, SCIPsetCalcMemGrowSize(), SCIP_Clique::size, SCIP_Clique::values, and SCIP_Clique::vars.

Referenced by SCIPcliqueAddVar().

◆ SCIPcliqueSearchVar()

int SCIPcliqueSearchVar	(	SCIP_CLIQUE *	clique,
		SCIP_VAR *	var,
		SCIP_Bool	value
	)

returns the position of the given variable/value pair in the clique; returns -1 if variable/value pair is not member of the clique

Parameters

clique	clique data structure
var	variable to search for
value	value of the variable in the clique

Definition at line 1054 of file implics.c.

References NULL, SCIP_Clique::nvars, SCIPvarGetIndex(), SCIP_Clique::values, and SCIP_Clique::vars.

Referenced by SCIPcliqueDelVar(), SCIPcliqueHasVar(), and SCIPcliquelistCheck().

◆ SCIPcliqueHasVar()

SCIP_Bool SCIPcliqueHasVar	(	SCIP_CLIQUE *	clique,
		SCIP_VAR *	var,
		SCIP_Bool	value
	)

returns whether the given variable/value pair is member of the given clique

Parameters

clique	clique data structure
var	variable to remove from the clique
value	value of the variable in the clique

Definition at line 1114 of file implics.c.

References SCIPcliqueSearchVar().

◆ SCIPcliqueAddVar()

SCIP_RETCODE SCIPcliqueAddVar	(	SCIP_CLIQUE *	clique,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_VAR *	var,
		SCIP_Bool	value,
		SCIP_Bool *	doubleentry,
		SCIP_Bool *	oppositeentry
	)

adds a single variable to the given clique

Parameters

clique	clique data structure
blkmem	block memory
set	global SCIP settings
var	variable to add to the clique
value	value of the variable in the clique
doubleentry	pointer to store whether the variable and value occurs twice in the clique
oppositeentry	pointer to store whether the variable with opposite value is in the clique

Definition at line 1124 of file implics.c.

References BMSmoveMemoryArray, cliqueEnsureSize(), SCIP_Clique::eventsissued, FALSE, SCIP_Clique::id, NULL, SCIP_Clique::nvars, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIPsetDebugMsg, SCIPsortedvecFindPtr(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarIsBinary(), TRUE, SCIP_Clique::values, and SCIP_Clique::vars.

Referenced by SCIPvarAddClique().

◆ SCIPcliqueDelVar()

void SCIPcliqueDelVar	(	SCIP_CLIQUE *	clique,
		SCIP_CLIQUETABLE *	cliquetable,
		SCIP_VAR *	var,
		SCIP_Bool	value
	)

removes a single variable from the given clique

Parameters

clique	clique data structure
cliquetable	clique table data structure
var	variable to remove from the clique
value	value of the variable in the clique

Definition at line 1258 of file implics.c.

References cliquetableMarkCliqueForCleanup(), SCIP_Clique::id, SCIP_CliqueTable::incleanup, SCIP_Clique::index, NULL, SCIPcliqueSearchVar(), SCIPdebugMessage, SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIP_Clique::startcleanup, SCIP_Clique::values, and SCIP_Clique::vars.

Referenced by SCIPcliquelistRemoveFromCliques(), and SCIPvarDelClique().

◆ cliquesSearchClique()

static int cliquesSearchClique	(	SCIP_CLIQUE **	cliques,
		int	ncliques,
		SCIP_CLIQUE *	clique
	)

static

gets the position of the given clique in the cliques array; returns -1 if clique is not member of cliques array

Parameters

cliques	array of cliques
ncliques	number of cliques in the cliques array
clique	clique to search for

Definition at line 1306 of file implics.c.

References cliqueCheck, SCIP_Clique::id, SCIP_Clique::index, NULL, SCIP_Clique::nvars, SCIPvarGetCliques(), SCIPvarGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetNCliques(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIP_Clique::startcleanup, SCIP_Clique::values, and SCIP_Clique::vars.

Referenced by SCIPcliquelistDel().

◆ cliquelistCreate()

static SCIP_RETCODE cliquelistCreate	(	SCIP_CLIQUELIST **	cliquelist,
		BMS_BLKMEM *	blkmem
	)

static

creates a clique list data structure

Parameters

cliquelist	pointer to store clique list data structure
blkmem	block memory

Definition at line 1395 of file implics.c.

References BMSallocBlockMemory, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by SCIPcliquelistAdd().

◆ SCIPcliquelistFree()

void SCIPcliquelistFree	(	SCIP_CLIQUELIST **	cliquelist,
		BMS_BLKMEM *	blkmem
	)

frees a clique list data structure

Parameters

cliquelist	pointer to the clique list data structure
blkmem	block memory

Definition at line 1414 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

Referenced by SCIPcliquelistDel(), SCIPvarRemoveCliquesImplicsVbs(), and varFree().

◆ cliquelistEnsureSize()

static SCIP_RETCODE cliquelistEnsureSize	(	SCIP_CLIQUELIST *	cliquelist,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_Bool	value,
		int	num
	)

static

ensures, that clique list arrays can store at least num entries

Parameters

cliquelist	clique list data structure
blkmem	block memory
set	global SCIP settings
value	value of the variable for which the clique list should be extended
num	minimum number of entries to store

Definition at line 1431 of file implics.c.

References BMSreallocBlockMemoryArray, SCIP_CliqueList::cliques, NULL, SCIP_ALLOC, SCIP_OKAY, SCIPsetCalcMemGrowSize(), and SCIP_CliqueList::size.

Referenced by SCIPcliquelistAdd().

◆ SCIPcliquelistAdd()

SCIP_RETCODE SCIPcliquelistAdd	(	SCIP_CLIQUELIST **	cliquelist,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_Bool	value,
		SCIP_CLIQUE *	clique
	)

adds a clique to the clique list

Parameters

cliquelist	pointer to the clique list data structure
blkmem	block memory
set	global SCIP settings
value	value of the variable for which the clique list should be extended
clique	clique that should be added to the clique list

Definition at line 1455 of file implics.c.

References BMSmoveMemoryArray, cliquelistCreate(), cliquelistEnsureSize(), SCIP_Clique::id, SCIP_CliqueList::ncliques, NULL, SCIP_CALL, SCIP_OKAY, and SCIPsetDebugMsg.

Referenced by SCIPvarAddClique(), SCIPvarAddCliqueToList(), and SCIPvarsAddClique().

◆ SCIPcliquelistDel()

SCIP_RETCODE SCIPcliquelistDel	(	SCIP_CLIQUELIST **	cliquelist,
		BMS_BLKMEM *	blkmem,
		SCIP_Bool	value,
		SCIP_CLIQUE *	clique
	)

removes a clique from the clique list

Parameters

cliquelist	pointer to the clique list data structure
blkmem	block memory
value	value of the variable for which the clique list should be reduced
clique	clique that should be deleted from the clique list

Definition at line 1500 of file implics.c.

References BMSduplicateBlockMemoryArray, BMSfreeBlockMemoryArray, BMSmoveMemoryArray, cliquesSearchClique(), SCIP_Clique::id, SCIP_CliqueList::ncliques, NULL, SCIP_ALLOC, SCIP_Bool, SCIP_OKAY, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPcliquelistFree(), SCIPdebugMessage, and SCIPsortPtrBool().

Referenced by SCIPvarDelClique(), and SCIPvarDelCliqueFromList().

◆ SCIPcliquelistsHaveCommonClique()

SCIP_Bool SCIPcliquelistsHaveCommonClique	(	SCIP_CLIQUELIST *	cliquelist1,
		SCIP_Bool	value1,
		SCIP_CLIQUELIST *	cliquelist2,
		SCIP_Bool	value2
	)

returns whether the given clique lists have a non-empty intersection, i.e. whether there is a clique that appears in both lists

Parameters

cliquelist1	first clique list data structure
value1	value of first variable
cliquelist2	second clique list data structure
value2	value of second variable

Definition at line 1578 of file implics.c.

References SCIP_CliqueList::cliques, FALSE, SCIP_CliqueList::ncliques, NULL, SCIPcliqueGetId(), and TRUE.

Referenced by SCIPvarsHaveCommonClique().

◆ SCIPcliquelistRemoveFromCliques()

void SCIPcliquelistRemoveFromCliques	(	SCIP_CLIQUELIST *	cliquelist,
		SCIP_CLIQUETABLE *	cliquetable,
		SCIP_VAR *	var,
		SCIP_Bool	irrelevantvar
	)

removes all listed entries from the cliques

Parameters

cliquelist	clique list data structure
cliquetable	clique table data structure
var	active problem variable the clique list belongs to
irrelevantvar	has the variable become irrelevant, meaning that equality cliques need to be relaxed?

Definition at line 1656 of file implics.c.

References cliqueCheck, SCIP_CliqueList::cliques, SCIP_Clique::equation, FALSE, SCIP_Clique::id, SCIP_CliqueTable::incleanup, SCIP_Clique::index, SCIP_CliqueList::ncliques, NULL, SCIP_Clique::nvars, SCIP_Bool, SCIPcliqueDelVar(), SCIPdebugMessage, SCIPvarGetCliques(), SCIPvarGetName(), SCIPvarGetNCliques(), and SCIPvarIsBinary().

Referenced by SCIPvarRemoveCliquesImplicsVbs().

◆ SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( hashgetkeyClique )

static

gets the key of the given element

Definition at line 1712 of file implics.c.

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashkeyeqClique )

static

returns TRUE iff both keys are equal

Definition at line 1719 of file implics.c.

References FALSE, NULL, SCIP_Clique::nvars, TRUE, SCIP_Clique::values, and SCIP_Clique::vars.

◆ SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashkeyvalClique )

static

returns the hash value of the key

Definition at line 1745 of file implics.c.

References SCIP_Clique::nvars, SCIPcombineThreeInt, SCIPcombineTwoInt, SCIPhashTwo, SCIPvarGetIndex(), SCIP_Clique::values, and SCIP_Clique::vars.

◆ SCIPcliquetableCreate()

SCIP_RETCODE SCIPcliquetableCreate	(	SCIP_CLIQUETABLE **	cliquetable,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem
	)

creates a clique table data structure

Parameters

cliquetable	pointer to store clique table data structure
set	global SCIP settings
blkmem	block memory

Definition at line 1761 of file implics.c.

References BMSallocMemory, FALSE, HASHTABLE_CLIQUETABLE_SIZE, MAX, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_HASHSIZE_CLIQUES, SCIP_HASHSIZE_CLIQUES_SMALL, SCIP_OKAY, and SCIPhashtableCreate().

Referenced by SCIPtransformProb().

◆ SCIPcliquetableFree()

SCIP_RETCODE SCIPcliquetableFree	(	SCIP_CLIQUETABLE **	cliquetable,
		BMS_BLKMEM *	blkmem
	)

frees a clique table data structure

Parameters

cliquetable	pointer to store clique table data structure
blkmem	block memory

Definition at line 1797 of file implics.c.

References BMSfreeMemory, BMSfreeMemoryArrayNull, cliqueFree(), NULL, SCIP_OKAY, SCIPdisjointsetFree(), SCIPhashmapFree(), and SCIPhashtableFree().

Referenced by freeTransform().

◆ cliquetableEnsureSize()

static SCIP_RETCODE cliquetableEnsureSize	(	SCIP_CLIQUETABLE *	cliquetable,
		SCIP_SET *	set,
		int	num
	)

static

ensures, that clique table arrays can store at least num entries

Parameters

cliquetable	clique table data structure
set	global SCIP settings
num	minimum number of entries to store

Definition at line 1834 of file implics.c.

References BMSreallocMemoryArray, SCIP_CliqueTable::cliques, NULL, SCIP_ALLOC, SCIP_OKAY, SCIPsetCalcMemGrowSize(), and SCIP_CliqueTable::size.

Referenced by SCIPcliquetableAdd().

◆ sortAndMergeClique()

static SCIP_RETCODE sortAndMergeClique	(	SCIP_VAR **	clqvars,
		SCIP_Bool *	clqvalues,
		int *	nclqvars,
		SCIP_Bool *	isequation,
		SCIP_CLIQUE *	clique,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PROB *	transprob,
		SCIP_PROB *	origprob,
		SCIP_TREE *	tree,
		SCIP_REOPT *	reopt,
		SCIP_LP *	lp,
		SCIP_BRANCHCAND *	branchcand,
		SCIP_EVENTQUEUE *	eventqueue,
		SCIP_CLIQUETABLE *	cliquetable,
		int *	nbdchgs,
		SCIP_Bool *	infeasible
	)

static

sort variables regarding their index and remove multiple entries of the same variable

Parameters

clqvars	variables of a clique
clqvalues	clique values, active or negated, for the variables in a clique
nclqvars	number of clique variables
isequation	do we have an equation clique at hand?
clique	clique data structure or NULL
blkmem	block memory
set	global SCIP settings
stat	problem statistics
transprob	transformed problem
origprob	original problem
tree	branch and bound tree if in solving stage
reopt	reoptimization data structure
lp	current LP data
branchcand	branching candidate storage
eventqueue	event queue
cliquetable	clique table data structure
nbdchgs	pointer to store number of fixed variables
infeasible	pointer to store whether an infeasibility was detected

Definition at line 1857 of file implics.c.

References FALSE, SCIP_Clique::id, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIPsetDebugMsg, SCIPsortPtrBool(), SCIPvarDelCliqueFromList(), SCIPvarFixBinary(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), TRUE, and w.

Referenced by cliqueCleanup(), and SCIPcliquetableAdd().

◆ cliquetableGetNodeIndexBinvar()

static int cliquetableGetNodeIndexBinvar	(	SCIP_CLIQUETABLE *	cliquetable,
		SCIP_VAR *	binvar
	)

static

helper function that returns the graph node index for a variable during connected component detection

Parameters

cliquetable	clique table data structure
binvar	binary (or binary integer or implicit binary) variable

Definition at line 2235 of file implics.c.

References SCIP_CliqueTable::compsfromscratch, NULL, SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPvarGetProbvar(), SCIPvarIsActive(), SCIPvarIsBinary(), TRUE, and SCIP_CliqueTable::varidxtable.

Referenced by cliquetableUpdateConnectednessClique(), and SCIPcliquetableGetVarComponentIdx().

◆ cliquetableUpdateConnectednessClique()

static void cliquetableUpdateConnectednessClique	(	SCIP_CLIQUETABLE *	cliquetable,
		SCIP_CLIQUE *	clique
	)

static

updates connectedness information for the clique

Parameters

cliquetable	clique table data structure
clique	clique that should be added

Definition at line 2278 of file implics.c.

References cliquetableGetNodeIndexBinvar(), SCIP_CliqueTable::compsfromscratch, SCIP_CliqueTable::djset, FALSE, NULL, SCIP_Clique::nvars, SCIPdisjointsetUnion(), TRUE, and SCIP_Clique::vars.

Referenced by SCIPcliquetableAdd(), and SCIPcliquetableComputeCliqueComponents().

◆ SCIPcliquetableGetVarComponentIdx()

int SCIPcliquetableGetVarComponentIdx	(	SCIP_CLIQUETABLE *	cliquetable,
		SCIP_VAR *	var
	)

returns the index of the connected component of the clique graph that the variable belongs to, or -1

Parameters

cliquetable	clique table data structure
var	problem variable

Definition at line 2322 of file implics.c.

References cliquetableGetNodeIndexBinvar(), SCIP_CliqueTable::djset, NULL, SCIPdisjointsetFind(), SCIPdisjointsetGetSize(), and SCIPvarIsBinary().

Referenced by SCIPcalcCliquePartition().

◆ SCIPcliquetableAdd()

SCIP_RETCODE SCIPcliquetableAdd	(	SCIP_CLIQUETABLE *	cliquetable,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PROB *	transprob,
		SCIP_PROB *	origprob,
		SCIP_TREE *	tree,
		SCIP_REOPT *	reopt,
		SCIP_LP *	lp,
		SCIP_BRANCHCAND *	branchcand,
		SCIP_EVENTQUEUE *	eventqueue,
		SCIP_VAR **	vars,
		SCIP_Bool *	values,
		int	nvars,
		SCIP_Bool	isequation,
		SCIP_Bool *	infeasible,
		int *	nbdchgs
	)

adds a clique to the clique table, using the given values for the given variables; performs implications if the clique contains the same variable twice

Parameters

cliquetable	clique table data structure
blkmem	block memory
set	global SCIP settings
stat	problem statistics
transprob	transformed problem
origprob	original problem
tree	branch and bound tree if in solving stage
reopt	reoptimization data structure
lp	current LP data
branchcand	branching candidate storage
eventqueue	event queue
vars	binary variables in the clique: at most one can be set to the given value
values	values of the variables in the clique; NULL to use TRUE for all vars
nvars	number of variables in the clique
isequation	is the clique an equation or an inequality?
infeasible	pointer to store whether an infeasibility was detected
nbdchgs	pointer to count the number of performed bound changes, or NULL

Definition at line 2350 of file implics.c.

References cliqueCheck, cliqueCreateWithData(), cliqueFree(), SCIP_CliqueTable::cliques, cliquetableEnsureSize(), cliquetableUpdateConnectednessClique(), SCIP_Clique::equation, FALSE, SCIP_CliqueTable::hashtable, SCIP_Clique::id, SCIP_Clique::index, SCIP_CliqueTable::ncliques, SCIP_CliqueTable::ncreatedcliques, SCIP_CliqueTable::nentries, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_LOOSE, SCIP_VARSTATUS_MULTAGGR, SCIPdebugCheckClique, SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPsetAllocBufferArray, SCIPsetDebugMsg, SCIPsetDuplicateBufferArray, SCIPsetFreeBufferArray, SCIPvarFixBinary(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsMarkedDeleteGlobalStructures(), SCIPvarsAddClique(), SCIPvarsGetProbvarBinary(), sortAndMergeClique(), TRUE, and w.

Referenced by SCIPaddClique(), and varAddImplic().

◆ cliqueCleanup()

static SCIP_RETCODE cliqueCleanup	(	SCIP_CLIQUE *	clique,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PROB *	transprob,
		SCIP_PROB *	origprob,
		SCIP_TREE *	tree,
		SCIP_REOPT *	reopt,
		SCIP_LP *	lp,
		SCIP_BRANCHCAND *	branchcand,
		SCIP_EVENTQUEUE *	eventqueue,
		SCIP_CLIQUETABLE *	cliquetable,
		int *	nchgbds,
		SCIP_Bool *	infeasible
	)

static

clean up given clique by removing fixed variables

Parameters

clique	clique data structure
blkmem	block memory
set	global SCIP settings
stat	problem statistics
transprob	transformed problem
origprob	original problem
tree	branch and bound tree if in solving stage
reopt	reoptimization data structure
lp	current LP data
branchcand	branching candidate storage
eventqueue	event queue
cliquetable	clique table data structure
nchgbds	pointer to store number of fixed variables
infeasible	pointer to store whether an infeasibility was detected

Definition at line 2612 of file implics.c.

References checkNEntries, SCIP_CliqueTable::cliques, SCIP_Clique::equation, FALSE, SCIP_Clique::id, SCIP_CliqueTable::ncliques, SCIP_CliqueTable::nentries, NULL, SCIP_Clique::nvars, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_LOOSE, SCIP_VARSTATUS_MULTAGGR, SCIP_VARSTATUS_NEGATED, SCIPcliqueIsCleanedUp(), SCIPsetDebugMsg, SCIPvarAddCliqueToList(), SCIPvarDelCliqueFromList(), SCIPvarFixBinary(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegationVar(), SCIPvarGetProbvarBinary(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsMarkedDeleteGlobalStructures(), sortAndMergeClique(), SCIP_Clique::startcleanup, TRUE, SCIP_Clique::values, SCIP_Clique::vars, and w.

Referenced by SCIPcliquetableCleanup().

◆ SCIPcliquetableCleanup()

SCIP_RETCODE SCIPcliquetableCleanup	(	SCIP_CLIQUETABLE *	cliquetable,
		BMS_BLKMEM *	blkmem,
		SCIP_SET *	set,
		SCIP_STAT *	stat,
		SCIP_PROB *	transprob,
		SCIP_PROB *	origprob,
		SCIP_TREE *	tree,
		SCIP_REOPT *	reopt,
		SCIP_LP *	lp,
		SCIP_BRANCHCAND *	branchcand,
		SCIP_EVENTQUEUE *	eventqueue,
		int *	nchgbds,
		SCIP_Bool *	infeasible
	)

removes all empty and single variable cliques from the clique table; removes double entries from the clique table

Note: cliques can be processed several times by this method

Parameters

cliquetable	clique table data structure
blkmem	block memory
set	global SCIP settings
stat	problem statistics
transprob	transformed problem
origprob	original problem
tree	branch and bound tree if in solving stage
reopt	reoptimization data structure
lp	current LP data
branchcand	branching candidate storage
eventqueue	event queue
nchgbds	pointer to store number of fixed variables
infeasible	pointer to store whether an infeasibility was detected

Definition at line 2883 of file implics.c.

Referenced by exitPresolve(), presolveRound(), and SCIPcleanupCliques().

◆ SCIPcliquetableComputeCliqueComponents()

SCIP_RETCODE SCIPcliquetableComputeCliqueComponents	(	SCIP_CLIQUETABLE *	cliquetable,
		SCIP_SET *	set,
		BMS_BLKMEM *	blkmem,
		SCIP_VAR **	vars,
		int	nbinvars,
		int	nintvars,
		int	nimplvars
	)

computes connected components of the clique table

an update becomes necessary if a clique gets added with variables from different components

Parameters

cliquetable	clique table data structure
set	global SCIP settings
blkmem	block memory
vars	array of problem variables, sorted by variable type
nbinvars	number of binary variables
nintvars	number of integer variables
nimplvars	number of implicit integer variables

Definition at line 3094 of file implics.c.

References SCIP_CliqueTable::cliques, cliquetableUpdateConnectednessClique(), SCIP_CliqueTable::compsfromscratch, SCIP_CliqueTable::djset, FALSE, SCIP_CliqueTable::ncliquecomponents, SCIP_CliqueTable::ncliques, NULL, SCIP_CALL, SCIP_OKAY, SCIPdisjointsetCreate(), SCIPdisjointsetFree(), SCIPdisjointsetGetComponentCount(), SCIPhashmapCreate(), SCIPhashmapInsert(), SCIPhashmapRemoveAll(), SCIPsetDebugMsg, SCIPvarGetProbvar(), SCIPvarIsActive(), SCIPvarIsBinary(), and SCIP_CliqueTable::varidxtable.

Referenced by SCIPcalcCliquePartition().

◆ SCIPvboundsGetNVbds()

int SCIPvboundsGetNVbds ( SCIP_VBOUNDS * vbounds )

gets number of variable bounds contained in given variable bounds data structure

Parameters

vbounds variable bounds data structure

Definition at line 3253 of file implics.c.

References SCIP_VBounds::len, and NULL.

Referenced by SCIPvarAggregate(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarRemoveCliquesImplicsVbs(), and varAddTransitiveImplic().

◆ SCIPvboundsGetVars()

SCIP_VAR** SCIPvboundsGetVars ( SCIP_VBOUNDS * vbounds )

gets array of variables contained in given variable bounds data structure

Parameters

vbounds variable bounds data structure

Definition at line 3261 of file implics.c.

References NULL, and SCIP_VBounds::vars.

Referenced by SCIPvarAggregate(), SCIPvarGetVlbVars(), SCIPvarGetVubVars(), SCIPvarRemoveCliquesImplicsVbs(), and varAddTransitiveImplic().

◆ SCIPvboundsGetCoefs()

SCIP_Real* SCIPvboundsGetCoefs ( SCIP_VBOUNDS * vbounds )

gets array of coefficients contained in given variable bounds data structure

Parameters

vbounds variable bounds data structure

Definition at line 3269 of file implics.c.

References SCIP_VBounds::coefs, and NULL.

Referenced by SCIPvarAggregate(), SCIPvarGetVlbCoefs(), SCIPvarGetVubCoefs(), SCIPvarRemoveCliquesImplicsVbs(), and varAddTransitiveImplic().

◆ SCIPvboundsGetConstants()

SCIP_Real* SCIPvboundsGetConstants ( SCIP_VBOUNDS * vbounds )

gets array of constants contained in given variable bounds data structure

Parameters

vbounds variable bounds data structure

Definition at line 3277 of file implics.c.

References SCIP_VBounds::constants, and NULL.

Referenced by SCIPvarAggregate(), SCIPvarGetVlbConstants(), SCIPvarGetVubConstants(), SCIPvarRemoveCliquesImplicsVbs(), and varAddTransitiveImplic().

◆ SCIPimplicsGetNImpls()

int SCIPimplicsGetNImpls	(	SCIP_IMPLICS *	implics,
		SCIP_Bool	varfixing
	)

gets number of implications for a given binary variable fixing

Parameters

implics	implication data
varfixing	should the implications on var == FALSE or var == TRUE be returned?

Definition at line 3285 of file implics.c.

References SCIP_Implics::nimpls, and NULL.

Referenced by SCIPvarAggregate(), SCIPvarGetImplRedcost(), SCIPvarGetNImpls(), SCIPvarRemoveCliquesImplicsVbs(), and varAddTransitiveBinaryClosureImplic().

◆ SCIPimplicsGetVars()

SCIP_VAR** SCIPimplicsGetVars	(	SCIP_IMPLICS *	implics,
		SCIP_Bool	varfixing
	)

gets array with implied variables for a given binary variable fixing

Parameters

implics	implication data
varfixing	should the implications on var == FALSE or var == TRUE be returned?

Definition at line 3294 of file implics.c.

References NULL, and SCIP_Implics::vars.

Referenced by SCIPvarAggregate(), SCIPvarGetImplRedcost(), SCIPvarGetImplVars(), SCIPvarRemoveCliquesImplicsVbs(), and varAddTransitiveBinaryClosureImplic().

◆ SCIPimplicsGetTypes()

SCIP_BOUNDTYPE* SCIPimplicsGetTypes	(	SCIP_IMPLICS *	implics,
		SCIP_Bool	varfixing
	)

gets array with implication types for a given binary variable fixing

Parameters

implics	implication data
varfixing	should the implications on var == FALSE or var == TRUE be returned?

Definition at line 3303 of file implics.c.

References NULL, and SCIP_Implics::types.

Referenced by SCIPvarAggregate(), SCIPvarGetImplRedcost(), SCIPvarGetImplTypes(), SCIPvarRemoveCliquesImplicsVbs(), and varAddTransitiveBinaryClosureImplic().

◆ SCIPimplicsGetBounds()

SCIP_Real* SCIPimplicsGetBounds	(	SCIP_IMPLICS *	implics,
		SCIP_Bool	varfixing
	)

gets array with implication bounds for a given binary variable fixing

Parameters

implics	implication data
varfixing	should the implications on var == FALSE or var == TRUE be returned?

Definition at line 3312 of file implics.c.

References SCIP_Implics::bounds, and NULL.

Referenced by SCIPvarAggregate(), SCIPvarGetImplBounds(), SCIPvarGetImplRedcost(), SCIPvarRemoveCliquesImplicsVbs(), and varAddTransitiveBinaryClosureImplic().

◆ SCIPimplicsGetIds()

int* SCIPimplicsGetIds	(	SCIP_IMPLICS *	implics,
		SCIP_Bool	varfixing
	)

Gets array with unique implication identifiers for a given binary variable fixing. If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication, its id is negative, otherwise it is nonnegative.

Parameters

implics	implication data
varfixing	should the implications on var == FALSE or var == TRUE be returned?

Definition at line 3324 of file implics.c.

References SCIP_Implics::ids, and NULL.

Referenced by SCIPvarGetImplIds().

◆ SCIPcliqueGetNVars()

int SCIPcliqueGetNVars ( SCIP_CLIQUE * clique )

gets number of variables in the cliques

Parameters

clique clique data structure

Definition at line 3333 of file implics.c.

References NULL, and SCIP_Clique::nvars.

Referenced by addGLSCliques(), addNextLevelCliques(), applyCliqueFixings(), collectBinaryCliqueData(), collectMinactImplicVars(), dfs(), extractCycle(), getMaxactImplicObjchg(), insertSortedRootNeighbors(), isNeighbor(), propagateVbounds(), SCIPcliquelistDel(), SCIPcopyImplicationsCliques(), SCIPnodePropagateImplics(), SCIPvarAddClique(), SCIPvarGetImplRedcost(), SCIPwriteCliqueGraph(), separateCuts(), tarjan(), and tcliquegraphConstructCliqueTable().

◆ SCIPcliqueGetVars()

SCIP_VAR** SCIPcliqueGetVars ( SCIP_CLIQUE * clique )

gets array of active problem variables in the cliques

Parameters

clique clique data structure

Definition at line 3343 of file implics.c.

References NULL, and SCIP_Clique::vars.

Referenced by addGLSCliques(), addNextLevelCliques(), applyCliqueFixings(), collectBinaryCliqueData(), collectMinactImplicVars(), dfs(), extractCycle(), getMaxactImplicObjchg(), insertSortedRootNeighbors(), isNeighbor(), propagateVbounds(), SCIPcliquelistDel(), SCIPcopyImplicationsCliques(), SCIPnodePropagateImplics(), SCIPvarAddClique(), SCIPvarGetImplRedcost(), SCIPwriteCliqueGraph(), separateCuts(), tarjan(), and tcliquegraphConstructCliqueTable().

◆ SCIPcliqueGetValues()

SCIP_Bool* SCIPcliqueGetValues ( SCIP_CLIQUE * clique )

gets array of values of active problem variables in the cliques, i.e. whether the variable is fixed to FALSE or to TRUE in the clique

Parameters

clique clique data structure

Definition at line 3355 of file implics.c.

References NULL, and SCIP_Clique::values.

Referenced by addGLSCliques(), addNextLevelCliques(), applyCliqueFixings(), collectBinaryCliqueData(), collectMinactImplicVars(), dfs(), extractCycle(), getMaxactImplicObjchg(), insertSortedRootNeighbors(), isNeighbor(), propagateVbounds(), SCIPcliquelistDel(), SCIPcopyImplicationsCliques(), SCIPnodePropagateImplics(), SCIPvarAddClique(), SCIPvarGetImplRedcost(), SCIPwriteCliqueGraph(), separateCuts(), tarjan(), and tcliquegraphConstructCliqueTable().

◆ SCIPcliqueGetId()

unsigned int SCIPcliqueGetId ( SCIP_CLIQUE * clique )

gets unique identifier of the clique

Parameters

clique clique data structure

Definition at line 3365 of file implics.c.

References SCIP_Clique::id, and NULL.

Referenced by SCIP_DECL_HASHKEYEQ(), SCIPcliquelistsHaveCommonClique(), and tcliquegraphAddNode().

◆ SCIPcliqueGetIndex()

int SCIPcliqueGetIndex ( SCIP_CLIQUE * clique )

gets index of the clique in the clique table

Parameters

clique clique data structure

Definition at line 3379 of file implics.c.

References SCIP_Clique::index, and NULL.

Referenced by dfs(), and tarjan().

◆ SCIPcliqueIsCleanedUp()

SCIP_Bool SCIPcliqueIsCleanedUp ( SCIP_CLIQUE * clique )

gets unique identifier of the clique

Parameters

clique clique data structure

Definition at line 3389 of file implics.c.

References NULL, and SCIP_Clique::startcleanup.

Referenced by cliqueCleanup(), cliquetableMarkCliqueForCleanup(), SCIPcliquetableCleanup(), and SCIPvarGetImplRedcost().

◆ SCIPcliqueIsEquation()

SCIP_Bool SCIPcliqueIsEquation ( SCIP_CLIQUE * clique )

return whether the given clique is an equation

Parameters

clique clique data structure

Definition at line 3399 of file implics.c.

References SCIP_Clique::equation, NULL, and SCIP_Bool.

Referenced by extractCycle(), SCIPcopyImplicationsCliques(), and separateCuts().

◆ SCIPcliquelistGetNCliques()

int SCIPcliquelistGetNCliques	(	SCIP_CLIQUELIST *	cliquelist,
		SCIP_Bool	value
	)

returns the number of cliques stored in the clique list

Parameters

cliquelist	clique list data structure
value	value of the variable for which the cliques should be returned

Definition at line 3409 of file implics.c.

References SCIP_CliqueList::ncliques, and NULL.

Referenced by SCIPcliquelistCheck(), and SCIPvarGetNCliques().

◆ SCIPcliquelistGetCliques()

SCIP_CLIQUE** SCIPcliquelistGetCliques	(	SCIP_CLIQUELIST *	cliquelist,
		SCIP_Bool	value
	)

returns the cliques stored in the clique list, or NULL if the clique list is empty

Parameters

cliquelist	clique list data structure
value	value of the variable for which the cliques should be returned

Definition at line 3418 of file implics.c.

References SCIP_CliqueList::cliques, and NULL.

Referenced by SCIPcliquelistCheck(), and SCIPvarGetCliques().

◆ SCIPcliquelistCheck()

void SCIPcliquelistCheck	(	SCIP_CLIQUELIST *	cliquelist,
		SCIP_VAR *	var
	)

checks whether variable is contained in all cliques of the cliquelist

Parameters

cliquelist	clique list data structure
var	variable, the clique list belongs to

Definition at line 3427 of file implics.c.

References FALSE, NULL, SCIP_Bool, SCIPcliquelistGetCliques(), SCIPcliquelistGetNCliques(), SCIPcliqueSearchVar(), SCIPvarGetCliques(), SCIPvarGetNCliques(), TRUE, SCIP_Clique::values, and SCIP_Clique::vars.

Referenced by SCIPvarAddClique(), SCIPvarDelClique(), and SCIPvarsAddClique().

◆ SCIPcliquetableGetNCliques()

int SCIPcliquetableGetNCliques ( SCIP_CLIQUETABLE * cliquetable )

gets the number of cliques stored in the clique table

Parameters

cliquetable clique table data structure

Definition at line 3469 of file implics.c.

References SCIP_CliqueTable::ncliques, and NULL.

Referenced by presolve(), SCIPgetNCliques(), SCIPhaveVarsCommonClique(), and SCIPisPresolveFinished().

◆ SCIPcliquetableGetNCliquesCreated()

int SCIPcliquetableGetNCliquesCreated ( SCIP_CLIQUETABLE * cliquetable )

gets the number of cliques created so far by the clique table

Parameters

cliquetable clique table data structure

Definition at line 3479 of file implics.c.

References SCIP_CliqueTable::ncreatedcliques, and NULL.

Referenced by SCIPgetNCliquesCreated().

◆ SCIPcliquetableGetCliques()

SCIP_CLIQUE** SCIPcliquetableGetCliques ( SCIP_CLIQUETABLE * cliquetable )

gets the array of cliques stored in the clique table

Parameters

cliquetable clique table data structure

Definition at line 3489 of file implics.c.

References SCIP_CliqueTable::cliques, and NULL.

Referenced by SCIPgetCliques().

◆ SCIPcliquetableGetNEntries()

SCIP_Longint SCIPcliquetableGetNEntries ( SCIP_CLIQUETABLE * cliquetable )

gets the number of entries in the whole clique table

Parameters

cliquetable clique table data structure

Definition at line 3499 of file implics.c.

References SCIP_CliqueTable::nentries, and NULL.

◆ SCIPcliquetableGetNCliqueComponents()

int SCIPcliquetableGetNCliqueComponents ( SCIP_CLIQUETABLE * cliquetable )

returns the number of clique components, or -1 if update is necessary first

Parameters

cliquetable clique table data structure

Definition at line 3509 of file implics.c.

References SCIP_CliqueTable::compsfromscratch, and SCIP_CliqueTable::ncliquecomponents.

◆ SCIPcliquetableNeedsComponentUpdate()

SCIP_Bool SCIPcliquetableNeedsComponentUpdate ( SCIP_CLIQUETABLE * cliquetable )

returns TRUE iff the connected clique components need an update (because new cliques were added)

Parameters

cliquetable clique table data structure

Definition at line 3517 of file implics.c.

References SCIP_CliqueTable::compsfromscratch, SCIP_CliqueTable::djset, and NULL.

Referenced by SCIPcalcCliquePartition().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ cliqueCheck

◆ HASHTABLE_CLIQUETABLE_SIZE

◆ checkNEntries

Function Documentation

◆ vboundsCreate()

◆ SCIPvboundsFree()

◆ vboundsEnsureSize()

◆ vboundsSearchPos()

◆ SCIPvboundsAdd()

◆ SCIPvboundsDel()

◆ SCIPvboundsShrink()

◆ SCIP_DECL_SORTPTRCOMP()

◆ checkImplics()

◆ implicsCreate()

◆ SCIPimplicsFree()

◆ implicsEnsureSize()

◆ implicsSearchVar()

◆ implicsSearchImplic()

◆ SCIPimplicsAdd()

◆ SCIPimplicsDel()

◆ SCIPimplicsGetVarImplics()

◆ SCIPimplicsContainsImpl()

◆ cliquetableSwapCliques()

◆ cliquetableMarkCliqueForCleanup()

◆ cliqueCreateWithData()

◆ cliqueFree()

◆ cliqueEnsureSize()

◆ SCIPcliqueSearchVar()

◆ SCIPcliqueHasVar()

◆ SCIPcliqueAddVar()

◆ SCIPcliqueDelVar()

◆ cliquesSearchClique()

◆ cliquelistCreate()

◆ SCIPcliquelistFree()

◆ cliquelistEnsureSize()

◆ SCIPcliquelistAdd()

◆ SCIPcliquelistDel()

◆ SCIPcliquelistsHaveCommonClique()

◆ SCIPcliquelistRemoveFromCliques()

◆ SCIP_DECL_HASHGETKEY()

◆ SCIP_DECL_HASHKEYEQ()

◆ SCIP_DECL_HASHKEYVAL()

◆ SCIPcliquetableCreate()

◆ SCIPcliquetableFree()

◆ cliquetableEnsureSize()

◆ sortAndMergeClique()

◆ cliquetableGetNodeIndexBinvar()

◆ cliquetableUpdateConnectednessClique()

◆ SCIPcliquetableGetVarComponentIdx()

◆ SCIPcliquetableAdd()

◆ cliqueCleanup()

◆ SCIPcliquetableCleanup()

◆ SCIPcliquetableComputeCliqueComponents()

◆ SCIPvboundsGetNVbds()

◆ SCIPvboundsGetVars()

◆ SCIPvboundsGetCoefs()

◆ SCIPvboundsGetConstants()

◆ SCIPimplicsGetNImpls()

◆ SCIPimplicsGetVars()

◆ SCIPimplicsGetTypes()

◆ SCIPimplicsGetBounds()

◆ SCIPimplicsGetIds()

◆ SCIPcliqueGetNVars()

◆ SCIPcliqueGetVars()

◆ SCIPcliqueGetValues()

◆ SCIPcliqueGetId()

◆ SCIPcliqueGetIndex()

◆ SCIPcliqueIsCleanedUp()

◆ SCIPcliqueIsEquation()

◆ SCIPcliquelistGetNCliques()

◆ SCIPcliquelistGetCliques()

◆ SCIPcliquelistCheck()

◆ SCIPcliquetableGetNCliques()

◆ SCIPcliquetableGetNCliquesCreated()

◆ SCIPcliquetableGetCliques()