cons_logicor.c
Go to the documentation of this file.
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
62 #define CONSHDLR_ENFOPRIORITY -2000000 /**< priority of the constraint handler for constraint enforcing */
63 #define CONSHDLR_CHECKPRIORITY -2000000 /**< priority of the constraint handler for checking feasibility */
64 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
65 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
66 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
68 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
69 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
70 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
71 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
76 #define LINCONSUPGD_PRIORITY +800000 /**< priority of the constraint handler for upgrading of linear constraints */
85 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
86 #define DEFAULT_STRENGTHEN TRUE /**< should pairwise constraint comparison try to strengthen constraints by removing superflous non-zeros? */
89 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
91 #define DEFAULT_NEGATEDCLIQUE TRUE /**< should negated clique information be used in presolving */
92 #define DEFAULT_IMPLICATIONS TRUE /**< should we try to shrink the variables and derive global boundchanges by
103 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
113 SCIP_CONSHDLR* conshdlrlinear; /**< pointer to linear constraint handler or NULL if not included */
114 SCIP_CONSHDLR* conshdlrsetppc; /**< pointer to setppc constraint handler or NULL if not included */
115 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
116 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in
120 SCIP_Bool useimplications; /**< should we try to shrink the variables and derive global boundchanges
122 SCIP_Bool usestrengthening; /**< should pairwise constraint comparison try to strengthen constraints by
130 /* @todo it might speed up exit-presolve to remember all positions for variables when catching the varfixed event, or we
131 * change catching and dropping the events like it is done in cons_setppc, which probably makes the code more
148 unsigned int presolved:1; /**< flag indicates if we have some fixed, aggregated or multi-aggregated
151 unsigned int impladded:1; /**< was the 2-variable logic or constraint already added as implication? */
153 unsigned int changed:1; /**< was constraint changed since last redundancy round in preprocessing? */
297 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
304 (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
479 if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR )
493 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_INITPRESOLVE )
547 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_INITPRESOLVE )
593 /** in case a part (more than one variable) in the logic or constraint is independent of every else, we can perform dual
595 * - fix the variable with the smallest object coefficient to one if the constraint is not modifiable and all
600 * also added the special case were exactly one variable is locked by this constraint and another variable without any
604 * Note: the following dual reduction for logic or constraints is already performed by the presolver "dualfix"
605 * - if a variable in a set covering constraint is only locked by that constraint and has negative or zero
616 SCIP_RESULT* result /**< pointer to store the result SCIP_SUCCESS, if presolving was performed */
644 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
645 * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are
658 /* we don't want to consider small constraints (note that the constraints can be modifiable, so we can't delete this
672 /* check if we can apply the dual reduction; therefore count the number of variables where the logic or has the only
680 /* variables with varstatus not equal to SCIP_VARSTATUS_FIXED can also have fixed bounds, but were not removed yet */
710 /* remember best variable with no uplocks, this variable dominates all other with exactly one downlock */
724 /* in case an other constraints has also locks on that variable we cannot perform a dual reduction on these
804 /* in case an other constraints has also locks on that variable we cannot perform a dual reduction on these
839 /* if all variable have our appreciated number of locks and the constraint is not modifiable, or if the bestobjval is
840 * less than or equal to zero, we can fix the variable with the smallest objective coefficient to one and the
860 /** deletes all zero-fixed variables, checks for variables fixed to one, replace all variables which are not active or
934 /* renew all variables, important that we do a backwards loop because deletion only affect rear items */
940 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED && SCIPvarGetStatus(SCIPvarGetNegatedVar(var)) == SCIP_VARSTATUS_MULTAGGR) )
957 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, nconsvars, &constant, &requiredsize, TRUE) );
964 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
997 assert(SCIPvarIsActive(consvars[v2]) || (SCIPvarGetStatus(consvars[v2]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(consvars[v2]))));
1013 /* it might happen that there are more than one multi-aggregated variable, so we need to get the whole probvar sum over all variables */
1017 /* memory needed is at least old number of variables - 1 + number of variables in first multi-aggregation */
1033 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, size, &constant, &requiredsize, TRUE) );
1035 /* if space was not enough(we found another multi-aggregation), we need to resize the buffers */
1041 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1084 SCIPwarningMessage(scip, "logicor constraint <%s> has a multi-aggregated variable, which was not resolved and therefore could lead to aborts\n", SCIPconsGetName(cons));
1133 /** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */
1144 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
1150 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1173 /* in case the logic or constraint is satisfied in the depth where it is also valid, we can delete it */
1180 SCIPdebugMsg(scip, "disabling constraint cons <%s> at depth %d\n", SCIPconsGetName(cons), SCIPgetDepth(scip));
1188 /** find sets of equal variables in constraint: multiple entries of variable can be replaced by single entry */
1194 unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
1245 /* all variables should be active or negative active variables, otherwise something went wrong with applyFixings()
1259 /* all variables should be active or negative active variables, otherwise something went wrong with applyFixings()
1263 (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
1270 /* check variable type, either pure binary or an integer/implicit integer variable with 0/1 bounds */
1273 ((pos >= nbinvars && pos < nbinvars + nintvars && SCIPvarGetType(var) == SCIP_VARTYPE_INTEGER) ||
1281 /* check all vars for multiple entries, do necessary backwards loop because deletion only affect rear items */
1297 SCIPdebugMsg(scip, "logicor constraint <%s> redundant: variable <%s> and its negation are present\n",
1314 SCIPdebugMsg(scip, "logicor constraint <%s> redundant: variable <%s> and its negation are present\n",
1337 /** checks constraint for violation only looking at the watched variables, applies fixings if possible */
1346 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
1372 SCIPdebugMsg(scip, "processing watched variables of constraint <%s>\n", SCIPconsGetName(cons));
1382 SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar1 fixed to 1.0)\n", SCIPconsGetName(cons));
1389 SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar2 fixed to 1.0)\n", SCIPconsGetName(cons));
1486 * - a modifiable constraint must be added as a cut and further pricing must be performed in the LP solving loop
1509 * - an unmodifiable constraint is feasible and can be disabled after the remaining variable is fixed to one
1520 /* fixed remaining variable to one and disable constraint; make sure, the fixed-to-one variable is watched */
1536 SCIPdebugMsg(scip, " -> new watched variables <%s> and <%s> of constraint <%s> are still unfixed\n",
1611 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, cons, SCIPconsGetName(cons), 1.0, SCIPinfinity(scip),
1614 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row, consdata->nvars, consdata->vars, 1.0) );
1630 /* skip deactivated, redundant, or local constraints (the NLP does not allow for local rows at the moment) */
1647 0.0, consdata->nvars, consdata->vars, coefs, NULL, 1.0, SCIPinfinity(scip), SCIP_EXPRCURV_LINEAR) );
1722 SCIP_CALL( processWatchedVars(scip, cons, eventhdlr, cutoff, reduceddom, &addcut, &mustcheck) );
1798 SCIP_CALL( processWatchedVars(scip, cons, eventhdlr, cutoff, reduceddom, &addcut, &mustcheck) );
1831 )
1872 found = SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var1, consdata->nvars, &pos);
1883 found = SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var2, consdata->nvars, &pos);
1916 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
1984 /** compares each constraint with all other constraints for a possible duplication and removes duplicates using a hash
2048 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
2117 signature |= ((unsigned int)1 << ((unsigned int)SCIPvarGetIndex(vars[v]) % (sizeof(unsigned int) * 8)));
2123 /** compute the constraint signature which is used to detect constraints, that contain potentially the same set of
2129 )
2144 int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2205 int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2232 /* it might be that a variable is not yet put into the occurlist, then this constraint cannot cover another */
2253 /** run a pairwise comparison for detecting subset-constraints of other constraint while using a signature */
2260 int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2293 findShortestOccurlist(vars, consdata->nvars, varstopos, occurlist, noccurlistentries, occurlistlength, &nentries, &shortestlist);
2397 int* noccurlistentries, /**< arrray with number of constraints for each variable in the occurlist */
2430 assert(SCIPvarIsActive(var) || (SCIPvarGetNegatedVar(var) != NULL && SCIPvarIsActive(SCIPvarGetNegatedVar(var))));
2446 SCIP_CALL( SCIPallocBufferArray(scip, &(occurlist[pos]), occurlistsizes[pos]) ); /*lint !e866*/
2474 SCIP_CALL( SCIPreallocBufferArray(scip, &(occurlist[pos]), occurlistsizes[pos]) ); /*lint !e866*/
2487 /** run a pairwise comparison for the given variables against all constraits to detect redundant non-zeros in these
2549 findShortestOccurlist(vars, nvars, varstopos, occurlist, noccurlistentries, occurlistlength, &nentries, &shortestlist);
2643 /* cons1 is might be covered by the changed constraints cons, meaning that we might remove the artvar from
2650 /* if the artificial variable was not yet found, search over the rear variables in constraint cons1 */
2673 SCIPdebugMsg(scip, "variable %s in logicor constraint <%s> is redundant and will be removed (used constraint %s)\n",
2704 SCIPdebugMsg(scip, "logicor constraint <%s> is redundant due to constraint <%s> after removing variable <%s>\n",
2801 /* @todo: improve this algorithm by using the information that a constraint variables does not appaer in any
2802 * other constraint, which means that only this variable needs to be negated to check for redundant
2806 SCIP_CALL( removeRedundantNonZeros(scip, cons, artvar, v, varstopos, occurlist, noccurlistentries,
2831 unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
2863 /* remove all variables that are fixed to zero, check redundancy due to fixed-to-one variable */
2920 * @see "Effective Preprocessing in SAT through Variable and Clause Elimination" by Niklas En and Armin Biere
2927 unsigned char** entries, /**< array to store whether two positions in constraints represent the same
2931 SCIP_Bool usestrengthening, /**< should we try to strengthen constraints by removing superflous
2972 SCIPdebugMsg(scip, "starting removeRedundantConssAndNonzeros(), pairwise comparison to detect covered logicor constraints\n");
2996 SCIP_CALL( prepareCons(scip, cons, eventhdlr, entries, nentries, &redundant, nfixedvars, nchgcoefs, ndelconss, cutoff) );
3030 /* we can stop if strengthening is disabled and all constraints have the same amount of variables */
3031 if( !usestrengthening && SCIPconsGetData(myconss[0])->nvars == SCIPconsGetData(myconss[nmyconss - 1])->nvars )
3038 /* @note: in the following we have at least number of nonzeros in logicor constraints + three times two the number of
3039 * binary variables memory consumption + a map for variables to positions, we need this to get a column base
3070 /* determine all constraints with the maximal number of variables and add them to the column representation */
3080 SCIP_CALL( addConsToOccurList(scip, cons, varstopos, occurlist, noccurlistentries, occurlistsizes, &occurlistlength, occurlistsize) );
3117 SCIP_CALL( removeRedundantConss(scip, cons, varstopos, occurlist, noccurlistentries, occurlistlength, ndelconss) );
3125 SCIP_CALL( addConsToOccurList(scip, cons, varstopos, occurlist, noccurlistentries, occurlistsizes, &occurlistlength, occurlistsize) );
3145 SCIP_CALL( strengthenConss(scip, myconss, nmyconss, varstopos, occurlist, noccurlistentries, occurlistlength, eventhdlr, ndelconss, nchgcoefs) );
3166 /** try to tighten constraints by reducing the number of variables in the constraints using implications and cliques,
3176 unsigned char** entries, /**< array to store whether two positions in constraints represent the same
3240 /* prepare constraint by removing fixings and merge it; we invalidate the presolved flag, because the calls to
3241 * SCIPcleanupCliques() in this loop may have lead to fixed variables that are not yet removed */
3243 SCIP_CALL( prepareCons(scip, cons, eventhdlr, entries, nentries, &redundant, nfixedvars, nchgcoefs, ndelconss, cutoff) );
3265 assert(SCIPvarIsActive(var) || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(var))));
3286 /* use implications and cliques to derive global fixings and to shrink the number of variables in this constraints */
3287 SCIP_CALL( SCIPshrinkDisjunctiveVarSet(scip, probvars, bounds, boundtypes, redundants, consdata->nvars, &nredvars,
3343 /* invalidate the presolved flags, because the calls to SCIPcleanupCliques() may have lead to fixed variables that
3370 /** try to find a negated clique in a constraint which makes this constraint redundant but we need to keep the negated
3381 unsigned char** entries, /**< array to store whether two positions in constraints represent the same
3422 if( SCIPgetNCliques(scip) == conshdlrdata->nlastcliquesneg && SCIPgetNImplications(scip) == conshdlrdata->nlastimplsneg )
3451 SCIP_CALL( prepareCons(scip, cons, eventhdlr, entries, nentries, &redundant, nfixedvars, nchgcoefs, ndelconss, cutoff) );
3479 /* all variables should be active or negative active variables, otherwise something went wrong with applyFixings()
3484 assert(SCIPvarIsActive(repvars[v]) || (SCIPvarGetStatus(repvars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(repvars[v]))));
3551 SCIPdebugMsg(scip, "logicor constraint <%s> is redundant, because variable <%s> and its negation <%s> exist\n",
3563 SCIPdebugMsg(scip, "in logicor constraint <%s>, active variable of <%s> and active variable of <%s> are the same, removing the first\n",
3570 /* delCoefPos replaces the variable on position v with the last one, so w also need to correct the
3571 * negated array the same way, and because of deletion the number of variables is already decreased
3586 /* this negated clique information could be created out of this logicor constraint even if there are more
3587 * than two variables left (, for example by probing), we need to keep this information by creating a
3613 SCIPdebugMsg(scip, "logicor constraint <%s> is redundant due to negated clique information and will be replaced by a setppc constraint \n",
3615 SCIPdebugMsg(scip, "variable <%s> and variable <%s> are in a negated clique\n", SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(consdata->vars[w]));
3645 * in case a constraint has two variables left, we will add the implication and upgrade it to a set-packing constraint
3686 /* if an unmodifiable logicor constraint has only two variables, we can add an implication and we will upgrade this
3700 /* a two-variable logicor constraint x + y >= 1 yields the implication x == 0 -> y == 1, and is represented
3703 SCIP_CALL( SCIPaddClique(scip, consdata->vars, values, consdata->nvars, FALSE, &implinfeasible, &nimplbdchgs) );
3711 /* adding the above implication could lead to fixings, which render the constraint redundant */
3716 /* remove all variables that are fixed to zero, check redundancy due to fixed-to-one variable */
3754 SCIPdebugMsg(scip, "logicor constraint <%s> was upgraded to a set-packing constraint\n", SCIPconsGetName(cons));
3762 * if unmodifiable constraint has only one variable, this one can be fixed and the constraint deleted
3802 SCIPdebugMsg(scip, " -> variable is multi-aggregated, upgrade to linear constraint <%s> == 1 \n",
3806 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "fixmaggr_%s_%s", SCIPconsGetName(cons),SCIPvarGetName(consdata->vars[0]) );
3807 SCIP_CALL( SCIPcreateConsLinear(scip, &conslinear, consname, 1, consdata->vars, &coef, 1.0, 1.0,
3859 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3861 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3890 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3911 * - logic or constraints have left hand side of +1.0, and right hand side of +infinity: x(S) >= 1.0
3914 if( nvars > 2 && nposbin + nnegbin + nposimplbin + nnegimplbin == nvars && ncoeffspone + ncoeffsnone == nvars
3920 SCIPdebugMsg(scip, "upgrading constraint <%s> to logic or constraint\n", SCIPconsGetName(cons));
3922 /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
3925 /* create the logic or constraint (an automatically upgraded constraint is always unmodifiable) */
3927 SCIP_CALL( createNormalizedLogicor(scip, upgdcons, SCIPconsGetName(cons), nvars, vars, vals, mult,
3960 SCIPdebugMsg(scip, "Enforcing %d logic or constraints for %s solution\n", nconss, sol == NULL ? "LP" : "relaxation");
3974 SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
3980 SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
4015 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
4037 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
4063 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4070 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
4092 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4101 SCIP_CALL( applyFixings(scip, conss[c], conshdlrdata->eventhdlr, &redundant, &nchgcoefs, NULL, NULL) );
4103 /* it may happen that a constraint still contains variables that are fixed to one; for example, this happens
4104 * when variable fixings have been detected in the last presolving round by some other plugins (see #2941)
4108 SCIPdebugMsg(scip, "logic or constraint <%s> is redundant (detected during EXITPRE)\n", SCIPconsGetName(conss[c]));
4116 /* we set the presolved flag to FALSE since not all fixing are removed if redundancy is detected */
4144 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4181 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_INITPRESOLVE )
4191 SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4227 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4230 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4236 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4281 SCIP_CALL( separateCons(scip, conss[c], NULL, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
4328 SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &separated, &reduceddom) );
4399 SCIP_CALL( enforcePseudo(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &infeasible, &reduceddom, &solvelp) );
4497 SCIP_CALL( processWatchedVars(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &reduceddom, &addcut, &mustcheck) );
4570 /* remove all variables that are fixed to zero, check redundancy due to fixed-to-one variable */
4571 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, &redundant, nchgcoefs, naddconss, ndelconss) );
4578 /* find sets of equal variables in constraint: multiple entries of variable can be replaced by single entry */
4581 SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, &redundant, nchgcoefs) );
4599 SCIP_CALL( fixDeleteOrUpgradeCons(scip, cons, conshdlrdata->eventhdlr, conshdlrdata->conshdlrlinear,
4600 conshdlrdata->conshdlrsetppc, nfixedvars, nchgbds, nchgcoefs, ndelconss, naddconss, nupgdconss, &cutoff) );
4619 SCIP_CALL( dualPresolving(scip, cons, conshdlrdata->eventhdlr, nfixedvars, ndelconss, nchgcoefs, result) );
4625 /* in dualpresolving we may have removed variables, so we need to take care of special cases */
4631 SCIP_CALL( fixDeleteOrUpgradeCons(scip, cons, conshdlrdata->eventhdlr, conshdlrdata->conshdlrlinear,
4632 conshdlrdata->conshdlrsetppc, nfixedvars, nchgbds, nchgcoefs, ndelconss, naddconss, nupgdconss, &cutoff) );
4660 /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
4661 SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, ndelconss) );
4672 SCIP_CALL( removeRedundantConssAndNonzeros(scip, conss, nconss, &entries, &nentries, conshdlrdata->eventhdlr,
4684 /* try to tighten constraints by reducing the number of variables in the constraints using implications and
4744 /* the only deductions are variables infered to 1.0 on logic or constraints where all other variables
4747 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5); /* the inference variable must be assigned to one */
4814 SCIPdebugMsg(scip, "activating information for logic or constraint <%s>\n", SCIPconsGetName(cons));
4821 SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4827 SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4858 SCIPdebugMsg(scip, "deactivating information for logic or constraint <%s>\n", SCIPconsGetName(cons));
4866 SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4875 SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED, conshdlrdata->eventhdlr, (SCIP_EVENTDATA*)cons,
4926 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
4972 /* copy string for parsing; note that isspace() in SCIPparseVarsList() requires that strcopy ends with '\0' */
4982 SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4994 SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
5002 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5019 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5049 /** constraint method of constraint handler which returns the number of variables (if possible) */
5080 SCIPdebugMsg(scip, "enabling constraint cons <%s> at depth %d\n", SCIPconsGetName((SCIP_CONS*)eventdata), SCIPgetDepth(scip));
5148 /* if the conflict consists of only two (binary) variables, it will be handled by the setppc conflict handler */
5180 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cf%d_%" SCIP_LONGINT_FORMAT, SCIPgetNRuns(scip), SCIPgetNConflictConssApplied(scip));
5204 )
5216 SCIP_CALL( SCIPincludeConflicthdlrBasic(scip, &conflicthdlr, CONFLICTHDLR_NAME, CONFLICTHDLR_DESC, CONFLICTHDLR_PRIORITY,
5243 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolLogicor,CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
5245 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropLogicor, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
5248 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpLogicor, consSepasolLogicor, CONSHDLR_SEPAFREQ,
5258 /* include the linear constraint to logicor constraint upgrade in the linear constraint handler */
5259 SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdLogicor, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) );
5285 "should pairwise constraint comparison try to strengthen constraints by removing superflous non-zeros?",
5294 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5320 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5322 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5344 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5357 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
5366 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
5367 * method SCIPcreateConsLogicor(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
5371 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5510 /** returns the linear relaxation of the given logic or constraint; may return NULL if no LP row was yet created;
5561 nconss = onlychecked ? SCIPconshdlrGetNCheckConss(conshdlr) : SCIPconshdlrGetNActiveConss(conshdlr);
5584 SCIP_CALL( mergeMultiples(scip, cons, eventhdlr, &entries, &nentries, &redundant, nchgcoefs) );
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition: scip_lp.c:1758
SCIP_RETCODE SCIPaddCoefLogicor(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_logicor.c:5392
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4205
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1413
SCIP_RETCODE SCIPaddConsAge(SCIP *scip, SCIP_CONS *cons, SCIP_Real deltaage)
Definition: scip_cons.c:1692
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:563
Definition: type_result.h:33
Definition: type_result.h:37
static SCIP_RETCODE removeRedundantCons(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1, int *ndelconss)
Definition: cons_logicor.c:2079
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11474
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2125
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:773
public methods for SCIP parameter handling
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3289
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:586
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:786
Definition: struct_scip.h:59
static SCIP_RETCODE enforcePseudo(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, SCIP_Bool *infeasible, SCIP_Bool *reduceddom, SCIP_Bool *solvelp)
Definition: cons_logicor.c:1775
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1989
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2487
public methods for memory management
Definition: type_conflict.h:50
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:816
SCIP_RETCODE SCIPcopyConsLinear(SCIP *scip, SCIP_CONS **cons, SCIP *sourcescip, const char *name, int nvars, SCIP_VAR **sourcevars, SCIP_Real *sourcecoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
Definition: cons_linear.c:18030
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5415
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:12309
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3347
public methods for conflict handler plugins and conflict analysis
static SCIP_DECL_CONSEXITPRE(consExitpreLogicor)
Definition: cons_logicor.c:4074
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:308
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1749
Definition: type_result.h:49
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1686
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
Definition: cons_logicor.c:325
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:547
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
static SCIP_DECL_CONFLICTEXEC(conflictExecLogicor)
Definition: cons_logicor.c:5134
Definition: type_set.h:37
SCIP_RETCODE SCIPdisableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1918
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:678
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
static SCIP_RETCODE removeConstraintsDueToNegCliques(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLR *conshdlrsetppc, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS **conss, int nconss, unsigned char **entries, int *nentries, int *nfixedvars, int *ndelconss, int *nupgdconss, int *nchgcoefs, SCIP_Bool *cutoff)
Definition: cons_logicor.c:3376
Definition: struct_var.h:198
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1436
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip_cons.c:1461
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:477
static SCIP_RETCODE disableCons(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:1168
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:862
static SCIP_DECL_CONSDEACTIVE(consDeactiveLogicor)
Definition: cons_logicor.c:4844
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:825
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_logicor.c:529
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4547
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:166
Definition: type_var.h:53
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
static unsigned int calcSignature(SCIP_VAR **vars, int nvars)
Definition: cons_logicor.c:2106
Definition: type_expr.h:53
static SCIP_DECL_CONSEXITSOL(consExitsolLogicor)
Definition: cons_logicor.c:4148
public methods for problem variables
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_conflict.c:314
SCIP_RETCODE SCIPenableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1888
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:220
Definition: type_result.h:40
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, int *firstchange, int *ndelconss)
Definition: cons_logicor.c:1990
SCIP_Longint SCIPvarGetNBranchingsCurrentRun(SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: var.c:15743
Constraint handler for the set partitioning / packing / covering constraints .
public methods for SCIP variables
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:609
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1477
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:793
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:934
static SCIP_DECL_HASHGETKEY(hashGetKeyLogicorcons)
Definition: cons_logicor.c:1912
static SCIP_RETCODE switchWatchedvars(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
Definition: cons_logicor.c:388
static SCIP_RETCODE addCut(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
Definition: cons_logicor.c:1665
static void consdataCalcSignature(SCIP_CONSDATA *consdata)
Definition: cons_logicor.c:2129
public methods for numerical tolerances
Definition: struct_conflict.h:40
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
public methods for querying solving statistics
Definition: struct_sol.h:64
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4256
static SCIP_RETCODE shortenConss(SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS **conss, int nconss, unsigned char **entries, int *nentries, int *nfixedvars, int *ndelconss, int *nchgcoefs, SCIP_Bool *cutoff)
Definition: cons_logicor.c:3172
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip_conflict.c:292
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:1137
public methods for the branch-and-bound tree
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
SCIP_Real SCIPgetDualsolLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5461
SCIP_RETCODE SCIPaddClique(SCIP *scip, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6918
static void removeConsFromOccurList(SCIP_CONS *cons, SCIP_HASHMAP *varstopos, SCIP_CONS ***occurlist, int *noccurlistentries, int occurlistlength)
Definition: cons_logicor.c:2142
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:429
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
static SCIP_DECL_HASHKEYVAL(hashKeyValLogicorcons)
Definition: cons_logicor.c:1966
Definition: struct_misc.h:128
public methods for managing constraints
SCIP_RETCODE SCIPparseVarsList(SCIP *scip, const char *str, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize, char **endptr, char delimiter, SCIP_Bool *success)
Definition: scip_var.c:601
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:332