SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
implics.h File Reference

Detailed Description

methods for implications, variable bounds, and cliques

Author
Tobias Achterberg

Definition in file implics.h.

#include "blockmemshell/memory.h"
#include "scip/def.h"
#include "scip/type_branch.h"
#include "scip/type_event.h"
#include "scip/type_implics.h"
#include "scip/type_lp.h"
#include "scip/type_prob.h"
#include "scip/type_reopt.h"
#include "scip/type_retcode.h"
#include "scip/type_set.h"
#include "scip/type_stat.h"
#include "scip/type_tree.h"
#include "scip/type_var.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_RealSCIPvboundsGetCoefs (SCIP_VBOUNDS *vbounds)
 
SCIP_RealSCIPvboundsGetConstants (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)
 
void SCIPimplicsGetVarImplicPoss (SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, int *haslowerimplic, int *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_BOUNDTYPESCIPimplicsGetTypes (SCIP_IMPLICS *implics, SCIP_Bool varfixing)
 
SCIP_RealSCIPimplicsGetBounds (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)
 
SCIP_RETCODE SCIPcliquetableComputeCliqueComponents (SCIP_CLIQUETABLE *cliquetable, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_VAR **vars, int nbinvars, int nintvars, int nimplvars)
 
int SCIPcliquetableGetVarComponentIdx (SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var)
 
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)
 

Function Documentation

◆ SCIPvboundsFree()

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

References assert(), BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

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

References assert(), FALSE, i, MAX, MIN, NULL, SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIP_VARTYPE_CONTINUOUS, SCIPsetIsZero(), SCIPvarGetStatus(), SCIPvarGetType(), TRUE, var, 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
vboundspointer to variable bounds data structure
blkmemblock memory
vbdvarvariable z in x >=/<= b*z + d
negativecoefis coefficient b negative?

Definition at line 288 of file implics.c.

References assert(), i, 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
vboundspointer to variable bounds data structure
blkmemblock memory
newnvbdsnew number of variable bounds

Definition at line 333 of file implics.c.

References assert(), NULL, and SCIPvboundsFree().

Referenced by SCIPvarRemoveCliquesImplicsVbs().

◆ SCIPvboundsGetNVbds()

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 3290 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
vboundsvariable bounds data structure

Definition at line 3298 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
vboundsvariable bounds data structure

Definition at line 3306 of file implics.c.

References SCIP_VBounds::coefs, NULL, and SCIP_Real.

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
vboundsvariable bounds data structure

Definition at line 3314 of file implics.c.

References SCIP_VBounds::constants, NULL, and SCIP_Real.

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

◆ SCIPimplicsFree()

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

References assert(), BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

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

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

References assert(), BMSmoveMemoryArray, checkImplics(), FALSE, implicsEnsureSize(), implicsSearchImplic(), SCIP_Stat::nimplications, NULL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, 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
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 836 of file implics.c.

References assert(), 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
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 894 of file implics.c.

References assert(), implicsSearchVar(), NULL, and SCIP_Bool.

◆ SCIPimplicsGetVarImplicPoss()

void SCIPimplicsGetVarImplicPoss ( SCIP_IMPLICS * implics,
SCIP_Bool varfixing,
SCIP_VAR * implvar,
int * lowerimplicpos,
int * upperimplicpos )

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
lowerimplicpospointer to store the position of an implication y >= l
upperimplicpospointer to store the position of an implication y <= u

Definition at line 916 of file implics.c.

References assert(), implicsSearchVar(), NULL, and SCIP_Bool.

Referenced by SCIPvarGetImplicVarBounds().

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

References implicsSearchImplic(), and SCIP_Bool.

Referenced by SCIPvarHasImplic().

◆ SCIPimplicsGetNImpls()

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

References SCIP_Implics::nimpls, NULL, and SCIP_Bool.

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
implicsimplication data
varfixingshould the implications on var == FALSE or var == TRUE be returned?

Definition at line 3331 of file implics.c.

References NULL, SCIP_Bool, 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
implicsimplication data
varfixingshould the implications on var == FALSE or var == TRUE be returned?

Definition at line 3340 of file implics.c.

References NULL, SCIP_Bool, 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
implicsimplication data
varfixingshould the implications on var == FALSE or var == TRUE be returned?

Definition at line 3349 of file implics.c.

References SCIP_Implics::bounds, NULL, SCIP_Bool, and SCIP_Real.

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
implicsimplication data
varfixingshould the implications on var == FALSE or var == TRUE be returned?

Definition at line 3361 of file implics.c.

References SCIP_Implics::ids, NULL, and SCIP_Bool.

Referenced by SCIPvarGetImplIds().

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

