Scippy

SCIP

Solving Constraint Integer Programs

implics.c File Reference

Detailed Description

methods for implications, variable bounds, and clique tables

Author
Tobias Achterberg

Definition in file implics.c.

#include <stdlib.h>
#include <assert.h>
#include "scip/def.h"
#include "scip/set.h"
#include "scip/stat.h"
#include "scip/event.h"
#include "scip/var.h"
#include "scip/implics.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/debug.h"
#include "scip/struct_implics.h"

Go to the source code of this file.

Macros

#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 void cliqueCheck (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)
 
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)
 
int SCIPvboundsGetNVbds (SCIP_VBOUNDS *vbounds)
 
SCIP_VAR ** SCIPvboundsGetVars (SCIP_VBOUNDS *vbounds)
 
SCIP_RealSCIPvboundsGetCoefs (SCIP_VBOUNDS *vbounds)
 
SCIP_RealSCIPvboundsGetConstants (SCIP_VBOUNDS *vbounds)
 
int SCIPimplicsGetNImpls (SCIP_IMPLICS *implics, SCIP_Bool varfixing)
 
SCIP_VAR ** SCIPimplicsGetVars (SCIP_IMPLICS *implics, SCIP_Bool varfixing)
 
SCIP_BOUNDTYPESCIPimplicsGetTypes (SCIP_IMPLICS *implics, SCIP_Bool varfixing)
 
