presolve.c
Go to the documentation of this file.
31 /* all general presolving methods (not working on any specific kind of data(, e.g. consdata) should be implemented here */
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
53 /** collect variable bound information for a variable set reduction and global implication; only variable which have the
67 SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
170 /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
171 if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
193 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound
224 else if( SCIPisFeasLT(scip, implcoefs[w] * SCIPvarGetUbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
230 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound so
236 SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", newub, bounds[issetvar[idx] - 1] );
285 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound
316 else if( SCIPisFeasLT(scip, implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
322 /* set variable 'var' with bound implies other set variable 'implvars[w]' with corresponding bound so
328 SCIPvarGetName(var), ">=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", newlb, bounds[issetvar[idx] - 1] );
407 /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
408 if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
458 else if( SCIPisFeasGT(scip, implcoefs[w]*SCIPvarGetLbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
467 SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), ">=", newlb, bounds[issetvar[idx] - 1]);
546 else if( SCIPisFeasGT(scip, implcoefs[w]*SCIPvarGetUbGlobal(implvars[w]) + implconsts[w], bounds[pos]) )
555 SCIPvarGetName(var), "<=", bounds[pos], SCIPvarGetName(implvars[w]), "<=", newub, bounds[issetvar[idx] - 1]);
591 /** collect non-binary implication data for variable set reduction and global bound implications; only variable which
592 * have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are saved as variable bounds
606 SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
614 int* ncountnonzeros, /**< pointer to store the number of non-zero entries in the counts array */
681 /* @todo if implvars[x] is aggregated, we could transform the variable into the active representation */
682 if( idx < 0 || SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(implvars[w]), SCIPvarGetUbGlobal(implvars[w])) )
693 /* set variable 'var' with bound implies other set variable 'implvars[w]' with a non-worse bound than the
706 /* ignore implications that are redundant with respect to the current global bounds (see #2888) */
716 /* the implied upper bound on a binary variable should not be trivial, otherwise we might globally fix
763 /* set variable 'var' with bound implies other set variable 'implvars[w]' with a non-worse bound than the
776 /* ignore implications that are redundant with respect to the current global bounds (see #2888) */
786 /* the implied lower bound on a binary variable should not be trivial, otherwise we might globally fix
789 * @note is is possible that the implied bound is greater than one, when the implied variable has
831 /** collect clique data on binary variables for variable set reduction and global bound implications */
843 SCIP_Real* newbounds, /**< array of implied bounds(, size is two times number of variables, first
851 int* ncountnonzeros, /**< pointer to store the number of non-zero entries in the counts array */
859 int* foundbin, /**< pointer to store the lowest index of a binary implication variable when found */
922 if( clqvars[w] == var || SCIPvarGetLbGlobal(clqvars[w]) > 0.5 || SCIPvarGetUbGlobal(clqvars[w]) < 0.5 )
933 /* set variable 'var' with bound implies other set variable 'clqvars[w]' with corresponding set bound so we can
974 /** try to reduce the necessary variable in a set of variables with corresponding bounds and boundtypes for which one
983 * by (global) implication data (cliques, implications, and variable bounds) we have also the following implications
990 * Because of the last implication x4 is redundant, because x1 >= 1 would also be fulfilled in the variable set, so we
992 * Also, the both other implications and x3 >= 1 (in the given variable set) all imply exactly x3 >= 1, so we tighten
1000 SCIP_Bool* boundtypes, /**< boundtypes array (TRUE == SCIP_BOUNDTYPE_UPPER, FALSE == SCIP_BOUNDTYPE_LOWER)
1002 SCIP_Bool* redundants, /**< array which be filled and then indicate if a variable in the set is redundant */
1007 SCIP_Bool* setredundant, /**< pointer to store if we found a global reduction on a variable which was part
1010 SCIP_Bool fullshortening /**< do we want to try the shortening procedure over the whole set (which might be expensive) */
1013 SCIP_Real* newbounds; /* array saving all overall implied global bounds, first nprobvars for lower bound, second
1016 SCIP_Real* lastbounds;/* temporary array to remember last implied bounds before taken the current variable into
1022 int* issetvar; /* array for mapping from a problem variable to the position in the variable set (,pos + 1 in
1026 int* counts; /* array saving number of implication by set variables, first nprobvars for lower bound, second
1029 int* implidx; /* temporary array to remember all indices of implied variables by the current set variable
1097 /* check if implied binary variables exist, because for these variables the implications can be stored in the
1135 collectBinaryCliqueData(var, varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts, countnonzeros,
1140 /* only variable which have the vartype SCIP_VARTYPE_BINARY have implications, otherwise the implications are
1143 * we only check binary to non-binary implications if we can detect further implications which either lead to
1146 if( SCIPvarGetType(var) == SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1148 collectNonBinaryImplicationData(scip, var, varidx, v, *nredvars, value, bounds, boundtypes, newbounds, counts,
1149 countnonzeros, &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1153 * we only check the variable bounds if we can detect further implications which either lead to global reductions
1156 else if( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY && ((usebin && implbinvarsexist) || usenonbin) )
1158 collectNonBinaryVBoundData(scip, var, varidx, v, *nredvars, bounds, boundtypes, newbounds, counts, countnonzeros,
1159 &ncountnonzeros, issetvar, nprobvars, &foundbin, &foundnonbin, implidx, &nimplidx, lastbounds);
1162 /* reduce implication counters on all variables which are implied by a variable now marked as redundant */
1168 SCIPdebugMsg(scip, "marked variable <%s> as redundant variable in variable set\n", SCIPvarGetName(var));
1173 /* correct implication counters and bounds, if the redundant variable implies other variables we need to reduce
1196 /* check if we want to shorten the whole set of variables, or terminate early if we did not find any further
1257 SCIPdebugMsg(scip, "mark redundant variable <%s> to be removed from variable set\n", SCIPvarGetName(var));
1274 SCIPdebugMsg(scip, "variable set led to global reductions (in %s)\n", SCIPprobGetName(scip->transprob));
1313 SCIPdebugMsg(scip, "can tighten lower bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar),
1316 /* the new lower bound is greater than the global upper bound => the problem is global infeasible */
1348 scip->transprob, scip->origprob, scip->tree, scip->reopt, scip->lp, scip->branchcand, scip->eventqueue,
1363 SCIPdebugMsg(scip, "can tighten upper bound variable %s [%g, %g] to %g\n", SCIPvarGetName(probvar),
1366 /* the new upper bound is small than the global upper bound => the problem is global infeasible */
1378 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:57
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:780
internal methods for branch and bound tree
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:793
Definition: struct_scip.h:68
public methods for memory management
public methods for implications, variable bounds, and cliques
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:497
SCIP_CLIQUE ** SCIPvarGetCliques(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18286
Definition: struct_var.h:207
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:832
Definition: type_var.h:62
public methods for problem variables
public methods for numerical tolerances
public methods for the branch-and-bound tree
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
internal methods for storing and manipulating the main problem
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
Definition: type_lp.h:56
Definition: type_retcode.h:42
SCIP main data structure.
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:819
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:806
methods commonly used for presolving
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18233
datastructures for block memory pools and memory buffers
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18247
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18218
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
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:2087
Definition: type_lp.h:57
public methods for message output
Definition: struct_implics.h:75
public methods for message handling
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:995
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:595
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:471
Definition: objbenders.h:43
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7532
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:833
memory allocation routines