presolve.c
Go to the documentation of this file.
22 /* all general presolving methods (not working on any specific kind of data(, e.g. consdata) should be implemented here */
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44 /** collect variable bound information for a variable set reduction and global implication; only variable which have the
58 SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
161 /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
162 if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
184 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound
215 else if( SCIPisFeasLT(scip, implcoefs[w] * SCIPvarGetUbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
221 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound so
227 SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", newub, bounds[issetvar[idx] - 1] );
276 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound
307 else if( SCIPisFeasLT(scip, implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
313 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound so
319 SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", newlb, bounds[issetvar[idx] - 1] );
398 /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
399 if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
449 else if( SCIPisFeasGT(scip, implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
458 SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", newlb, bounds[issetvar[idx] - 1]);
537 else if( SCIPisFeasGT(scip, implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
546 SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", newub, bounds[issetvar[idx] - 1]);
582 /** collect non-binary implication data for variable set reduction and global bound implications; only variable which
583 * have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are saved as variable bounds
597 SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
605 int* ncountnonzeros, /**< pointer to store the number of non-zero entries in the counts array */
672 /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
673 if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
684 /* set variable 'var' with bound implies other set variable 'implvars[w]' with a non-worse bound than the
697 /* ignore implications that are redundant with respect to the current global bounds (see #2888) */
707 /* the implied upper bound on a binary variable should not be trivial, otherwise we might globally fix
754 /* set variable 'var' with bound implies other set variable 'implvars[w]' with a non-worse bound than the
767 /* ignore implications that are redundant with respect to the current global bounds (see #2888) */
777 /* the implied lower bound on a binary variable should not be trivial, otherwise we might globally fix
780 * @note is is possible that the implied bound is greater than one, when the implied variable has
822 /** collect clique data on binary variables for variable set reduction and global bound implications */
834 SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
842 int* ncountnonzeros, /**< pointer to store the number of non-zero entries in the counts array */
850 int* foundbin, /**< pointer to store the lowest index of a binary implication variable when found */
913 if( clqvars[w] == var || SCIPvarGetLbGlobal(clqvars[w]) > 0.5 || SCIPvarGetUbGlobal(clqvars[w]) < 0.5 )
924 /* set variable 'var' with bound implies other set variable 'clqvars[w]' with corresponding set bound so we can
965 /** try to reduce the necessary variable in a set of variables with corresponding bounds and boundtypes for which one
974 * by (global) implication data (cliques, implications, and variable bounds) we have also the following implications
981 * Because of the last implication x4 is redundant, because x1 >= 1 would also be fulfilled in the variable set, so we
983 * Also, the both other implications and x3 >= 1 (in the given variable set) all imply exactly x3 >= 1, so we tighten
991 SCIP_Bool* boundtypes, /**< boundtypes array (TRUE == SCIP_BOUNDTYPE_UPPER, FALSE == SCIP_BOUNDTYPE_LOWER)
993 SCIP_Bool* redundants, /**< array which be filled and then indicate if a variable in the set is redundant */
998 SCIP_Bool* setredundant, /**< pointer to store if we found a global reduction on a variable which was part
1001 SCIP_Bool fullshortening /**< do we want to try the shortening procedure over the whole set (which might be expensive) */
1004 SCIP_Real* newbounds; /* array saving all overall implied global bounds, first nprobvars for lower bound, second
1007 SCIP_Real* lastbounds;/* temporary array to remember last implied bounds before taken the current variable into
1013 int* issetvar; /* array for mapping from a problem variable to the position in the variable set (,pos + 1 in
1017 int* counts; /* array saving number of implication by set variables, first nprobvars for lower bound, second
1020 int* implidx; /* temporary array to remember all indices of implied variables by the current set variable
1088 /* check if implied binary variables exist, because for these variables the implications can be stored in the
1126 collectBinaryCliqueData(var, varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts, countnonzeros,
1131 /* only variable which have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are
1134 * we only check binary to non-binary implications if we can detect further implications which either lead to
1137 if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1139 collectNonBinaryImplicationData(scip, var, varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts,
1140 countnonzeros, &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1144 * we only check the variable bounds if we can detect further implications which either lead to global reductions
1147 else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1149 collectNonBinaryVBoundData(scip, var, varidx, v, *nredvars, bounds, boundtypes, newbounds, counts, countnonzeros,
1150 &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1153 /* reduce implication counters on all variables which are implied by a variable now marked as redundant */
1159 SCIPdebugMsg(scip, "marked variable <%s> as redundant variable in variable set\n", SCIPvarGetName(var));
1164 /* correct implication counters and bounds, if the redundant variable implies other variables we need to reduce
1187 /* check if we want to shorten the whole set of variables, or terminate early if we did not find any further
1248 SCIPdebugMsg(scip, "mark redundant variable <%s> to be removed from variable set\n", SCIPvarGetName(var));
1265 SCIPdebugMsg(scip, "variable set led to global reductions (in %s)\n", SCIPprobGetName(scip->transprob));
1304 SCIPdebugMsg(scip, "can tighten lower bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar),
1307 /* the new lower bound is greater than the global upper bound => the problem is global infeasible */
1340 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue,
1355 SCIPdebugMsg(scip, "can tighten upper bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar),
1358 /* the new upper bound is small than the global upper bound => the problem is global infeasible */
1371 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue,
static void collectNonBinaryVBoundData(SCIP *scip, SCIP_VAR *var, int varidx, int pos, int nredvars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *countnonzeros, int *ncountnonzeros, int *issetvar, int nvars, int *foundbin, int *foundnonbin, int *implidx, int *nimplidx, SCIP_Real *lastbounds)
Definition: presolve.c:48
internal methods for branch and bound tree
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7513
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
Definition: struct_scip.h:59
public methods for memory management
SCIP_RETCODE SCIPshrinkDisjunctiveVarSet(SCIP *scip, SCIP_VAR **vars, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Bool *redundants, int nvars, int *nredvars, int *nglobalred, SCIP_Bool *setredundant, SCIP_Bool *glbinfeas, SCIP_Bool fullshortening)
Definition: presolve.c:986
public methods for implications, variable bounds, and cliques
Definition: struct_var.h:198
SCIP_EXPORT SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17957
Definition: type_var.h:53
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:799
public methods for problem variables
SCIP_EXPORT SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17986
public methods for numerical tolerances
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
public methods for the branch-and-bound tree
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:129
internal methods for storing and manipulating the main problem
SCIP_EXPORT int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17940
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
Definition: type_lp.h:47
Definition: type_retcode.h:33
SCIP main data structure.
methods commonly used for presolving
datastructures for block memory pools and memory buffers
SCIP_EXPORT SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18025
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:812
SCIP_RETCODE SCIPnodeAddBoundchg(SCIP_NODE *node, 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_VAR *var, SCIP_Real newbound, SCIP_BOUNDTYPE boundtype, SCIP_Bool probingchange)
Definition: tree.c:2075
Definition: type_lp.h:48
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:786
public methods for message output
SCIP_EXPORT SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:17886
Definition: struct_implics.h:66
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:451
public methods for message handling
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:477
SCIP_EXPORT SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:17972
static void collectNonBinaryImplicationData(SCIP *scip, SCIP_VAR *var, int varidx, int pos, int nredvars, SCIP_Bool value, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *countnonzeros, int *ncountnonzeros, int *issetvar, int nvars, int *foundbin, int *foundnonbin, int *implidx, int *nimplidx, SCIP_Real *lastbounds)
Definition: presolve.c:586
SCIP_EXPORT int SCIPvarGetNCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18014
Definition: objbenders.h:33
static void collectBinaryCliqueData(SCIP_VAR *var, int varidx, int pos, int nredvars, SCIP_Bool value, SCIP_Real *bounds, SCIP_Bool *boundtypes, SCIP_Real *newbounds, int *counts, int *countnonzeros, int *ncountnonzeros, int *issetvar, int nvars, int *foundbin, int *implidx, int *nimplidx)
Definition: presolve.c:824
SCIP_EXPORT SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:17928
memory allocation routines