SCIP_RealSCIPimplicsGetBounds (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_BoolSCIPcliqueGetValues (SCIP_CLIQUE *clique)
 
int SCIPcliqueGetId (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)
 
SCIP_CLIQUE ** SCIPcliquetableGetCliques (SCIP_CLIQUETABLE *cliquetable)
 
SCIP_Longint SCIPcliquetableGetNEntries (SCIP_CLIQUETABLE *cliquetable)
 

Macro Definition Documentation

#define HASHTABLE_CLIQUETABLE_SIZE   100

Definition at line 1773 of file implics.c.

Referenced by SCIPcliquetableCreate().

#define checkNEntries (   cliquetable)    TRUE

Definition at line 2771 of file implics.c.

Referenced by cliqueCleanup(), and SCIPcliquetableCleanup().

Function Documentation

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

creates a variable bounds data structure

Parameters
vboundspointer to store variable bounds data structure
blkmemblock memory

Definition at line 48 of file implics.c.

References BMSallocBlockMemory, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by vboundsEnsureSize().

void SCIPvboundsFree ( SCIP_VBOUNDS **  vbounds,
BMS_BLKMEM blkmem 
)

frees a variable bounds data structure

Parameters
vboundspointer to store variable bounds data structure
blkmemblock memory

Definition at line 66 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

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
vboundspointer to variable bounds data structure
blkmemblock memory
setglobal SCIP settings
numminimum number of entries to store

Definition at line 84 of file implics.c.

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

Referenced by SCIPvboundsAdd().

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
vboundsvariable bounds data structure, or NULL
varvariable to search in vbounds data structure
negativecoefis coefficient b negative?
insertpospointer to store position where to insert new entry
foundpointer to store whether the same variable was found at the returned pos

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

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
vboundspointer to variable bounds data structure
blkmemblock memory
setglobal SCIP settings
vboundtypetype of variable bound (LOWER or UPPER)
varvariable z in x <= b*z + d or x >= b*z + d
coefcoefficient b in x <= b*z + d or x >= b*z + d
constantconstant d in x <= b*z + d or x >= b*z + d
addedpointer 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
vboundspointer to variable bounds data structure
blkmemblock memory
vbdvarvariable z in x >=/<= b*z + d
negativecoefis 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
vboundspointer to variable bounds data structure
blkmemblock memory
newnvbdsnew number of variable bounds

Definition at line 326 of file implics.c.

References NULL, and SCIPvboundsFree().

Referenced by SCIPvarRemoveCliquesImplicsVbs().

static SCIP_DECL_SORTPTRCOMP ( compVars  )
static

comparator function for implication variables in the implication data structure

Definition at line 352 of file implics.c.

References NULL, and SCIPvarGetIndex().

static void checkImplics ( SCIP_IMPLICS implics)
static

performs integrity check on implications data structure

Parameters
implicsimplications data structure

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

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

creates an implications data structure

Parameters
implicspointer to store implications data structure
blkmemblock memory

Definition at line 418 of file implics.c.

References BMSallocBlockMemory, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by implicsEnsureSize().

void SCIPimplicsFree ( SCIP_IMPLICS **  implics,
BMS_BLKMEM blkmem 
)

frees an implications data structure

Parameters
implicspointer of implications data structure to free
blkmemblock memory

Definition at line 444 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

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
implicspointer to implications data structure
blkmemblock memory
setglobal SCIP settings
varfixingFALSE if size of arrays for x == 0 has to be ensured, TRUE for x == 1
numminimum number of entries to store

Definition at line 467 of file implics.c.

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

Referenced by SCIPimplicsAdd().

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
implicsimplications data structure
varfixingFALSE if y is searched in implications for x == 0, TRUE for x == 1
implvarvariable y to search for
poslowerpointer to store position of y_lower (-1 if not found)
posupperpointer to store position of y_upper (-1 if not found)
posaddpointer to store position of first y entry, or where a new y entry should be placed

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

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
implicsimplications data structure
varfixingFALSE if y is searched in implications for x == 0, TRUE for x == 1
implvarvariable y to search for
impltypetype of implication y <=/>= b to search for
poslowerpointer to store position of y_lower (inf if not found)
posupperpointer to store position of y_upper (inf if not found)
posaddpointer to store correct position (with respect to impltype) to add y

Definition at line 593 of file implics.c.

References implicsSearchVar(), NULL, and SCIP_BOUNDTYPE_LOWER.

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

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
implicspointer to implications data structure
blkmemblock memory
setglobal SCIP settings
statproblem statistics
varfixingFALSE if implication for x == 0 has to be added, TRUE for x == 1
implvarvariable y in implication y <= b or y >= b
impltypetype of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER)
implboundbound b in implication y <= b or y >= b
isshortcutis the implication a shortcut, i.e., added as part of the transitive closure of another implication?
conflictpointer to store whether implication causes a conflict for variable x
addedpointer 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
implicspointer to implications data structure
blkmemblock memory
setglobal SCIP settings
varfixingFALSE if y should be removed from implications for x <= 0, TRUE for x >= 1
implvarvariable y in implication y <= b or y >= b
impltypetype 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
implicsimplications data structure
varfixingFALSE if y should be searched in implications for x == 0, TRUE for x == 1
implvarvariable y to search for
haslowerimplicpointer to store whether there exists an implication y >= l
hasupperimplicpointer 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
implicsimplications data structure
varfixingFALSE if y should be searched in implications for x == 0, TRUE for x == 1
implvarvariable y to search for
impltypetype of implication y <=/>= b to search for

Definition at line 917 of file implics.c.

References implicsSearchImplic().

Referenced by SCIPvarHasImplic().

static void cliquetableSwapCliques ( SCIP_CLIQUETABLE cliquetable,
int  first,
int  second 
)
static
Parameters
cliquetableclique table data structure
firstfirst index
secondsecond index

Definition at line 940 of file implics.c.

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

Referenced by cliquetableMarkCliqueForCleanup(), and SCIPcliquetableCleanup().

static void cliquetableMarkCliqueForCleanup ( SCIP_CLIQUETABLE cliquetable,
SCIP_CLIQUE clique 
)
static
Parameters
cliquetableclique table data structure
cliqueclique data structure

Definition at line 966 of file implics.c.

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

Referenced by SCIPcliqueDelVar().

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
cliquepointer to store clique data structure
blkmemblock memory
sizeinitial size of clique
varsbinary variables in the clique: at most one can be set to the given value
valuesvalues of the variables in the clique
nvarsnumber of variables in the clique
idunique identifier of the clique
isequationis the clique an equation or an inequality?

Definition at line 988 of file implics.c.

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

Referenced by SCIPcliquetableAdd().

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

frees a clique data structure

Parameters
cliquepointer to store clique data structure
blkmemblock memory

