implics.h File Reference

Detailed Description

methods for implications, variable bounds, and cliques

Author

Tobias Achterberg

Definition in file implics.h.

#include "scip/def.h"
#include "blockmemshell/memory.h"
#include "scip/type_retcode.h"
#include "scip/type_set.h"
#include "scip/type_stat.h"
#include "scip/type_event.h"
#include "scip/type_lp.h"
#include "scip/type_var.h"
#include "scip/type_implics.h"
#include "scip/type_branch.h"
#include "scip/pub_implics.h"

Go to the source code of this file.

Functions
void	SCIPvboundsFree (SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem)
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)
int	SCIPvboundsGetNVbds (SCIP_VBOUNDS *vbounds)
SCIP_VAR **	SCIPvboundsGetVars (SCIP_VBOUNDS *vbounds)
SCIP_Real *	SCIPvboundsGetCoefs (SCIP_VBOUNDS *vbounds)
SCIP_Real *	SCIPvboundsGetConstants (SCIP_VBOUNDS *vbounds)
void	SCIPimplicsFree (SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem)
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)
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)
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)
void	SCIPcliquelistFree (SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem)
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)
SCIP_RETCODE	SCIPcliquetableCreate (SCIP_CLIQUETABLE **cliquetable, SCIP_SET *set, BMS_BLKMEM *blkmem)
SCIP_RETCODE	SCIPcliquetableFree (SCIP_CLIQUETABLE **cliquetable, BMS_BLKMEM *blkmem)
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)
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)
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)
SCIP_CLIQUE **	SCIPcliquetableGetCliques (SCIP_CLIQUETABLE *cliquetable)
SCIP_Longint	SCIPcliquetableGetNEntries (SCIP_CLIQUETABLE *cliquetable)

Function Documentation

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 66 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

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 <= b*z + d or x >= b*z + d
coef	coefficient b in x <= b*z + d or x >= b*z + d
constant	constant d in x <= b*z + d or x >= b*z + d
added	pointer to store whether the variable bound was added

Definition at line 199 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().

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 281 of file implics.c.

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

Referenced by SCIPvarRemoveCliquesImplicsVbs().

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 326 of file implics.c.

References NULL, and SCIPvboundsFree().

Referenced by SCIPvarRemoveCliquesImplicsVbs().

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 3021 of file implics.c.

References SCIP_VBounds::len, and NULL.

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

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 3029 of file implics.c.

References NULL, and SCIP_VBounds::vars.

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

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 3037 of file implics.c.

References SCIP_VBounds::coefs, and NULL.

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

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 3045 of file implics.c.

References SCIP_VBounds::constants, and NULL.

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

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 444 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

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 630 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, SCIPdebugMessage, SCIPsetIsFeasGE(), SCIPsetIsFeasGT(), SCIPsetIsFeasLE(), SCIPsetIsFeasLT(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), and TRUE.

Referenced by varAddImplic().

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 837 of file implics.c.

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

Referenced by SCIPvarRemoveCliquesImplicsVbs().

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 895 of file implics.c.

References implicsSearchVar(), and NULL.

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 917 of file implics.c.

References implicsSearchImplic().

Referenced by SCIPvarHasImplic().

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 3053 of file implics.c.

References SCIP_Implics::nimpls, and NULL.

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

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 3062 of file implics.c.

References NULL, and SCIP_Implics::vars.

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

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 3071 of file implics.c.

References NULL, and SCIP_Implics::types.

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

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 3080 of file implics.c.

References SCIP_Implics::bounds, and NULL.

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

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 3092 of file implics.c.

References SCIP_Implics::ids, and NULL.

Referenced by SCIPvarGetImplIds().

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 1135 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, SCIPdebugMessage, SCIPsortedvecFindPtr(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarIsBinary(), TRUE, SCIP_Clique::values, and SCIP_Clique::vars.

Referenced by SCIPvarAddClique().

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 1269 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().

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 1425 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

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 1466 of file implics.c.

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

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

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 1511 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().

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 1589 of file implics.c.

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

Referenced by SCIPvarsHaveCommonClique().

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 1667 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_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 1776 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, SCIPcalcHashtableSize(), and SCIPhashtableCreate().

Referenced by SCIPtransformProb().

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 1808 of file implics.c.

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

Referenced by freeTransform().

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 2240 of file implics.c.

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

Referenced by SCIPaddClique(), and varAddImplic().

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

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 2780 of file implics.c.

References checkNEntries, cliqueCheck(), cliqueCleanup(), cliqueFree(), SCIP_CliqueTable::cliques, cliquetableSwapCliques(), SCIP_Clique::equation, SCIP_Clique::eventsissued, FALSE, SCIP_CliqueTable::hashtable, SCIP_Clique::id, SCIP_CliqueTable::incleanup, SCIP_Clique::index, SCIP_CliqueTable::ncleanupaggrvars, SCIP_CliqueTable::ncleanupfixedvars, SCIP_CliqueTable::ncliques, SCIP_CliqueTable::ndirtycliques, SCIP_CliqueTable::nentries, SCIP_Stat::npresolaggrvars, SCIP_Stat::npresolfixedvars, NULL, SCIP_Clique::nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIPcliqueIsCleanedUp(), SCIPdebugMessage, SCIPeventCreateImplAdded(), SCIPeventqueueAdd(), SCIPeventqueueDelay(), SCIPeventqueueProcess(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPsetGetStage(), SCIPvarDelCliqueFromList(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarTryAggregateVars(), TRUE, SCIP_Clique::values, and SCIP_Clique::vars.

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

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 3163 of file implics.c.

References SCIP_CliqueList::ncliques, and NULL.

Referenced by SCIPcliquelistCheck(), and SCIPvarGetNCliques().

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 3172 of file implics.c.

References SCIP_CliqueList::cliques, and NULL.

Referenced by SCIPcliquelistCheck(), and SCIPvarGetCliques().

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 3181 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().

int SCIPcliquetableGetNCliques

(

SCIP_CLIQUETABLE *

cliquetable

)

gets the number of cliques stored in the clique table

Parameters

cliquetable

clique table data structure

Definition at line 3223 of file implics.c.

References SCIP_CliqueTable::ncliques, and NULL.

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

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 3233 of file implics.c.

References SCIP_CliqueTable::cliques, and NULL.

Referenced by SCIPgetCliques().

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 3243 of file implics.c.

References SCIP_CliqueTable::nentries, and NULL.