cons_setppc.c
Go to the documentation of this file.
27 * @brief Constraint handler for the set partitioning / packing / covering constraints \f$1^T x\ \{=, \le, \ge\}\ 1\f$.
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
70 #define CONSHDLR_ENFOPRIORITY -700000 /**< priority of the constraint handler for constraint enforcing */
71 #define CONSHDLR_CHECKPRIORITY -700000 /**< priority of the constraint handler for checking feasibility */
72 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
73 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
74 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
76 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
77 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
78 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
79 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
84 #define LINCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of linear constraints */
85 #define NONLINCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of nonlinear constraints */
88 #define EVENTHDLR_DESC "bound change event handler for set partitioning / packing / covering constraints"
94 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
97 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
99 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
103 /*#define VARUSES*/ /* activate variable usage counting, that is necessary for LP and pseudo branching */
104 /*#define BRANCHLP*/ /* BRANCHLP is only useful if the ENFOPRIORITY is set to a positive value */
109 #define DEFAULT_NPSEUDOBRANCHES 2 /**< number of children created in pseudo branching (0: disable branching) */
112 #define DEFAULT_CLIQUELIFTING FALSE /**< should we try to lift variables into other clique constraints, fix
116 #define DEFAULT_ADDVARIABLESASCLIQUES FALSE/**< should we try to generate extra clique constraint out of all binary
119 #define DEFAULT_CLIQUESHRINKING TRUE /**< should we try to shrink the number of variables in a clique constraints, by
123 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
133 SCIP_CONSHDLR* conshdlrlinear; /**< pointer to linear constraint handler or NULL if not included */
138 int npseudobranches; /**< number of children created in pseudo branching (0 to disable branching) */
146 SCIP_Bool enablecliquelifting;/**< check whether we have enough changes to run the lifting procedure again */
150 SCIP_Bool addvariablesascliques;/**< should we try to generate extra clique constraint out of all binary
154 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
155 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
172 unsigned int cliqueadded:1; /**< was the set partitioning / packing constraint already added as clique? */
174 unsigned int changed:1; /**< was constraint changed since last redundancy round in preprocessing? */
177 unsigned int presolpropagated:1; /**< was the constraint already propagated in presolving w.r.t. the current domains? */
189 /** compares two active constraints of type set partitioning or set packing such that a "-1" is return if
191 * 2. both constraints are set partitioning constraints and the second has more! variables than the first or
192 * 3. both constraints are set packing constraints and the second has less! variables than the first
222 (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) || /*lint !e641*/
223 (consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars) ) /*lint !e641*/
225 else if( (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars) ) /*lint !e641*/
229 assert(consdata1->setppctype > consdata2->setppctype || (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == consdata2->setppctype && consdata1->nvars > consdata2->nvars) || (consdata1->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->setppctype == consdata2->setppctype && consdata1->nvars < consdata2->nvars)); /*lint !e641*/
234 /** sort constraints first after type (partitioning before packing before covering) and second after number of
235 * variables such that the partitioning constraints have increasing number of variables and the packing constraints
243 /** compares two setppc constraints such that a "-1" is return if the first constraint is active and
246 * 3. both constraints are set partitioning constraints and the second has more! variables than the first or
247 * 4. both constraints are set packing constraints and the second has less! variables than the first
281 assert(SCIP_SETPPCTYPE_PARTITIONING < SCIP_SETPPCTYPE_PACKING && SCIP_SETPPCTYPE_PACKING < SCIP_SETPPCTYPE_COVERING); /*lint !e506*//*lint !e1564*/
285 (((SCIP_SETPPCTYPE)consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) ||
286 ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars))) )
288 else if( ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_COVERING || (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars)) )
292 assert(consdata1->setppctype > consdata2->setppctype || ((consdata1->setppctype == consdata2->setppctype) &&
294 || (consdata1->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars < consdata2->nvars)))); /*lint !e641*/
299 /** sort constraints first after type (partitioning before packing before covering) and second after number of
300 * variables such that the partitioning constraints have increasing number of variables and the packing constraints
373 /** creates constraint handler data for set partitioning / packing / covering constraint handler */
402 /** frees constraint handler data for set partitioning / packing / covering constraint handler */
442 /* if the variable is the negation of a problem variable, count the varuses in the problem variable */
570 SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
573 SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
593 /* @todo the setppc constraint handler does not remove fixed variables from its var array; removing those
594 * variables is only possible if we consider the values of nfixedones and nfixedzeros in all propagation methods
644 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
651 (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
687 SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
690 SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
700 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
709 SCIP_CONSDATA** consdata /**< pointer to store the set partitioning / packing / covering constraint */
852 SCIPdebugMsg(scip, " -> converting <%s> into setppc type %d\n", SCIPconsGetName(cons), setppctype);
929 * - SCIP_EVENTTYPE_BOUNDCHANGED: Is used to count the number of variable fixed locally to zero and one. That helps
934 * - SCIP_EVENTTYPE_VARFIXED: Is used to get informed if a variable of the constraint was aggregated which means was
949 /* during presolving, we may fix the last unfixed variable or do an aggregation if there are two unfixed variables */
950 if( SCIPconsIsActive(cons) && ((SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE) && (consdata->nfixedzeros >= consdata->nvars - 2)) )
1124 if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR )
1194 /* the last variable of the constraint was deleted; mark it for propagation (so that it can be deleted) */
1223 /** in case a part (more than one variable) in the setppc constraint is independent of every else (is locked only by
1235 * (ii) a variable x has exactly 0 uplocks and arbitrary downlocks and a variable y has exactly 1 downlock and
1247 * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 1 downlock and
1256 * - fix the variable with the smallest object coefficient to one if the object coefficient is negative or zero
1259 * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 0 downlocks and
1265 * Note: the following dual reduction for set covering and set packing constraints is already performed by the presolver
1268 * - if a variable in a set covering constraint is only locked by that constraint and has negative or zero
1271 * - if a variable in a set packing constraint is only locked by that constraint and has positive or zero
1274 * Note: all dual reduction (ii) could also be performed by the "domcol" presolver, but cause the pairwise comparison of
1275 * columns is only done heuristically (and here it should be even cheaper) we perform them here (too)
1284 SCIP_RESULT* result /**< pointer to store the result SCIP_SUCCESS, if presolving was performed */
1312 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
1313 * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are
1324 /* modifiable non-covering constraints cannot be deleted if one variable is fixed to one, because the propagation for
1336 /* we don't want to consider small constraints (note that the constraints can be modifiable, so we can't delete this
1370 /* check if we can apply the dual reduction; therefore count the number of variables where the setppc has the only
1404 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1436 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1466 /* if we got a set covering constraint and not all variables are locked from this constraint it might not get
1467 * redundant (which is case if it is not possible to fix at least one variable to one), we fix all redundant
1481 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1494 || (SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksDownType(activevar, SCIP_LOCKTYPE_MODEL)
1495 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksUpType(activevar, SCIP_LOCKTYPE_MODEL)));
1497 || (SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksUpType(activevar, SCIP_LOCKTYPE_MODEL)
1498 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksDownType(activevar, SCIP_LOCKTYPE_MODEL)));
1510 /* if variables has a negative objective contribution, and is uplocked by another constraint we cannot fix
1513 if( (fixval == 1.0 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) > nlockups) || objval < bestobjval )
1520 SCIPdebugMsg(scip, " -> dual-fixed dominated variable <%s> == %g\n", SCIPvarGetName(var), fixval);
1526 /* if all variables but the domination variable is fixed and the constraint is not modifiable or the constraint is a
1527 * covering constraint and the bestobjval is less than or equal to zero, we can fix the domination variable (with best
1530 if( ((*nfixedvars - noldfixed == nvars - 1) && !SCIPconsIsModifiable(cons)) || (setppctype == SCIP_SETPPCTYPE_COVERING && bestobjval <= 0.0) )
1532 /* in case of a set packing constraint with positive objective values, all variables can be fixed to zero; in all
1548 SCIPdebugMsg(scip, " -> dual-fixed best variable <%s> == %g\n", SCIPvarGetName(vars[idx]), fixval);
1588 {
1631 assert(SCIPvarIsActive(var1) || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_FIXED);
1641 assert(SCIPvarIsActive(var2) || SCIPvarGetStatus(var2) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var2) == SCIP_VARSTATUS_FIXED);
1710 SCIP_CALL( delCoefPos(scip, cons, v) ); /* only some changed behind position v-1, so it's okay */
1775 if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR || (SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_NEGATED && SCIPvarGetStatus(SCIPvarGetNegatedVar(repvar)) == SCIP_VARSTATUS_MULTAGGR) )
1792 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, nconsvars, &constant, &requiredsize, TRUE) );
1799 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1845 SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(consdata->vars[v2]));
1867 if( ndelconss != NULL && (nfixedvars != NULL || consdata->nvars == 1 || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING) )
1890 assert(SCIPvarIsActive(consvars[v2]) || (SCIPvarGetStatus(consvars[v2]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(consvars[v2]))));
1905 /* it might happen that there are more than one multi-aggregated variable, so we need to get the whole
1911 /* memory needed is at least old number of variables - 1 + number of variables in first multi-aggregation */
1927 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, size, &constant, &requiredsize, TRUE) );
1929 /* if space was not enough (we found another multi-aggregation), we need to resize the buffers */
1935 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1996 SCIPwarningMessage(scip, "setppc constraint <%s> has a multi-aggregated variable, which was not resolved and therefore could lead to aborts\n", SCIPconsGetName(cons));
2027 /** analyzes conflicting assignment on given constraint where all of the variables where assigned to zero,
2033 SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
2040 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
2048 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
2062 /** analyzes conflicting assignment on given constraint where two of the variables where assigned to one,
2068 SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
2076 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
2084 /* initialize conflict analysis, and add the two variables assigned to one to conflict candidate queue */
2104 /** checks constraint for violation only looking at the fixed variables, applies further fixings if possible */
2112 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
2114 {
2141 /*SCIPdebugMsg(scip, "processing constraint <%s> with respect to fixed variables (%d fixed to 0.0, %d fixed to 1.0)\n",
2170 SCIPdebugMsg(scip, " -> fixing all other variables to zero in set packing/partitioning constraint <%s>\n",
2174 * this could result in additional variables fixed to one due to aggregations; in this case, the
2185 assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
2204 /* the fixed to one variable must have been found, and at least one variable must have been fixed */
2215 SCIPdebugMsg(scip, " -> disabling set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2235 SCIPdebugMsg(scip, " -> conflict on set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2250 * - a set partitioning or covering constraint is infeasible, and if it's unmodifiable, the node
2266 SCIPdebugMsg(scip, " -> set covering/partitioning constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2285 * - an unmodifiable set partitioning or covering constraint is feasible and can be disabled after the
2314 assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
2317 SCIPdebugMsg(scip, " -> fixing remaining variable <%s> to one in set covering/partitioning constraint <%s>\n",
2344 SCIP_CONSDATA* consdata, /**< set partitioning / packing / covering constraint to be checked */
2362 sumbound = ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING ? 1.0 : 1.0 + 2*SCIPfeastol(scip));
2363 for( v = 0; v < nvars && sum < sumbound; ++v ) /* if sum >= sumbound, the feasibility is clearly decided */
2378 /* in case of partitioning, the violation is equal to the absolute difference between sum and 1 */
2442 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row, consdata->nvars, consdata->vars, 1.0) );
2491 /* skip deactivated, redundant, or local constraints (the NLP does not allow for local rows at the moment) */
2555 )
2582 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2641 {
2655 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2700 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
2823 /* @todo: maybe sort cliques and accordingly the variables so it will be faster to add the constraints */
2832 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "extra_clq_%d_round_%d", cliquepartition[c], nrounds);
2846 /* @todo: try to find a good value for what are enough variables to create this constraint, maybe at least
2891 /** start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
2932 /* we only want to consider constraints with either active or negated of active variables, applyfixings removes
2933 * aggregated and fixed variables to zero, processFixings removes fixings to one but no aggregation
2969 /* @todo: check for covering constraints with only two variables which are equal to a packing constraint with
2973 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
2983 /** creating all necessary data in array structure, collect all clique constraint variables and occurrences,
2994 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
2996 int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
3030 /* here we should have no covering constraints anymore and the constraint data should be merged */
3031 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
3051 assert(SCIPvarIsActive(var) || (SCIPvarIsNegated(var) && SCIPvarIsActive(SCIPvarGetNegationVar(var))));
3066 SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3074 /* the number of occurrences of a variable is not limited by the locks (so maybe we have to increase memory),
3075 * because for examples converted cuts are not check and therefore they have no locks on their variables */
3079 SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3099 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3100 int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
3145 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3147 int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
3166 assert(SCIPvarGetNegatedVar(addvar) != NULL && SCIPhashmapExists(vartoindex, (void*) SCIPvarGetNegatedVar(addvar)));
3168 /* @note because we can only have created a negated variable, and we already allocated enough memory for
3171 SCIPsortedvecInsertDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, addvar, nusefulvars, NULL);
3178 SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3189 SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3202 /** check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3210 SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3214 SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3218 int*const naggregations, /**< pointer to store number of aggregations which are not yet performed;
3221 int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3261 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3263 SCIPdebugMsg(scip, "empty set-partition/-covering constraint <%s> found -> cutoff\n", SCIPconsGetName(cons));
3273 SCIPdebugMsg(scip, " -> deleting constraint <%s>, no variables left\n", SCIPconsGetName(cons));
3291 SCIPdebugMsg(scip, " -> deleting set-covering constraint <%s>, at least two variables are fixed to 1\n", SCIPconsGetName(cons));
3298 SCIPdebugMsg(scip, "set partitioning / packing constraint <%s> is infeasible, %d variables fixed to one\n", SCIPconsGetName(cons), consdata->nfixedones);
3310 if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING && consdata->nfixedzeros < nvars - 1 ) /*lint !e641*/
3318 SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(vars[v]));
3336 if( !SCIPconsIsModifiable(cons) || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3339 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3354 /* all variables were fixed to zero then either delete the constraint or stop with infeasibility */
3363 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3365 SCIPdebugMsg(scip, "set partitioning / covering constraint <%s> is infeasible\n", SCIPconsGetName(cons));
3372 SCIPdebugMsg(scip, " -> deleting set-packing constraint <%s>, all variables are fixed to zero\n", SCIPconsGetName(cons));
3380 /* all but one variable were fixed to zero then delete the constraint and for setpartition fix the remaining variable to 1 */
3390 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3398 SCIPdebugMsg(scip, "trying to fix <%s> to 1 due to it's the last unfixed variable is the set-partitioning/covering constraint\n", SCIPvarGetName(vars[v]));
3419 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all %svariables are fixed\n", SCIPconsGetName(cons), consdata->setppctype == (int) SCIP_SETPPCTYPE_PACKING ? "but one " : "");
3427 /* all but two variable were fixed to zero in a setpartitioning constraint then delete the constraint and
3430 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros + 2 == nvars ) /*lint !e641*/
3459 SCIPdebugMsg(scip, "trying to aggregate <%s> and <%s> due to they are the last two unfixed variables in the set partitionning constraint <%s>\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]), SCIPconsGetName(cons));
3462 /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
3470 SCIP_CALL( SCIPaggregateVars(scip, var, vars[v], 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
3491 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3504 SCIPdebugMsg(scip, "memorize the aggregation of <%s> + <%s> = 1, because they are the last two unfixed variable in the set partitioning constraints <%s>\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]), SCIPconsGetName(cons));
3514 /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
3515 BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
3527 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3538 /* we should never be here, because the last to unfixed variables should have been either aggregated or a cutoff
3559 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3561 int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
3562 int*const countofoverlapping, /**< the amount of variables of cons which overlap in all other constraint */
3567 SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3570 SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3574 int*const naggregations, /**< pointer to store number of aggregations which are not yet performed; */
3575 int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3658 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3661 SCIP_CALL( presolvePropagateCons(scip, cons1, FALSE, undoneaggrvars, undoneaggrtypes, naggregations, saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
3686 SCIPdebugMsg(scip, "constraint <%s> overlaps with constraint <%s> by %d variables\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), countofoverlapping[c]);
3707 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3726 /* all variables inside the second clique constraint should be either active or negated of an active one */
3727 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3755 assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
3762 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3768 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));
3785 /* because the constraint's are merged it is not possible that one constraint contains a negated
3801 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));
3817 /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
3819 if( consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nfixedzeros == nvars1 && consdata1->nfixedones != 1 ) /*lint !e641*/
3821 SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
3829 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
3835 /* could already be deleted because the constraint was included in another set partition constraint */
3839 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
3848 * @note that zero fixations from above can only appear through a set-partitioning constraint, this means if
3849 * cons was the set-partitioning constraint only variables which are not in this constraint could be fixed
3850 * to zero, and this also means that the overlapping variables in this particular case are still active or
3852 * later on it could be possible that even variables in cons are fixed to zero, which can lead to wrong
3853 * results when checking if countofoverlapping[c] + consdata1->nfixedzeros == nvars1, because a fixed
3856 else if( (!overlapdestroyed && countofoverlapping[c] + consdata1->nfixedzeros == nvars1) || countofoverlapping[c] == nvars1 )
3872 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3891 /* all variables inside the second clique constraint should be either active or negated of an active one */
3892 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3893 /* all variables inside the first clique constraint should be either active or negated of an active one */
3894 assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
3906 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
3923 assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
3930 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3933 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(var));
3954 /* because the constraint's are merged it is not possible that one constraint contains a negated
3955 * variable of another and because all variables in cons1 are in cons this should be really the same
3971 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars[v]));
3986 /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
3988 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros == nvars && consdata->nfixedones != 1 ) /*lint !e641*/
3990 SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
3996 /* could already be deleted because the constraint was included in another set partition constraint */
4000 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
4008 /* due to fixings in cons0 mark overlapping invalid for checking with fixedzero variables together */
4017 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
4025 /* if cons has only one unfixed variable which is not in cons1 and cons1 has one variable which does not appear in
4026 * cons and both constraints are setpartitioning constraints we might aggregate both not overlapping variables and
4029 else if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1 && countofoverlapping[c] == nvars1 - 1 ) /*lint !e641*/
4045 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
4064 /* all variables inside the second clique constraint should be either active or negated of an active one */
4065 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
4066 /* all variables inside the first clique constraint should be either active or negated of an active one */
4067 assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
4077 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
4090 assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
4095 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4119 /* because the constraint's are merged it is not possible that one constraint contains a negated variable
4127 SCIPdebugMsg(scip, "two set-partitioning constraint <%s> and <%s> have only one variable not in common, but this variable <%s> appears in one constraint as the negated version as in the other constraint\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), SCIPvarGetName(vars[v]));
4137 /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
4167 /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
4171 SCIPdebugMsg(scip, "memorize the aggregation of <%s> == <%s>, because they are the last two variable which are different in these two set partitioning constraints <%s> <%s>\n", SCIPvarGetName(aggvar1), SCIPvarGetName(aggvar2), SCIPconsGetName(cons), SCIPconsGetName(cons1));
4181 /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
4182 BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
4194 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it is dominated by constraint <%s>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons));
4202 /* w.l.o.g. cons is a setpartitioning constraint and countofoverlapping == nvars - oldnfixedzeros - 1 we can
4203 * delete all overlapping variables in cons1 and add the negated variable of the not overlapped variable to cons
4206 else if( shrinking && !overlapdestroyed && countofoverlapping[c] > 1 && ((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) || (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars1 - 1)) ) /*lint !e641*/
4225 assert((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING) != (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING) || countofoverlapping[c] != nvars - 1 || countofoverlapping[c] != nvars1 - 1); /*lint !e641*/
4231 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
4237 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) /*lint !e641*/
4262 /* iterate over the both cliques variables the "same" time, here we need the backward loop, because we
4278 /* all variables inside the second clique constraint should be either active or negated of an active one */
4279 assert(SCIPvarIsActive(varstochange[v1]) || (SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1]))));
4280 /* all variables inside the first clique constraint should be either active or negated of an active one */
4281 assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4291 assert(SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v])));
4304 assert(SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1])));
4309 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4323 /* because the constraint's are merged it is not possible that one constraint contains a negated variable
4330 SCIPdebugMsg(scip, "-> trying to fix <%s> to 0 because it would exist twice in a constraint\n", SCIPvarGetName(varstochange[v1]));
4344 /* the above fixing is equal to the fixation of varstostay[v] to 1, so we can call presolvePropagateCons() for consstay */
4345 SCIP_CALL( presolvePropagateCons(scip, constostay, FALSE, NULL, NULL, NULL, NULL, nfixedvars, naggrvars, ndelconss, cutoff) );
4351 /* correct local data structure, remove variable from constraint entry where it will be removed */
4354 SCIPdebugMsg(scip, " -> deleting variable <%s> in constraint <%s> number %d, because it will be replaced\n", SCIPvarGetName(varstochange[v1]), SCIPconsGetName(constochange), constochangeidx);
4376 /* all variables inside the first clique constraint should be either active or negated of an active one */
4377 assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4389 SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(constochange), constochangeidx);
4399 SCIP_CALL( addCliqueDataEntry(scip, addvar, constochangeidx, TRUE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4411 /** @todo try another variant by determine lifting variables as the intersection of all cliques variables of the
4422 SCIP_Bool** cliquevalues, /**< pointer to clique values of constraint-variables, either one if the
4449 int nottocheck; /* will be the position for a variable in cons0 which is in negated form in the same clique */
4502 /* check that constraint variables are still correctly sorted, indices of active variables should be decreasing */
4509 /* all variables which we have inside the clique constraint and which can possibly be added should be either active or negated */
4510 assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
4511 assert(SCIPvarIsActive(usefulvars[v1]) || (SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1]))));
4513 /* constraint should during adding of variables stay merged, because for each variable which is added holds that
4514 * the index of this corresponding active variable is pairwise different to all indices of all active
4516 * @note it should not happen that we add one variable and the corresponding counterpart to the same constraint */
4524 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
4536 assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4544 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4550 /* variable index in the constraint is greater than the other one, so check for possible inclusion of the variable */
4562 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4571 assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
4580 /* variable index in the constraint is equal to the index of the other variable, check if these variables are
4581 * negated of each other so memorize the position and check for possible inclusion of the new variable and if
4602 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4614 assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
4623 /* don't decrease v because it might happen that the corresponding negated variable of var is next in
4629 /* if k is smaller than 0 than the possible new variables is in the same clique with all variables of cons,
4635 /* we found a variable which is the negated variable of another one in this clique so we can fix all
4636 * other variable to zero and if it's a partitioning constraint we can also fix the variable of the
4652 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4656 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because we could lift a negated variable of another constraint variable\n", SCIPvarGetName(vars[k]));
4675 assert(SCIPvarIsActive(vars[nottocheck]) || (SCIPvarGetStatus(vars[nottocheck]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[nottocheck]))));
4677 SCIPdebugMsg(scip, "trying to fix <%s> to 1 due to this setpartitioning variable is with its negated in the same clique\n", SCIPvarGetName(vars[nottocheck]));
4678 /* fix the remaining variable to one, due to it's the only one left to satisfy the constraint */
4692 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to active and negated variable in the same clique constraint\n", SCIPconsGetName(cons), arraypos);
4699 /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4702 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1 + 1]));
4717 /* we have found a new variable for a set packing constraint cons, so add the found variable to the first constraint */
4729 SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(usefulvars[v1 + 1]), SCIPconsGetName(cons), arraypos);
4739 SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4741 /* we need the new pointer to the variables, because due to adding variables it is possible that we
4742 * did reallocate the variables array inside the constraint, the index v should stay the same because the
4781 assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4797 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4806 assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
4818 /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4821 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1]));
4848 SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(cons), arraypos);
4858 SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4860 /* we need the new pointer to the variables, because due to adding variables it is possible that we
4861 * did reallocate the variables array inside the constraint, the index v should stay the same because the
4893 SCIP_Bool*const undoneaggrtypes, /**< aggregation type storage, type FALSE means the aggregation is of the
4923 SCIPdebugMsg(scip, "trying to aggregate <%s> %s <%s>%s\n", SCIPvarGetName(var1), undoneaggrtypes[a] ? "=" : "+", SCIPvarGetName(var2), undoneaggrtypes[a] ? "" : " = 1");
4926 /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
4936 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, -1.0, 0.0, cutoff, &redundant, &aggregated) );
4940 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
4949 /* binary variables should always be aggregated, or due to fixation the aggregation is redundant */
4965 /** check whether we can combine or grow cliques so some constraints become redundant or we can fix variables */
4966 /** @todo try another variant, by building up the clique graph and delete unnecessary (transitive closure) edges and do
4986 /* extend cliques/constraints by checking whether some variables are in the same clique, no pairwise clique lifting
4989 SCIP_CONS** usefulconss; /* array with pointers of constraint of setpartitioning and setpacking type */
4990 SCIP_VAR** usefulvars; /* array with pointers of variables in setpartitioning and setpacking constraints */
4991 int** varconsidxs; /* array consisting of constraint indices in which the corresponding variable exists */
4995 SCIP_Bool* cliquevalues = NULL; /* values of clique-variables, either one if the variable is active or zero if the variable is negated */
5011 SCIP_Bool* undoneaggrtypes; /* storage for not yet performed aggregation type (x = y or x + y = 1) */
5037 susefulvars = 2 * nvars; /* two times because of negated vars, maybe due to deleted variables we need to increase this */
5039 /* a hashmap from varindex to postion in varconsidxs array, because above is still too small */
5042 /* get temporary memory for the aggregation storage, to memorize aggregations which will be performed later, otherwise we would destroy our local data structures */
5049 /* get temporary memory for all clique constraints, all appearing variables and the mapping from variables to constraints */
5082 /* try to create a clique-partition over all binary variables and create these cliques as new setppc constraints
5083 * and add them to the usefulconss array and adjust all necessary data this will hopefully lead to faster
5093 /* add extra clique constraints resulting from the cliquepartition calculation to SCIP and to the local data structure */
5094 SCIP_CALL( addExtraCliques(scip, binvars, nbinvars, cliquepartition, ncliques, usefulconss, &nusefulconss,
5097 /* bad hack, we don't want to count these artificial created constraints if they got deleted, so ndelconss
5098 * can become negative which will be change to zero at the end of this method if it's still negative
5109 /* start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
5112 SCIP_CALL( collectCliqueConss(scip, conss, nconss, usefulconss, &nusefulconss, nfixedvars, ndelconss, nchgcoefs, cutoff) );
5113 /* @Note: Even after the call above some constraints can have fixed variables, because it might happen that caused by
5123 /* @todo: maybe sort them after biggest indices too, or another variant would be to restore the order as they were
5126 /* sort constraints first after type (partitioning before packing) and second after number of variables such that the
5127 * partitioning constraints have increasing number of variables and the packing constraints have decreasing number of
5128 * variables, because we loop from back to front we sort them downwards, so they are the other way around
5132 /* creating all necessary data in array structure, collect all clique constraint variables and occurrences */
5133 SCIP_CALL( collectCliqueData(scip, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs, &maxnvars) );
5141 /* sort usefulvars after indices of variables, negated and active counterparts will stand side by side */
5144 /* extend cliques/constraints by checking whether some variables of a second constraint are in the same clique */
5163 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
5166 SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
5177 /* we need to determine the cliquedata in each iteration because we eventual will change it later */
5184 /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5217 SCIP_CALL( checkForOverlapping(scip, cons0, c, c, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex,
5218 varnconss, maxnvarconsidx, varconsidxs, countofoverlapping, conshdlrdata->cliqueshrinking, &chgcons0,
5237 /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5243 /* check cons0 again for redundancy/fixings, because due to fixings in all other constraints it might happen that cons0 is redundant now */
5246 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
5249 SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
5263 /* iterate over the cliques variables and all possible new clique variables at the "same" time, determine starting
5266 * @note: it might be better to start the first round with our computed v1, but maybe it's better to switch to
5270 /* we try to add all variables to the partitioning constraints, to try to fix as much as possible */
5280 /* find start position of variable which we will try to add to our constraint, so we will get better clique constraints */
5281 (void) SCIPsortedvecFindDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, (void*)cons0vars[ncons0vars - 1], nusefulvars, &v1);
5283 /* if constraint is not merged and we found a variable which is negated the same as it's neighbour we have to
5285 if( v1 + 1 < nusefulvars && ((SCIPvarIsNegated(usefulvars[v1 + 1]) && SCIPvarGetNegatedVar(usefulvars[v1 + 1]) == usefulvars[v1]) || (SCIPvarIsNegated(usefulvars[v1]) && SCIPvarGetNegatedVar(usefulvars[v1]) == usefulvars[v1 + 1])) )
5297 assert(SCIPvarIsActive(cons0vars[v]) || (SCIPvarGetStatus(cons0vars[v]) == SCIP_VARSTATUS_NEGATED &&
5306 SCIP_CALL( liftCliqueVariables(scip, cons0, c, usefulvars, &nusefulvars, v1, &cliquevalues, vartoindex, varnconss,
5356 /* check for overlapping constraint after lifting, in the first round we will only check up front */
5357 SCIP_CALL( checkForOverlapping(scip, cons0, c, (conshdlrdata->nclqpresolve > 0) ? nusefulconss : c,
5358 usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs,
5375 /* free temporary memory for constraints, variables and the mapping between them in reverse order as they were
5395 SCIP_CALL( performAggregations(scip, conshdlrdata, undoneaggrvars, undoneaggrtypes, naggregations, naggrvars, cutoff) );
5463 if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
5466 ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING), &infeasible, &nlocalbdchgs) );
5477 /* a two-variable set covering constraint x + y >= 1 yields the implication x == 0 -> y == 1 */
5495 /** perform multi-aggregation on variables resulting from a set-partitioning/-packing constraint */
5499 SCIP_Bool linearconshdlrexist,/**< does the linear constraint handler exist, necessary for multi-aggregations */
5500 SCIP_VAR** vars, /**< all variables including the variable to which will be multi-aggregated */
5505 )
5523 SCIP_CALL( SCIPaggregateVars(scip, vars[pos], vars[nvars - pos - 1], 1.0, 1.0, 1.0, infeasible, &redundant, aggregated) );
5526 SCIPdebugMsg(scip, "aggregated %s = 1 - %s\n", SCIPvarGetName(vars[pos]), SCIPvarGetName(vars[nvars - pos - 1]));
5552 SCIPdebugMsg(scip, "multi-aggregating binary variable <%s> (locks: [%d,%d]; to %d variables)\n",
5557 SCIP_CALL( SCIPmultiaggregateVar(scip, vars[pos], nvars - 1, tmpvars, scalars, 1.0, infeasible, aggregated) );
5571 /** determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and negated)
5574 * we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint or
5577 * 1. c1: x + y + z = 1, uplocks(x) = 1, downlocks(x) = 1 => x = 1 - y - z and change c1 to y + z <= 1
5579 * 2. c2: x + y + z <= 1, uplocks(x) = 1, downlocks(x) = 0, obj(x) < 0 => x = 1 - y - z and change c2 to y + z <= 1
5585 * 4. e1: x + y + z == 1 and e2: ~x + u + v (<= or ==) 1, uplocks(x) = (1 or 2), downlocks(x) = 2
5588 * we can also aggregate a variable in a set-packing constraint with only two variables when the uplocks are equal to
5593 * @todo might want to multi-aggregate variables even with more locks, when the fill in is still smaller or equal to
5667 if( (nuplocks == 1 && ndownlocks <= 1) || (nuplocks <= 1 && ndownlocks == 1) || (nuplocks <= 2 && ndownlocks <= 2 && SCIPvarGetNegatedVar(binvars[v]) != NULL) )
5698 /* determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and
5701 * we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint
5772 /* if the constraint was not merged and consists of a variable with its negation, the constraint is redundant */
5793 SCIPdebugMsg(scip, "empty set partition constraint <%s> led to infeasibility\n", SCIPconsGetName(cons));
5799 SCIPdebugMsg(scip, "fixing <%s> to 1 because this variable is the last variable in a set partition constraint <%s>\n", SCIPvarGetName(consdata->vars[0]), SCIPconsGetName(cons));
5809 SCIPdebugMsg(scip, "deleting redundant set-partition constraint <%s>\n", SCIPconsGetName(cons));