Definition at line 1022 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

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
cliqueclique data structure
blkmemblock memory
setglobal SCIP settings
numminimum number of entries to store

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

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
cliqueclique data structure
varvariable to search for
valuevalue of the variable in the clique

Definition at line 1065 of file implics.c.

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

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

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
cliqueclique data structure
varvariable to remove from the clique
valuevalue of the variable in the clique

Definition at line 1125 of file implics.c.

References SCIPcliqueSearchVar().

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
cliqueclique data structure
blkmemblock memory
setglobal SCIP settings
varvariable to add to the clique
valuevalue of the variable in the clique
doubleentrypointer to store whether the variable and value occurs twice in the clique
oppositeentrypointer 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
cliqueclique data structure
cliquetableclique table data structure
varvariable to remove from the clique
valuevalue 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().

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
cliquesarray of cliques
ncliquesnumber of cliques in the cliques array
cliqueclique to search for

Definition at line 1317 of file implics.c.

References SCIP_Clique::id, and NULL.

Referenced by cliqueCheck(), and SCIPcliquelistDel().

static void cliqueCheck ( SCIP_CLIQUE clique)
static
static SCIP_RETCODE cliquelistCreate ( SCIP_CLIQUELIST **  cliquelist,
BMS_BLKMEM blkmem 
)
static

creates a clique list data structure

Parameters
cliquelistpointer to store clique list data structure
blkmemblock memory

Definition at line 1406 of file implics.c.

References BMSallocBlockMemory, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by SCIPcliquelistAdd().

void SCIPcliquelistFree ( SCIP_CLIQUELIST **  cliquelist,
BMS_BLKMEM blkmem 
)

frees a clique list data structure

Parameters
cliquelistpointer to the clique list data structure
blkmemblock memory

Definition at line 1425 of file implics.c.

References BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

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
cliquelistclique list data structure
blkmemblock memory
setglobal SCIP settings
valuevalue of the variable for which the clique list should be extended
numminimum number of entries to store

Definition at line 1442 of file implics.c.

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

Referenced by 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
cliquelistpointer to the clique list data structure
blkmemblock memory
setglobal SCIP settings
valuevalue of the variable for which the clique list should be extended
cliqueclique 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
cliquelistpointer to the clique list data structure
blkmemblock memory
valuevalue of the variable for which the clique list should be reduced
cliqueclique 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
cliquelist1first clique list data structure
value1value of first variable
cliquelist2second clique list data structure
value2value 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
cliquelistclique list data structure
cliquetableclique table data structure
varactive problem variable the clique list belongs to
irrelevantvarhas 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().

static SCIP_DECL_HASHGETKEY ( hashgetkeyClique  )
static

gets the key of the given element

Definition at line 1723 of file implics.c.

static SCIP_DECL_HASHKEYEQ ( hashkeyeqClique  )
static

returns TRUE iff both keys are equal

Definition at line 1730 of file implics.c.

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

static SCIP_DECL_HASHKEYVAL ( hashkeyvalClique  )
static

returns the hash value of the key

Definition at line 1756 of file implics.c.

References SCIP_Clique::nvars, SCIP_Clique::values, and SCIP_Clique::vars.

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

creates a clique table data structure

Parameters
cliquetablepointer to store clique table data structure
setglobal SCIP settings
blkmemblock 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
cliquetablepointer to store clique table data structure
blkmemblock memory

Definition at line 1808 of file implics.c.

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

Referenced by freeTransform().

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
cliquetableclique table data structure
setglobal SCIP settings
numminimum number of entries to store

Definition at line 1837 of file implics.c.

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

Referenced by SCIPcliquetableAdd().

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
clqvarsvariables of a clique
clqvaluesclique values, active or negated, for the variables in a clique
nclqvarsnumber of clique variables
isequationdo we have an equation clique at hand?
cliqueclique data structure or NULL
blkmemblock memory
setglobal SCIP settings
statproblem statistics
transprobtransformed problem
origproboriginal problem
treebranch and bound tree if in solving stage
reoptreoptimization data structure
lpcurrent LP data
branchcandbranching candidate storage
eventqueueevent queue
cliquetableclique table data structure
nbdchgspointer to store number of fixed variables
infeasiblepointer to store whether an infeasibility was detected

