SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
methods for implications, variable bounds, and cliques
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.
| void SCIPvboundsFree | ( | SCIP_VBOUNDS ** | vbounds, |
| BMS_BLKMEM * | blkmem | ||
| ) |
frees a variable bounds data structure
| vbounds | pointer to store variable bounds data structure |
| blkmem | block memory |
Definition at line 68 of file implics.c.
References BMSfreeBlockMemory, and BMSfreeBlockMemoryArrayNull.
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
| 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 201 of file implics.c.
References FALSE, SCIP_VBounds::len, MAX, 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
| 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 283 of file implics.c.
References 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
| vbounds | pointer to variable bounds data structure |
| blkmem | block memory |
| newnvbds | new number of variable bounds |
Definition at line 328 of file implics.c.
References SCIPvboundsFree().
Referenced by SCIPvarRemoveCliquesImplicsVbs().
| int SCIPvboundsGetNVbds | ( | SCIP_VBOUNDS * | vbounds | ) |
gets number of variable bounds contained in given variable bounds data structure
| vbounds | variable bounds data structure |
Definition at line 3263 of file implics.c.
References SCIP_VBounds::len.
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
| vbounds | variable bounds data structure |
Definition at line 3271 of file implics.c.
References 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
| vbounds | variable bounds data structure |
Definition at line 3279 of file implics.c.
References SCIP_VBounds::coefs.
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
| vbounds | variable bounds data structure |
Definition at line 3287 of file implics.c.
References SCIP_VBounds::constants.
Referenced by SCIPvarAggregate(), SCIPvarGetVlbConstants(), SCIPvarGetVubConstants(), SCIPvarRemoveCliquesImplicsVbs(), and varAddTransitiveImplic().
| void SCIPimplicsFree | ( | SCIP_IMPLICS ** | implics, |
| BMS_BLKMEM * | blkmem | ||
| ) |
frees an implications data structure
| implics | pointer of implications data structure to free |
| blkmem | block memory |
Definition at line 446 of file implics.c.
References BMSfreeBlockMemory, and BMSfreeBlockMemoryArrayNull.
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
| 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 628 of file implics.c.
References BMSmoveMemoryArray, checkImplics(), FALSE, implicsEnsureSize(), implicsSearchImplic(), SCIP_Stat::nimplications, SCIP_Implics::nimpls, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIPsetDebugMsg, SCIPsetIsFeasGE(), SCIPsetIsFeasGT(), SCIPsetIsFeasLE(), SCIPsetIsFeasLT(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), and TRUE.
Referenced by varAddImplic().
| 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
| 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 831 of file implics.c.
References BMSmoveMemoryArray, checkImplics(), implicsSearchImplic(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_OKAY, SCIPimplicsFree(), SCIPsetDebugMsg, 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
| 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 889 of file implics.c.
References implicsSearchVar().
| 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
| 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 911 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
| implics | implication data |
| varfixing | should the implications on var == FALSE or var == TRUE be returned? |
Definition at line 3295 of file implics.c.
References SCIP_Implics::nimpls.
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
| implics | implication data |
| varfixing | should the implications on var == FALSE or var == TRUE be returned? |
Definition at line 3304 of file implics.c.
References 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
| implics | implication data |
| varfixing | should the implications on var == FALSE or var == TRUE be returned? |
Definition at line 3313 of file implics.c.
References 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
| implics | implication data |
| varfixing | should the implications on var == FALSE or var == TRUE be returned? |
Definition at line 3322 of file implics.c.
References SCIP_Implics::bounds.
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.
| implics | implication data |
| varfixing | should the implications on var == FALSE or var == TRUE be returned? |
Definition at line 3334 of file implics.c.
References SCIP_Implics::ids.
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
| 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 1129 of file implics.c.
References BMSmoveMemoryArray, cliqueEnsureSize(), SCIP_Clique::eventsissued, FALSE, SCIP_Clique::id, SCIP_Clique::nvars, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_LOOSE, SCIPsetDebugMsg, SCIPsortedvecFindPtr(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarIsBinary(), TRUE, SCIP_Clique::values, and SCIP_Clique::vars.
Referenced by SCIPvarAddClique().
| void SCIPcliqueDelVar | ( | SCIP_CLIQUE * | clique, |
| SCIP_CLIQUETABLE * | cliquetable, | ||
| SCIP_VAR * | var, | ||
| SCIP_Bool | value | ||
| ) |
removes a single variable from the given clique
| 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 1263 of file implics.c.
References cliquetableMarkCliqueForCleanup(), SCIP_Clique::id, SCIP_CliqueTable::incleanup, SCIP_Clique::index, 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
| cliquelist | pointer to the clique list data structure |
| blkmem | block memory |
Definition at line 1419 of file implics.c.
References BMSfreeBlockMemory, and BMSfreeBlockMemoryArrayNull.
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
| 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 1460 of file implics.c.
References BMSmoveMemoryArray, cliquelistCreate(), cliquelistEnsureSize(), SCIP_Clique::id, SCIP_CliqueList::ncliques, SCIP_CALL, SCIP_OKAY, and SCIPsetDebugMsg.
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
| 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 1505 of file implics.c.
References BMSduplicateBlockMemoryArray, BMSfreeBlockMemoryArray, BMSmoveMemoryArray, cliquesSearchClique(), SCIP_Clique::id, SCIP_CliqueList::ncliques, 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
| 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 1583 of file implics.c.
References SCIP_CliqueList::cliques, FALSE, SCIP_CliqueList::ncliques, 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
| 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 1661 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, 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
| cliquetable | pointer to store clique table data structure |
| set | global SCIP settings |
| blkmem | block memory |
Definition at line 1766 of file implics.c.
References BMSallocMemory, FALSE, HASHTABLE_CLIQUETABLE_SIZE, MAX, SCIP_ALLOC, SCIP_CALL, SCIP_HASHSIZE_CLIQUES, SCIP_HASHSIZE_CLIQUES_SMALL, SCIP_OKAY, and SCIPhashtableCreate().
Referenced by SCIPtransformProb().
| SCIP_RETCODE SCIPcliquetableFree | ( | SCIP_CLIQUETABLE ** | cliquetable, |
| BMS_BLKMEM * | blkmem | ||
| ) |
frees a clique table data structure
| cliquetable | pointer to store clique table data structure |
| blkmem | block memory |
Definition at line 1802 of file implics.c.
References BMSfreeMemory, BMSfreeMemoryArrayNull, cliqueFree(), SCIP_OKAY, SCIPdisjointsetFree(), SCIPhashmapFree(), 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
| 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 2358 of file implics.c.
References cliqueCheck, cliqueCreateWithData(), cliqueFree(), SCIP_CliqueTable::cliques, cliquetableEnsureSize(), cliquetableUpdateConnectednessClique(), SCIP_Clique::equation, FALSE, SCIP_CliqueTable::hashtable, SCIP_Clique::id, SCIP_Clique::index, SCIP_CliqueTable::ncliques, SCIP_CliqueTable::ncreatedcliques, SCIP_CliqueTable::nentries, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARSTATUS_COLUMN, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_LOOSE, SCIP_VARSTATUS_MULTAGGR, SCIPdebugCheckClique, SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPsetAllocBufferArray, SCIPsetDebugMsg, SCIPsetDuplicateBufferArray, SCIPsetFreeBufferArray, SCIPvarFixBinary(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), SCIPvarIsMarkedDeleteGlobalStructures(), SCIPvarsAddClique(), SCIPvarsGetProbvarBinary(), sortAndMergeClique(), 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
removes all empty and single variable cliques from the clique table; removes double entries from the clique table
| 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 2893 of file implics.c.
References 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, SCIP_Clique::nvars, SCIP_Bool, SCIP_CALL, 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().
| 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
| cliquetable | clique table data structure |
| set | global SCIP settings |
| blkmem | block memory |
| vars | array of problem variables, sorted by variable type |
| nbinvars | number of binary variables |
| nintvars | number of integer variables |
| nimplvars | number of implicit integer variables |
Definition at line 3104 of file implics.c.
References SCIP_CliqueTable::cliques, cliquetableUpdateConnectednessClique(), SCIP_CliqueTable::compsfromscratch, SCIP_CliqueTable::djset, FALSE, SCIP_CliqueTable::ncliquecomponents, SCIP_CliqueTable::ncliques, SCIP_CALL, SCIP_OKAY, SCIPdisjointsetCreate(), SCIPdisjointsetFree(), SCIPdisjointsetGetComponentCount(), SCIPhashmapCreate(), SCIPhashmapInsert(), SCIPhashmapRemoveAll(), SCIPsetDebugMsg, SCIPvarGetProbvar(), SCIPvarIsActive(), SCIPvarIsBinary(), and SCIP_CliqueTable::varidxtable.
Referenced by SCIPcalcCliquePartition().
| 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
| cliquetable | clique table data structure |
| var | problem variable |
Definition at line 2330 of file implics.c.
References cliquetableGetNodeIndexBinvar(), SCIP_CliqueTable::djset, SCIPdisjointsetFind(), SCIPdisjointsetGetSize(), and SCIPvarIsBinary().
Referenced by SCIPcalcCliquePartition().
| int SCIPcliquelistGetNCliques | ( | SCIP_CLIQUELIST * | cliquelist, |
| SCIP_Bool | value | ||
| ) |
returns the number of cliques stored in the clique list
| cliquelist | clique list data structure |
| value | value of the variable for which the cliques should be returned |
Definition at line 3419 of file implics.c.
References SCIP_CliqueList::ncliques.
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
| cliquelist | clique list data structure |
| value | value of the variable for which the cliques should be returned |
Definition at line 3428 of file implics.c.
References SCIP_CliqueList::cliques.
Referenced by SCIPcliquelistCheck(), and SCIPvarGetCliques().
| void SCIPcliquelistCheck | ( | SCIP_CLIQUELIST * | cliquelist, |
| SCIP_VAR * | var | ||
| ) |
checks whether variable is contained in all cliques of the cliquelist
| cliquelist | clique list data structure |
| var | variable, the clique list belongs to |
Definition at line 3437 of file implics.c.
References FALSE, 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
| cliquetable | clique table data structure |
Definition at line 3479 of file implics.c.
References SCIP_CliqueTable::ncliques.
Referenced by presolve(), SCIPgetNCliques(), SCIPhaveVarsCommonClique(), and SCIPisPresolveFinished().
| int SCIPcliquetableGetNCliquesCreated | ( | SCIP_CLIQUETABLE * | cliquetable | ) |
gets the number of cliques created so far by the clique table
| cliquetable | clique table data structure |
Definition at line 3489 of file implics.c.
References SCIP_CliqueTable::ncreatedcliques.
Referenced by SCIPgetNCliquesCreated().
| SCIP_CLIQUE** SCIPcliquetableGetCliques | ( | SCIP_CLIQUETABLE * | cliquetable | ) |
gets the array of cliques stored in the clique table
| cliquetable | clique table data structure |
Definition at line 3499 of file implics.c.
References SCIP_CliqueTable::cliques.
Referenced by SCIPgetCliques().
| SCIP_Longint SCIPcliquetableGetNEntries | ( | SCIP_CLIQUETABLE * | cliquetable | ) |
gets the number of entries in the whole clique table
| cliquetable | clique table data structure |
Definition at line 3509 of file implics.c.
References SCIP_CliqueTable::nentries.
| int SCIPcliquetableGetNCliqueComponents | ( | SCIP_CLIQUETABLE * | cliquetable | ) |
returns the number of clique components, or -1 if update is necessary first
| cliquetable | clique table data structure |
Definition at line 3519 of file implics.c.
References SCIP_CliqueTable::compsfromscratch, and SCIP_CliqueTable::ncliquecomponents.
| SCIP_Bool SCIPcliquetableNeedsComponentUpdate | ( | SCIP_CLIQUETABLE * | cliquetable | ) |
returns TRUE iff the connected clique components need an update (because new cliques were added)
| cliquetable | clique table data structure |
Definition at line 3527 of file implics.c.
References SCIP_CliqueTable::compsfromscratch, and SCIP_CliqueTable::djset.
Referenced by SCIPcalcCliquePartition().