References assert(), BMSmoveMemoryArray, cliqueEnsureSize(), FALSE, i, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIPsetDebugMsg, SCIPsortedvecFindPtr(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarIsBinary(), TRUE, and var.

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

Definition at line 1285 of file implics.c.

References assert(), cliquetableMarkCliqueForCleanup(), SCIP_CliqueTable::incleanup, NULL, nvars, SCIP_Bool, SCIPcliqueSearchVar(), SCIPdebugMessage, SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and var.

Referenced by SCIPcliquelistRemoveFromCliques(), and SCIPvarDelClique().

◆ SCIPcliquelistFree()

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

References assert(), BMSfreeBlockMemory, BMSfreeBlockMemoryArrayNull, and NULL.

Referenced by SCIPcliquelistDel(), and varFree().

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

References assert(), BMSmoveMemoryArray, cliquelistCreate(), cliquelistEnsureSize(), i, NULL, SCIP_Bool, 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
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 1527 of file implics.c.

References assert(), BMSduplicateBlockMemoryArray, BMSfreeBlockMemoryArray, BMSmoveMemoryArray, cliquesSearchClique(), 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
cliquelist1first clique list data structure
value1value of first variable
cliquelist2second clique list data structure
value2value of second variable

Definition at line 1605 of file implics.c.

References assert(), SCIP_CliqueList::cliques, FALSE, SCIP_CliqueList::ncliques, NULL, SCIP_Bool, 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
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 1683 of file implics.c.

References assert(), cliqueCheck, SCIP_CliqueList::cliques, FALSE, i, SCIP_CliqueTable::incleanup, SCIP_CliqueList::ncliques, NULL, SCIP_Bool, SCIPcliqueDelVar(), SCIPdebugMessage, SCIPvarGetCliques(), SCIPvarGetName(), SCIPvarGetNCliques(), SCIPvarIsBinary(), and var.

Referenced by SCIPvarRemoveCliquesImplicsVbs().

◆ SCIPcliquetableCreate()

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

References assert(), 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
cliquetablepointer to store clique table data structure
blkmemblock memory

Definition at line 1822 of file implics.c.

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

Referenced by freeTransform(), and freeTransforming().

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

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

Referenced by SCIPaddClique(), and varAddImplic().

◆ 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

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

References assert(), checkNEntries, cliqueCheck, cliqueCleanup(), cliqueFree(), SCIP_CliqueTable::cliques, cliquetableSwapCliques(), SCIP_Clique::equation, FALSE, SCIP_CliqueTable::hashtable, 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_LONGINT_FORMAT, SCIP_OKAY, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIPcliqueIsCleanedUp(), SCIPeventCreateImplAdded(), SCIPeventqueueAdd(), SCIPeventqueueDelay(), SCIPeventqueueProcess(), SCIPhashtableInsert(), SCIPhashtableRemove(), SCIPhashtableRetrieve(), SCIPsetDebugMsg, SCIPsetGetStage(), SCIPvarDelCliqueFromList(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarTryAggregateVars(), and TRUE.

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 graph

use depth-first search similarly to the components presolver/constraint handler, representing a clique as a path to reduce memory usage, but leaving the connected components the same

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

computes connected components of the clique table

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

Parameters
cliquetableclique table data structure
setglobal SCIP settings
blkmemblock memory
varsarray of problem variables, sorted by variable type
nbinvarsnumber of binary variables
nintvarsnumber of integer variables
nimplvarsnumber of implicit integer variables

Definition at line 3131 of file implics.c.

References assert(), c, SCIP_CliqueTable::cliques, cliquetableUpdateConnectednessClique(), SCIP_CliqueTable::compsfromscratch, SCIP_CliqueTable::djset, FALSE, nbinvars, SCIP_CliqueTable::ncliquecomponents, SCIP_CliqueTable::ncliques, nintvars, NULL, SCIP_CALL, SCIP_OKAY, SCIPdisjointsetCreate(), SCIPdisjointsetFree(), SCIPdisjointsetGetComponentCount(), SCIPhashmapCreate(), SCIPhashmapInsertInt(), SCIPhashmapRemoveAll(), SCIPsetDebugMsg, SCIPvarGetProbvar(), SCIPvarIsActive(), SCIPvarIsBinary(), var, SCIP_CliqueTable::varidxtable, and vars.

Referenced by SCIPcalcCliquePartition().

◆ 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
cliquetableclique table data structure
varproblem variable

Definition at line 2348 of file implics.c.

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

Referenced by SCIPcalcCliquePartition().

◆ SCIPcliquelistGetNCliques()

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

References SCIP_CliqueList::ncliques, NULL, and SCIP_Bool.

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
cliquelistclique list data structure
valuevalue of the variable for which the cliques should be returned

Definition at line 3455 of file implics.c.

References SCIP_CliqueList::cliques, NULL, and SCIP_Bool.

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
cliquelistclique list data structure
varvariable, the clique list belongs to

Definition at line 3464 of file implics.c.

References assert(), FALSE, i, NULL, nvars, SCIP_Bool, SCIPcliquelistGetCliques(), SCIPcliquelistGetNCliques(), SCIPcliqueSearchVar(), SCIPvarGetCliques(), SCIPvarGetNCliques(), TRUE, and var.

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

◆ SCIPcliquetableGetNCliques()

int SCIPcliquetableGetNCliques ( SCIP_CLIQUETABLE * cliquetable)

gets the number of cliques stored in the clique table

Parameters
cliquetableclique table data structure

Definition at line 3506 of file implics.c.

References assert(), 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
cliquetableclique table data structure

Definition at line 3516 of file implics.c.

References assert(), 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
cliquetableclique table data structure

Definition at line 3526 of file implics.c.

References assert(), 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
cliquetableclique table data structure

Definition at line 3536 of file implics.c.

References assert(), SCIP_CliqueTable::nentries, NULL, and SCIP_Longint.

Referenced by SCIPcliquetableAdd(), and SCIPprintTransProblemStatistics().

◆ SCIPcliquetableGetNCliqueComponents()

int SCIPcliquetableGetNCliqueComponents ( SCIP_CLIQUETABLE * cliquetable)

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

Parameters
cliquetableclique table data structure

Definition at line 3546 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
cliquetableclique table data structure

Definition at line 3554 of file implics.c.

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

Referenced by SCIPcalcCliquePartition().