Definition at line 1860 of file implics.c.

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

Referenced by cliqueCleanup(), and 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
cliquetableclique table data structure
blkmemblock memory
setglobal SCIP settings
statproblem statistics
transprobtransformed problem
origproboriginal problem
treebranch and bound tree if in solving stage
reoptreoptimization data structure
lpcurrent LP data
branchcandbranching candidate storage
eventqueueevent queue
varsbinary variables in the clique: at most one can be set to the given value
valuesvalues of the variables in the clique; NULL to use TRUE for all vars
nvarsnumber of variables in the clique
isequationis the clique an equation or an inequality?
infeasiblepointer to store whether an infeasibility was detected
nbdchgspointer 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().

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
cliqueclique data structure
blkmemblock memory
setglobal SCIP settings
statproblem statistics
transprobtransformed problem
origproboriginal problem
treebranch and bound tree if in solving stage
reoptreoptimization data structure
lpcurrent LP data
branchcandbranching candidate storage
eventqueueevent queue
cliquetableclique table data structure
nchgbdspointer to store number of fixed variables
infeasiblepointer to store whether an infeasibility was detected

Definition at line 2510 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(), SCIPdebugMessage, SCIPvarAddCliqueToList(), SCIPvarDelCliqueFromList(), SCIPvarFixBinary(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegationVar(), SCIPvarGetProbvarBinary(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsMarkedDeleteGlobalStructures(), sortAndMergeClique(), SCIP_Clique::startcleanup, TRUE, SCIP_Clique::values, and SCIP_Clique::vars.

Referenced by 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
cliquetableclique table data structure
blkmemblock memory
setglobal SCIP settings
statproblem statistics
transprobtransformed problem
origproboriginal problem
treebranch and bound tree if in solving stage
reoptreoptimization data structure
lpcurrent LP data
branchcandbranching candidate storage
eventqueueevent queue
nchgbdspointer to store number of fixed variables
infeasiblepointer 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 SCIPvboundsGetNVbds ( SCIP_VBOUNDS vbounds)

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

Parameters
vboundsvariable 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
vboundsvariable 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
vboundsvariable 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
vboundsvariable 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().

int SCIPimplicsGetNImpls ( SCIP_IMPLICS implics,
SCIP_Bool  varfixing 
)

gets number of implications for a given binary variable fixing

Parameters
implicsimplication data
varfixingshould 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
implicsimplication data
varfixingshould 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
implicsimplication data
varfixingshould 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
implicsimplication data
varfixingshould 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
implicsimplication data
varfixingshould 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_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
cliqueclique data structure

Definition at line 3123 of file implics.c.

References NULL, and SCIP_Clique::values.

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

int SCIPcliqueGetId ( SCIP_CLIQUE clique)

gets unique identifier of the clique

Parameters
cliqueclique data structure

Definition at line 3133 of file implics.c.

References SCIP_Clique::id, and NULL.

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

SCIP_Bool SCIPcliqueIsCleanedUp ( SCIP_CLIQUE clique)

gets unique identifier of the clique

Parameters
cliqueclique data structure

Definition at line 3143 of file implics.c.

References NULL, and SCIP_Clique::startcleanup.

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

SCIP_Bool SCIPcliqueIsEquation ( SCIP_CLIQUE clique)

return whether the given clique is an equation

Parameters
cliqueclique data structure

Definition at line 3153 of file implics.c.

References SCIP_Clique::equation, NULL, and SCIP_Bool.

Referenced by SCIPcopyImplicationsCliques(), and separateCuts().

int SCIPcliquelistGetNCliques ( SCIP_CLIQUELIST cliquelist,
SCIP_Bool  value 
)

returns the number of cliques stored in the clique list

Parameters
cliquelistclique list data structure
valuevalue 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
cliquelistclique list data structure
valuevalue 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
cliquelistclique list data structure
varvariable, 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
cliquetableclique 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
cliquetableclique 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
cliquetableclique table data structure

Definition at line 3243 of file implics.c.

References SCIP_CliqueTable::nentries, and NULL.