implics.c
Go to the documentation of this file.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
105 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->coefs, (*vbounds)->size, newsize) );
106 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->constants, (*vbounds)->size, newsize) );
114 /** binary searches the insertion position of the given variable in the vbounds data structure */
121 SCIP_Bool* found /**< pointer to store whether the same variable was found at the returned pos */
213 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
232 if( constant + MIN(coef, 0.0) < (*vbounds)->constants[insertpos] + MIN((*vbounds)->coefs[insertpos], 0.0) )
241 if( constant + MAX(coef, 0.0) > (*vbounds)->constants[insertpos] + MAX((*vbounds)->coefs[insertpos], 0.0) )
463 /** ensures, that arrays for x == 0 or x == 1 in implications data structure can store at least num entries */
469 SCIP_Bool varfixing, /**< FALSE if size of arrays for x == 0 has to be ensured, TRUE for x == 1 */
488 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->vars[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
489 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->types[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
490 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->bounds[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
491 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->ids[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
499 /** gets the positions of the implications y >= l and y <= u in the implications data structure;
534 found = SCIPsortedvecFindPtr((void**)(&(implics->vars[varfixing][0])), SCIPvarComp, (void*)implvar, right + 1, &pos);
583 /** returns whether variable y is already contained in implications for x == 0 or x == 1 with the given impltype
631 SCIP_BOUNDTYPE impltype, /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
633 SCIP_Bool isshortcut, /**< is the implication a shortcut, i.e., added as part of the transitive closure of another implication? */
634 SCIP_Bool* conflict, /**< pointer to store whether implication causes a conflict for variable x */
650 assert(SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_LOOSE);
651 assert((impltype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGT(set, implbound, SCIPvarGetLbGlobal(implvar)))
652 || (impltype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLT(set, implbound, SCIPvarGetUbGlobal(implvar))));
657 (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbound);
667 found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd);
689 SCIPsetDebugMsg(set, " -> implication is redundant to <%s> >= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]);
696 SCIPsetDebugMsg(set, " -> implication is conflicting to <%s> <= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]);
733 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/
734 BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/
735 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/
736 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/
758 SCIPsetDebugMsg(set, " -> implication is redundant to <%s> <= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]);
765 SCIPsetDebugMsg(set, " -> implication is conflicting to <%s> >= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]);
802 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/
803 BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/
804 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/
805 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/
826 /** removes the implication x <= 0 or x >= 1 ==> y <= b or y >= b from the implications data structure */
831 SCIP_Bool varfixing, /**< FALSE if y should be removed from implications for x <= 0, TRUE for x >= 1 */
833 SCIP_BOUNDTYPE impltype /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
846 (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=");
851 found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd);
869 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd]), &((*implics)->types[varfixing][posadd+1]), amount); /*lint !e866*/
870 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd]), &((*implics)->vars[varfixing][posadd+1]), amount); /*lint !e866*/
871 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd]), &((*implics)->bounds[varfixing][posadd+1]), amount); /*lint !e866*/
884 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */
887 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
906 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */
909 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
923 /** returns whether an implication y <= b or y >= b is contained in implications for x == 0 or x == 1 */
926 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
935 return implicsSearchImplic(implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd); /*lint !e438*/
993 /** creates a clique data structure with already created variables and values arrays in the size of 'size' */
1069 /** returns the position of the given variable/value pair in the clique; returns -1 if variable/value pair is not member
1148 SCIP_Bool* doubleentry, /**< pointer to store whether the variable and value occurs twice in the clique */
1149 SCIP_Bool* oppositeentry /**< pointer to store whether the variable with opposite value is in the clique */
1156 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
1161 SCIPsetDebugMsg(set, "adding variable <%s> == %u to clique %u\n", SCIPvarGetName(var), value, clique->id);
1169 /* search for insertion position by binary variable, note that first the entries are order after variable index and
1191 for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] == value; ++pos ); /*lint !e722*/
1206 for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value; --pos ); /*lint !e722*/
1230 for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] != value; ++pos ); /*lint !e722*/
1254 for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] == value; --pos ); /*lint !e722*/
1289 /* if the clique is the leading clique during the cleanup step, we do not need to insert it again */
1293 SCIPdebugMessage("marking variable <%s> == %u from clique %u for deletion\n", SCIPvarGetName(var), value, clique->id);
1322 /** gets the position of the given clique in the cliques array; returns -1 if clique is not member of cliques array */
1394 /* assert that the clique is correctly listed in all clique lists of unfixed variables. For fixed variables,
1464 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &cliquelist->cliques[value], cliquelist->size[value], newsize) ); /*lint !e866*/
1498 for( i = (*cliquelist)->ncliques[value]; i > 0 && (*cliquelist)->cliques[value][i - 1]->id > id; --i ); /*lint !e574 !e722*/
1504 SCIP_CALL( cliquelistEnsureSize(*cliquelist, blkmem, set, value, (*cliquelist)->ncliques[value] + 1) );
1509 BMSmoveMemoryArray(&((*cliquelist)->cliques[value][i+1]), &((*cliquelist)->cliques[value][i]), (*cliquelist)->ncliques[value] - i); /*lint !e866*/
1529 /* if a variable appeared twice in its last clique and is now removed both times, the cliquelist is already cleaned
1537 pos = cliquesSearchClique((*cliquelist)->cliques[value], (*cliquelist)->ncliques[value], clique);
1539 /* clique does not exist in cliquelist, the clique should contain multiple entries of the same variable */
1552 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvars, SCIPcliqueGetVars(clique), nclqvars) );
1553 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvalues, SCIPcliqueGetValues(clique), nclqvars) );
1582 BMSmoveMemoryArray(&((*cliquelist)->cliques[value][pos]), &((*cliquelist)->cliques[value][pos+1]),
1593 /** returns whether the given clique lists have a non-empty intersection, i.e. whether there is a clique that appears
1644 /* if last item in clique1 has a smaller index than the actual clique in clique2, than cause of increasing order
1656 /* if last item in clique2 has a smaller index than the actual clique in clique1, than cause of increasing order
1717 /* during the cleanup step, we skip the consistency check because clique may be temporarily inconsistent */
1751 /* the variables are sorted: we can simply check the equality of each pair of variable/values */
1791 hashtablesize = MAX(hashtablesize, (set->misc_usesmalltables ? SCIP_HASHSIZE_CLIQUES_SMALL : SCIP_HASHSIZE_CLIQUES));
1899 SCIPsetDebugMsg(set, "starting merging %d variables in clique %d\n", *nclqvars, (clique == NULL) ? -1 : (int) clique->id);
1916 /* sort variables and corresponding clique values regarding variables indices before merging multiples */
1920 /* check for multiple occurences or pairs of negations in the variable array, this should be very rare when creating a
1932 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
1935 /* the counters denote the occurrences of the variable var with value TRUE and FALSE as clqvalues, respectively */
2004 SCIP_CALL( SCIPvarFixBinary(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2007 SCIPsetDebugMsg(set, "same var %s twice in a clique with value %d fixed to %d (was %s)\n", SCIPvarGetName(var), fixvalue ? 0 : 1,
2017 SCIPsetDebugMsg(set, "var %s is paired with its negation in one clique -> fix all other variables\n", SCIPvarGetName(var));
2019 /* a pair of negated variables in one clique forces all other variables in the clique to be zero */
2058 SCIP_CALL( SCIPvarFixBinary(clqvars[w], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2061 SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[w]), clqvalues[w],
2094 * @note that if we are in probing or solving stage, the fixation on the variable might not be carried out yet,
2120 if( (clqvalues[startidx] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[startidx] && SCIPvarGetUbGlobal(var) < 0.5) )
2126 SCIPsetDebugMsg(set, "two variables in clique %d fixed to one %s%s and %s%s\n", (clique != NULL) ? (int) clique->id : -1,
2127 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clqvalues[startidx] ? "" : "~", SCIPvarGetName(clqvars[startidx]));
2147 assert((SCIPvarGetUbGlobal(var) < 0.5 && clqvalues[startidx]) || (SCIPvarGetLbGlobal(var) > 0.5 && !clqvalues[startidx]));
2163 SCIPsetDebugMsg(set, "variable %s%s in clique %d fixed to one, fixing all other variables to zero\n",
2164 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), (clique != NULL) ? (int) clique->id : -1);
2194 SCIPsetDebugMsg(set, "fixing variable %s in clique %d to %d\n", SCIPvarGetName(clqvars[startidx]), (clique != NULL) ? (int) clique->id : -1,
2198 SCIP_CALL( SCIPvarFixBinary(clqvars[startidx], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2236 SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2239 SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0],
2250 /** helper function that returns the graph node index for a variable during connected component detection */
2278 /* if the map does not contain an index for this variable, return -1 and mark that the components must be
2338 /** returns the index of the connected component of the clique graph that the variable belongs to, or -1 */
2379 SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given value */
2380 SCIP_Bool* values, /**< values of the variables in the clique; NULL to use TRUE for all vars */
2399 SCIPsetDebugMsg(set, "trying to add clique %d with %d vars to clique table\n", cliquetable->ncliques, nvars);
2438 ((clqvalues[v] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[v] && SCIPvarGetUbGlobal(var) < 0.5)) )
2440 SCIPsetDebugMsg(set, "in a clique var %s with value %u is fixed to %d -> fix the rest\n", SCIPvarGetName(var), clqvalues[v], clqvalues[v] ? 1 : 0);
2446 /* the rare case where the same variable appears several times is handled later during sort and merge */
2451 /* check if variable is fixed already and terminate with infeasible if this fixing contradicts the clique info */
2466 /* the following piece of code is disabled because it assumes the clqvars to be sorted which they aren't until the method
2489 SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvar), clqval,
2503 (SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN && SCIPvarGetStatus(var) != SCIP_VARSTATUS_LOOSE) ||
2509 isequation = isequation && !(SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR) && ! SCIPvarIsMarkedDeleteGlobalStructures(var);
2531 SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2534 SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0],
2554 SCIP_CALL( sortAndMergeClique(clqvars, clqvalues, &nvars, &isequation, NULL, blkmem, set, stat, transprob, origprob, tree,
2564 if( !SCIPsetIsInfinity(set, set->presol_clqtablefac) && SCIPcliquetableGetNEntries(cliquetable) + nvars > set->presol_clqtablefac * stat->nnz )
2566 SCIPsetDebugMsg(set, "reject %d-variable clique to keep clique table entries below threshold of %g entries\n",
2580 SCIP_CALL( cliqueCreateWithData(&clique, blkmem, nvars, clqvars, clqvalues, nvars, cliquetable->ncreatedcliques, isequation) );
2605 SCIPsetDebugMsg(set, "same clique %p (id: %d) already found in cliquetable -> discard new one\n", (void*) sameclique, sameclique->id);
2608 /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove
2671 SCIPsetDebugMsg(set, "Starting clean up of clique %u (size %d) from position %d\n", clique->id, clique->nvars, w);
2676 SCIP_Bool addvartoclique; /* has the variable status changed such that it needs to be replaced by an active representative? */
2704 /* check for variables that are either fixed to zero or marked for deletion from global structures */
2756 SCIPsetDebugMsg(set, "variable %s%s in clique %u fixed to one, fixing all other variables to zero\n",
2769 /* the variable could have been fixed already because it appears more than once in the clique */
2791 /* the following piece of code is wrong at this point because it assumes sorted variables. can be enabled if sorting
2809 SCIPsetDebugMsg(set, "fixing variable %s in clique %u to %d\n", SCIPvarGetName(clqvar), clique->id, clqval ? 0 : 1);
2811 SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2847 SCIPsetDebugMsg(set, "fixing last variable %s in clique %u to %d\n", SCIPvarGetName(clique->vars[0]), clique->id,
2850 SCIP_CALL( SCIPvarFixBinary(clique->vars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2866 SCIP_CALL( sortAndMergeClique(clique->vars, clique->values, &(clique->nvars), &isequation, clique, blkmem, set, stat,
2867 transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, nchgbds, infeasible) );
2902 /** removes all empty and single variable cliques from the clique table; removes double entries from the clique table
2936 SCIPsetDebugMsg(set, "cleaning up clique table with %d cliques (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
2956 SCIP_CALL( cliqueCleanup(clique, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
3025 assert((SCIPvarGetStatus(var0) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var0) == SCIP_VARSTATUS_COLUMN)
3026 && (SCIPvarGetStatus(var1) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_COLUMN));
3039 /* check if the clique is already contained in the clique table, or if it is redundant (too small) */
3047 /* if the clique which is already in the hashtable is an inequality and the current clique is an equation, we
3054 /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove
3073 cliquetable->cliques[cliquetable->ndirtycliques] = cliquetable->cliques[cliquetable->ncliques];
3100 /* remember the number of fixed variables and cliques in order to avoid unnecessary cleanups */
3107 SCIPsetDebugMsg(set, "cleaned up clique table has %d cliques left (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
3146 /* detect integer and implicit integer variables with bounds {0,1} because they might appear in cliques, as well */
3159 SCIPsetDebugMsg(set, "0 binary variables in total --> 0 connected components in the clique table");
3182 /* loop through variables and store their respective positions in the hash map if they are binary */
3204 /* free previous disjoint set (union find) data structure which has become outdated if new variables are present */
3208 /* we need to consider integer and implicit integer variables for which SCIPvarIsBinary() returns TRUE.
3210 * For simplicity, we add all integer and implicit integer variables as nodes to the graph, and subtract
3223 * if the graph turns out to be completely connected (except for the nonbinary variables), we terminate */
3224 for( c = 0; c < cliquetable->ncliques && SCIPdisjointsetGetComponentCount(djset) > 1 + nnonbinvars; ++c )
3237 SCIPsetDebugMsg(set, "connected components detection: %d comps (%d clqs, %d vars)", cliquetable->ncliquecomponents, cliquetable->ncliques, nbinvarstotal);
3312 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3321 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3330 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3339 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3346 * If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication,
3351 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3377 /** gets array of values of active problem variables in the cliques, i.e. whether the variable is fixed to FALSE or
3457 /* @todo might need to change ifndef NDEBUG to ifdef SCIP_MORE_DEBUG because it can take at lot of time to check for
3541 /** returns TRUE iff the connected clique components need an update (because new cliques were added) */
void SCIPcliquelistRemoveFromCliques(SCIP_CLIQUELIST *cliquelist, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Bool irrelevantvar)
Definition: implics.c:1674
Definition: struct_implics.h:39
static int cliquetableGetNodeIndexBinvar(SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *binvar)
Definition: implics.c:2252
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:461
internal methods for managing events
int SCIPcliquetableGetVarComponentIdx(SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var)
Definition: implics.c:2339
static SCIP_Bool implicsSearchImplic(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype, int *poslower, int *posupper, int *posadd)
Definition: implics.c:587
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11175
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2487
void SCIPimplicsGetVarImplics(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_Bool *haslowerimplic, SCIP_Bool *hasupperimplic)
Definition: implics.c:885
SCIP_RETCODE SCIPeventqueueProcess(SCIP_EVENTQUEUE *eventqueue, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter)
Definition: event.c:2487
SCIP_Longint SCIPcliquetableGetNEntries(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3524
SCIP_RETCODE SCIPcliqueAddVar(SCIP_CLIQUE *clique, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_VAR *var, SCIP_Bool value, SCIP_Bool *doubleentry, SCIP_Bool *oppositeentry)
Definition: implics.c:1142
#define SCIPsetDuplicateBufferArray(set, ptr, source, num)
Definition: set.h:1727
public methods for implications, variable bounds, and cliques
methods for implications, variable bounds, and cliques
SCIP_RETCODE SCIPeventqueueAdd(SCIP_EVENTQUEUE *eventqueue, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_PRIMAL *primal, SCIP_LP *lp, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter, SCIP_EVENT **event)
Definition: event.c:2231
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:12309
SCIP_RETCODE SCIPeventCreateImplAdded(SCIP_EVENT **event, BMS_BLKMEM *blkmem, SCIP_VAR *var)
Definition: event.c:805
SCIP_VAR ** SCIPimplicsGetVars(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3319
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18273
static SCIP_RETCODE cliquetableEnsureSize(SCIP_CLIQUETABLE *cliquetable, SCIP_SET *set, int num)
Definition: implics.c:1850
int SCIPcliquelistGetNCliques(SCIP_CLIQUELIST *cliquelist, SCIP_Bool value)
Definition: implics.c:3434
Definition: struct_var.h:198
SCIP_Bool SCIPcliqueHasVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1132
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)
Definition: implics.c:2637
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
static SCIP_RETCODE implicsEnsureSize(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool varfixing, int num)
Definition: implics.c:465
SCIP_RETCODE SCIPeventqueueDelay(SCIP_EVENTQUEUE *eventqueue)
Definition: event.c:2472
SCIP_RETCODE SCIPvboundsDel(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem, SCIP_VAR *vbdvar, SCIP_Bool negativecoef)
Definition: implics.c:279
SCIP_RETCODE SCIPcliquetableCreate(SCIP_CLIQUETABLE **cliquetable, SCIP_SET *set, BMS_BLKMEM *blkmem)
Definition: implics.c:1777
void SCIPimplicsGetVarImplicPoss(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, int *lowerimplicpos, int *upperimplicpos)
Definition: implics.c:907
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
static SCIP_RETCODE cliquelistCreate(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem)
Definition: implics.c:1413
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)
Definition: implics.c:2908
Definition: struct_prob.h:39
public methods for problem variables
SCIP_RETCODE SCIPimplicsDel(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: implics.c:827
SCIP_RETCODE SCIPcliquetableFree(SCIP_CLIQUETABLE **cliquetable, BMS_BLKMEM *blkmem)
Definition: implics.c:1813
SCIP_CLIQUE ** SCIPcliquelistGetCliques(SCIP_CLIQUELIST *cliquelist, SCIP_Bool value)
Definition: implics.c:3443
SCIP_RETCODE SCIPcliquelistAdd(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: implics.c:1473
static void implicsSearchVar(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, int *poslower, int *posupper, int *posadd)
Definition: implics.c:503
Definition: heur_padm.c:123
static void cliquetableSwapCliques(SCIP_CLIQUETABLE *cliquetable, int first, int second)
Definition: implics.c:947
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2236
static void cliquetableMarkCliqueForCleanup(SCIP_CLIQUETABLE *cliquetable, SCIP_CLIQUE *clique)
Definition: implics.c:973
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)
Definition: implics.c:197
int SCIPcliquetableGetNCliquesCreated(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3504
Definition: struct_set.h:63
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
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)
Definition: implics.c:995
void SCIPcliquelistFree(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem)
Definition: implics.c:1432
int SCIPcliqueSearchVar(SCIP_CLIQUE *clique, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1072
int SCIPcliquetableGetNCliques(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3494
#define BMSduplicateBlockMemoryArray(mem, ptr, source, num)
Definition: memory.h:455
SCIP_BOUNDTYPE * SCIPimplicsGetTypes(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3328
void SCIPcliqueDelVar(SCIP_CLIQUE *clique, SCIP_CLIQUETABLE *cliquetable, SCIP_VAR *var, SCIP_Bool value)
Definition: implics.c:1276
SCIP_Bool SCIPimplicsContainsImpl(SCIP_IMPLICS *implics, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype)
Definition: implics.c:924
void SCIPdisjointsetFree(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem)
Definition: misc.c:11226
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)
Definition: implics.c:624
void SCIPsortPtrBool(void **ptrarray, SCIP_Bool *boolarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
Definition: type_lp.h:47
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
static int cliquesSearchClique(SCIP_CLIQUE **cliques, int ncliques, SCIP_CLIQUE *clique)
Definition: implics.c:1324
Definition: type_var.h:42
Definition: type_var.h:44
internal miscellaneous methods
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11148
Definition: type_retcode.h:33
Definition: struct_event.h:152
internal methods for global SCIP settings
SCIP_Bool SCIPsetIsFeasGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6686
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2617
SCIP_Real * SCIPvboundsGetConstants(SCIP_VBOUNDS *vbounds)
Definition: implics.c:3302
Definition: graph_load.c:93
static void cliquetableUpdateConnectednessClique(SCIP_CLIQUETABLE *cliquetable, SCIP_CLIQUE *clique)
Definition: implics.c:2295
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
Definition: misc.c:11245
SCIP_Bool SCIPcliquelistsHaveCommonClique(SCIP_CLIQUELIST *cliquelist1, SCIP_Bool value1, SCIP_CLIQUELIST *cliquelist2, SCIP_Bool value2)
Definition: implics.c:1596
SCIP_Bool SCIPsetIsFeasLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6642
Definition: struct_implics.h:80
int SCIPcliquetableGetNCliqueComponents(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3534
void SCIPvboundsShrink(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem, int newnvbds)
Definition: implics.c:324
internal methods for problem variables
SCIP_RETCODE SCIPvarTryAggregateVars(SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_PROB *origprob, SCIP_PRIMAL *primal, SCIP_TREE *tree, SCIP_REOPT *reopt, SCIP_LP *lp, SCIP_CLIQUETABLE *cliquetable, SCIP_BRANCHCAND *branchcand, SCIP_EVENTFILTER *eventfilter, SCIP_EVENTQUEUE *eventqueue, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
Definition: var.c:5275
datastructures for implications, variable bounds, and cliques
public data structures and miscellaneous methods
SCIP_Bool SCIPcliquetableNeedsComponentUpdate(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3542
Definition: type_var.h:46
int * SCIPimplicsGetIds(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3349
SCIP_RETCODE SCIPcliquetableComputeCliqueComponents(SCIP_CLIQUETABLE *cliquetable, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_VAR **vars, int nbinvars, int nintvars, int nimplvars)
Definition: implics.c:3119
int SCIPimplicsGetNImpls(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3310
Definition: type_set.h:40
SCIP_RETCODE SCIPvarAddCliqueToList(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: var.c:11392
Definition: struct_reopt.h:130
Definition: type_var.h:41
Definition: type_var.h:45
SCIP_RETCODE SCIPvarFixBinary(SCIP_VAR *var, 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, SCIP_Bool value, SCIP_Bool *infeasible, int *nbdchgs)
Definition: var.c:11178
datastructures for problem statistics
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2548
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6620
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)
Definition: implics.c:2367
static SCIP_RETCODE vboundsCreate(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem)
Definition: implics.c:46
static void cliqueFree(SCIP_CLIQUE **clique, BMS_BLKMEM *blkmem)
Definition: implics.c:1029
static SCIP_RETCODE cliqueEnsureSize(SCIP_CLIQUE *clique, BMS_BLKMEM *blkmem, SCIP_SET *set, int num)
Definition: implics.c:1046
methods for sorting joint arrays of various types
static SCIP_RETCODE vboundsSearchPos(SCIP_VBOUNDS *vbounds, SCIP_VAR *var, SCIP_Bool negativecoef, int *insertpos, SCIP_Bool *found)
Definition: implics.c:116
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)
Definition: implics.c:1873
static SCIP_RETCODE vboundsEnsureSize(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem, SCIP_SET *set, int num)
Definition: implics.c:82
Definition: struct_lp.h:259
Definition: type_lp.h:48
public methods for message output
Definition: struct_implics.h:88
void SCIPcliquelistCheck(SCIP_CLIQUELIST *cliquelist, SCIP_VAR *var)
Definition: implics.c:3452
SCIP_RETCODE SCIPvarsGetProbvarBinary(SCIP_VAR ***vars, SCIP_Bool **negatedarr, int nvars)
Definition: var.c:12277
Definition: struct_implics.h:66
SCIP_RETCODE SCIPdisjointsetCreate(SCIP_DISJOINTSET **djset, BMS_BLKMEM *blkmem, int ncomponents)
Definition: misc.c:11108
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6664
static SCIP_RETCODE cliquelistEnsureSize(SCIP_CLIQUELIST *cliquelist, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_Bool value, int num)
Definition: implics.c:1449
Definition: struct_misc.h:268
SCIP_Bool SCIPvarIsMarkedDeleteGlobalStructures(SCIP_VAR *var)
Definition: var.c:17518
Definition: struct_stat.h:50
Definition: struct_tree.h:175
Definition: struct_implics.h:53
Definition: struct_event.h:214
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
SCIP_Real * SCIPimplicsGetBounds(SCIP_IMPLICS *implics, SCIP_Bool varfixing)
Definition: implics.c:3337
Definition: type_var.h:43
Definition: struct_branch.h:37
static SCIP_RETCODE implicsCreate(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem)
Definition: implics.c:416
void SCIPvboundsFree(SCIP_VBOUNDS **vbounds, BMS_BLKMEM *blkmem)
Definition: implics.c:64
SCIP_RETCODE SCIPvarsAddClique(SCIP_VAR **vars, SCIP_Bool *values, int nvars, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_CLIQUE *clique)
Definition: var.c:11354
datastructures for global SCIP settings
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:451
SCIP_CLIQUE ** SCIPcliquetableGetCliques(SCIP_CLIQUETABLE *cliquetable)
Definition: implics.c:3514
void SCIPimplicsFree(SCIP_IMPLICS **implics, BMS_BLKMEM *blkmem)
Definition: implics.c:442
SCIP_RETCODE SCIPcliquelistDel(SCIP_CLIQUELIST **cliquelist, BMS_BLKMEM *blkmem, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: implics.c:1518
SCIP_RETCODE SCIPvarDelCliqueFromList(SCIP_VAR *var, BMS_BLKMEM *blkmem, SCIP_Bool value, SCIP_CLIQUE *clique)
Definition: var.c:11414
Definition: type_var.h:58