cons_setppc.c
Go to the documentation of this file.
17 * @brief Constraint handler for the set partitioning / packing / covering constraints \f$1^T x\ \{=, \le, \ge\}\ 1\f$.
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
59 #define CONSHDLR_ENFOPRIORITY -700000 /**< priority of the constraint handler for constraint enforcing */
60 #define CONSHDLR_CHECKPRIORITY -700000 /**< priority of the constraint handler for checking feasibility */
61 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
62 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
63 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
65 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
66 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
67 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
68 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
73 #define LINCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of linear constraints */
74 #define QUADCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of linear constraints */
77 #define EVENTHDLR_DESC "bound change event handler for set partitioning / packing / covering constraints"
83 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
86 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
88 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
92 /*#define VARUSES*/ /* activate variable usage counting, that is necessary for LP and pseudo branching */
93 /*#define BRANCHLP*/ /* BRANCHLP is only useful if the ENFOPRIORITY is set to a positive value */
98 #define DEFAULT_NPSEUDOBRANCHES 2 /**< number of children created in pseudo branching (0: disable branching) */
101 #define DEFAULT_CLIQUELIFTING FALSE /**< should we try to lift variables into other clique constraints, fix
105 #define DEFAULT_ADDVARIABLESASCLIQUES FALSE/**< should we try to generate extra clique constraint out of all binary
108 #define DEFAULT_CLIQUESHRINKING TRUE /**< should we try to shrink the number of variables in a clique constraints, by
112 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
122 SCIP_CONSHDLR* conshdlrlinear; /**< pointer to linear constraint handler or NULL if not included */
127 int npseudobranches; /**< number of children created in pseudo branching (0 to disable branching) */
135 SCIP_Bool enablecliquelifting;/**< check whether we have enough changes to run the lifting procedure again */
139 SCIP_Bool addvariablesascliques;/**< should we try to generate extra clique constraint out of all binary
143 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
144 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
160 unsigned int cliqueadded:1; /**< was the set partitioning / packing constraint already added as clique? */
162 unsigned int changed:1; /**< was constraint changed since last redundancy round in preprocessing? */
165 unsigned int presolpropagated:1; /**< was the constraint already propagated in presolving w.r.t. the current domains? */
177 /** compares two active constraints of type set partitioning or set packing such that a "-1" is return if
179 * 2. both constraints are set partitioning constraints and the second has more! variables than the first or
180 * 3. both constraints are set packing constraints and the second has less! variables than the first
210 (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) || /*lint !e641*/
211 (consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars) ) /*lint !e641*/
213 else if( (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars) ) /*lint !e641*/
217 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*/
222 /** sort constraints first after type (partitioning before packing before covering) and second after number of
223 * variables such that the partitioning constraints have increasing number of variables and the packing constraints
231 /** compares two setppc constraints such that a "-1" is return if the first constraint is active and
234 * 3. both constraints are set partitioning constraints and the second has more! variables than the first or
235 * 4. both constraints are set packing constraints and the second has less! variables than the first
269 assert(SCIP_SETPPCTYPE_PARTITIONING < SCIP_SETPPCTYPE_PACKING && SCIP_SETPPCTYPE_PACKING < SCIP_SETPPCTYPE_COVERING);
273 (((SCIP_SETPPCTYPE)consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) ||
274 ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars))) )
276 else if( ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_COVERING || (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars)) )
280 assert(consdata1->setppctype > consdata2->setppctype || ((consdata1->setppctype == consdata2->setppctype) &&
282 || (consdata1->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars < consdata2->nvars)))); /*lint !e641*/
287 /** sort constraints first after type (partitioning before packing before covering) and second after number of
288 * variables such that the partitioning constraints have increasing number of variables and the packing constraints
361 /** creates constraint handler data for set partitioning / packing / covering constraint handler */
390 /** frees constraint handler data for set partitioning / packing / covering constraint handler */
430 /* if the variable is the negation of a problem variable, count the varuses in the problem variable */
558 SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
561 SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
580 /* @todo the setppc constraint handler does not remove fixed variables from its var array; removing those
581 * variables is only possible if we consider the values of nfixedones and nfixedzeros in all propagation methods
631 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
638 (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
674 SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
677 SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
687 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
696 SCIP_CONSDATA** consdata /**< pointer to store the set partitioning / packing / covering constraint */
833 SCIPdebugMsg(scip, " -> converting <%s> into setppc type %d\n", SCIPconsGetName(cons), setppctype);
910 * - SCIP_EVENTTYPE_BOUNDCHANGED: Is used to count the number of variable fixed locally to zero and one. That helps
915 * - SCIP_EVENTTYPE_VARFIXED: Is used to get informed if a variable of the constraint was aggregated which means was
930 /* during presolving, we may fix the last unfixed variable or do an aggregation if there are two unfixed variables */
931 if( SCIPconsIsActive(cons) && ((SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE) && (consdata->nfixedzeros >= consdata->nvars - 2)) )
1105 if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR )
1175 /* the last variable of the constraint was deleted; mark it for propagation (so that it can be deleted) */
1204 /** in case a part (more than one variable) in the setppc constraint is independent of every else (is locked only by
1216 * (ii) a variable x has exactly 0 uplocks and arbitrary downlocks and a variable y has exactly 1 downlock and
1228 * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 1 downlock and
1237 * - fix the variable with the smallest object coefficient to one if the object coefficient is negative or zero
1240 * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 0 downlocks and
1246 * Note: the following dual reduction for set covering and set packing constraints is already performed by the presolver
1249 * - if a variable in a set covering constraint is only locked by that constraint and has negative or zero
1252 * - if a variable in a set packing constraint is only locked by that constraint and has positive or zero
1255 * Note: all dual reduction (ii) could also be performed by the "domcol" presolver, but cause the pairwise comparison of
1256 * columns is only done heuristically (and here it should be even cheaper) we perform them here (too)
1265 SCIP_RESULT* result /**< pointer to store the result SCIP_SUCCESS, if presolving was performed */
1293 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
1294 * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are
1305 /* modifiable non-covering constraints cannot be deleted if one variable is fixed to one, because the propagation for
1317 /* we don't want to consider small constraints (note that the constraints can be modifiable, so we can't delete this
1351 /* check if we can apply the dual reduction; therefore count the number of variables where the setppc has the only
1385 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1417 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1447 /* if we got a set covering constraint and not all variables are locked from this constraint it might not get
1448 * redundant (which is case if it is not possible to fix at least one variable to one), we fix all redundant
1462 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1475 || (SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksDownType(activevar, SCIP_LOCKTYPE_MODEL)
1476 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksUpType(activevar, SCIP_LOCKTYPE_MODEL)));
1478 || (SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksUpType(activevar, SCIP_LOCKTYPE_MODEL)
1479 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == SCIPvarGetNLocksDownType(activevar, SCIP_LOCKTYPE_MODEL)));
1491 /* if variables has a negative objective contribution, and is uplocked by another constraint we cannot fix
1494 if( (fixval == 1.0 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) > nlockups) || objval < bestobjval )
1501 SCIPdebugMsg(scip, " -> dual-fixed dominated variable <%s> == %g\n", SCIPvarGetName(var), fixval);
1507 /* if all variables but the domination variable is fixed and the constraint is not modifiables or the constraint is a
1508 * covering constraint and the bestobjval is less than or equal to zero, we can fix the domination variable (with best
1511 if( ((*nfixedvars - noldfixed == nvars - 1) && !SCIPconsIsModifiable(cons)) || (setppctype == SCIP_SETPPCTYPE_COVERING && bestobjval <= 0.0) )
1513 /* in case of a set packing constraint with positive objective values, all variables can be fixed to zero; in all
1529 SCIPdebugMsg(scip, " -> dual-fixed best variable <%s> == %g\n", SCIPvarGetName(vars[idx]), fixval);
1569 {
1612 assert(SCIPvarIsActive(var1) || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_FIXED);
1622 assert(SCIPvarIsActive(var2) || SCIPvarGetStatus(var2) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var2) == SCIP_VARSTATUS_FIXED);
1691 SCIP_CALL( delCoefPos(scip, cons, v) ); /* only some changed behind position v-1, so it's okay */
1756 if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR || (SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_NEGATED && SCIPvarGetStatus(SCIPvarGetNegatedVar(repvar)) == SCIP_VARSTATUS_MULTAGGR) )
1773 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, nconsvars, &constant, &requiredsize, TRUE) );
1780 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1795 SCIPerrorMessage("try to resolve a multi-aggregation with a non-binary variable <%s>\n", consvars[v2]);
1832 SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(consdata->vars[v2]));
1854 if( ndelconss != NULL && (nfixedvars != NULL || consdata->nvars == 1 || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING) )
1877 assert(SCIPvarIsActive(consvars[v2]) || (SCIPvarGetStatus(consvars[v2]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(consvars[v2]))));
1892 /* it might happen that there are more than one multi-aggregated variable, so we need to get the whole
1898 /* memory needed is at least old number of variables - 1 + number of variables in first multi-aggregation */
1914 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, size, &constant, &requiredsize, TRUE) );
1916 /* if space was not enough (we found another multi-aggregation), we need to resize the buffers */
1922 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1983 SCIPwarningMessage(scip, "setppc constraint <%s> has a multi-aggregated variable, which was not resolved and therefore could lead to aborts\n", SCIPconsGetName(cons));
2014 /** analyzes conflicting assignment on given constraint where all of the variables where assigned to zero,
2020 SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
2027 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
2035 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
2049 /** analyzes conflicting assignment on given constraint where two of the variables where assigned to one,
2055 SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
2063 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
2071 /* initialize conflict analysis, and add the two variables assigned to one to conflict candidate queue */
2091 /** checks constraint for violation only looking at the fixed variables, applies further fixings if possible */
2099 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
2101 {
2128 /*SCIPdebugMsg(scip, "processing constraint <%s> with respect to fixed variables (%d fixed to 0.0, %d fixed to 1.0)\n",
2157 SCIPdebugMsg(scip, " -> fixing all other variables to zero in set packing/partitioning constraint <%s>\n",
2161 * this could result in additional variables fixed to one due to aggregations; in this case, the
2172 assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
2191 /* the fixed to one variable must have been found, and at least one variable must have been fixed */
2202 SCIPdebugMsg(scip, " -> disabling set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2222 SCIPdebugMsg(scip, " -> conflict on set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2237 * - a set partitioning or covering constraint is infeasible, and if it's unmodifiable, the node
2253 SCIPdebugMsg(scip, " -> set covering/partitioning constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2272 * - an unmodifiable set partitioning or covering constraint is feasible and can be disabled after the
2301 assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
2304 SCIPdebugMsg(scip, " -> fixing remaining variable <%s> to one in set covering/partitioning constraint <%s>\n",
2331 SCIP_CONSDATA* consdata, /**< set partitioning / packing / covering constraint to be checked */
2349 sumbound = ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING ? 1.0 : 1.0 + 2*SCIPfeastol(scip));
2350 for( v = 0; v < nvars && sum < sumbound; ++v ) /* if sum >= sumbound, the feasibility is clearly decided */
2365 /* in case of partitioning, the violation is equal to the absolute difference between sum and 1 */
2426 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, SCIPconsGetHdlr(cons), SCIPconsGetName(cons), lhs, rhs,
2429 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row, consdata->nvars, consdata->vars, 1.0) );
2477 )
2504 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2563 {
2577 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2622 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
2746 /* @todo: maybe sort cliques and accordingly the variables so it will be faster to add the constraints */
2755 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "extra_clq_%d_round_%d", cliquepartition[c], nrounds);
2769 /* @todo: try to find a good value for what are enough variables to create this constraint, maybe at least
2814 /** start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
2855 /* we only want to consider constraints with either active or negated of active variables, applyfixings removes
2856 * aggregated and fixed variables to zero, processFixings removes fixings to one but no aggregation
2892 /* @todo: check for covering constraints with only two variables which are equal to a packing constraint with
2896 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
2906 /** creating all necessary data in array structure, collect all clique constraint variables and occurances,
2917 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
2919 int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
2953 /* here we should have no covering constraints anymore and the constraint data should be merged */
2954 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
2974 assert(SCIPvarIsActive(var) || (SCIPvarIsNegated(var) && SCIPvarIsActive(SCIPvarGetNegationVar(var))));
2989 SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
2997 /* the number of occurances of a variable is not limited by the locks (so maybe we have to increase memory),
2998 * because for examples converted cuts are not check and therefore they have no locks on their variables */
3002 SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3022 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3023 int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
3068 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3070 int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
3089 assert(SCIPvarGetNegatedVar(addvar) != NULL && SCIPhashmapExists(vartoindex, (void*) SCIPvarGetNegatedVar(addvar)));
3091 /* @note because we can only have created a negated variable, and we already alloacted enough memory for
3094 SCIPsortedvecInsertDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, addvar, nusefulvars, NULL);
3101 SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3112 SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3125 /** check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3133 SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3137 SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3141 int*const naggregations, /**< pointer to store number of aggregations which are not yet performed;
3144 int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3184 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3186 SCIPdebugMsg(scip, "empty set-partition/-covering constraint <%s> found -> cutoff\n", SCIPconsGetName(cons));
3196 SCIPdebugMsg(scip, " -> deleting constraint <%s>, no variables left\n", SCIPconsGetName(cons));
3214 SCIPdebugMsg(scip, " -> deleting set-covering constraint <%s>, at least two variables are fixed to 1\n", SCIPconsGetName(cons));
3221 SCIPdebugMsg(scip, "set partitioning / packing constraint <%s> is infeasible, %d variables fixed to one\n", SCIPconsGetName(cons), consdata->nfixedones);
3233 if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING && consdata->nfixedzeros < nvars - 1 ) /*lint !e641*/
3241 SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(vars[v]));
3259 if( !SCIPconsIsModifiable(cons) || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3262 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3277 /* all variables were fixed to zero then either delete the constraint or stop with infeasibility */
3286 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3288 SCIPdebugMsg(scip, "set partitioning / covering constraint <%s> is infeasible\n", SCIPconsGetName(cons));
3295 SCIPdebugMsg(scip, " -> deleting set-packing constraint <%s>, all variables are fixed to zero\n", SCIPconsGetName(cons));
3303 /* all but one variable were fixed to zero then delete the constraint and for setpartition fix the remaining variable to 1 */
3313 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3321 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]));
3342 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all %svariables are fixed\n", SCIPconsGetName(cons), consdata->setppctype == (int) SCIP_SETPPCTYPE_PACKING ? "but one " : "");
3350 /* all but two variable were fixed to zero in a setpartitioning constraint then delete the constraint and
3353 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros + 2 == nvars ) /*lint !e641*/
3382 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));
3385 /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
3393 SCIP_CALL( SCIPaggregateVars(scip, var, vars[v], 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
3414 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3427 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));
3437 /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
3438 BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
3450 SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3461 /* we should never be here, because the last to unfixed variables should have been either aggregated or a cutoff
3482 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3484 int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
3485 int*const countofoverlapping, /**< the amount of variables of cons which overlap in all other constraint */
3490 SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3493 SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3497 int*const naggregations, /**< pointer to store number of aggregations which are not yet performed; */
3498 int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3581 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3584 SCIP_CALL( presolvePropagateCons(scip, cons1, FALSE, undoneaggrvars, undoneaggrtypes, naggregations, saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
3609 SCIPdebugMsg(scip, "constraint <%s> overlaps with constraint <%s> by %d variables\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), countofoverlapping[c]);
3630 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3649 /* all variables inside the second clique constraint should be either active or negated of an active one */
3650 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3678 assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
3685 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3691 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]));
3708 /* because the constraint's are merged it is not possible that one constraint contains a negated
3724 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]));
3740 /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
3742 if( consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nfixedzeros == nvars1 && consdata1->nfixedones != 1 ) /*lint !e641*/
3744 SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
3752 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
3758 /* could already be deleted because the constraint was included in another set partition constraint */
3762 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
3771 * @note that zero fixations from above can only appear through a set-partitioning constraint, this means if
3772 * cons was the set-partitioning constraint only variables which are not in this constraint could be fixed
3773 * to zero, and this also means that the overlapping variables in this particular case are still active or
3775 * later on it could be possible that even variables in cons are fixed to zero, which can lead to wrong
3776 * results when checking if countofoverlapping[c] + consdata1->nfixedzeros == nvars1, because a fixed
3779 else if( (!overlapdestroyed && countofoverlapping[c] + consdata1->nfixedzeros == nvars1) || countofoverlapping[c] == nvars1 )
3795 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3814 /* all variables inside the second clique constraint should be either active or negated of an active one */
3815 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3816 /* all variables inside the first clique constraint should be either active or negated of an active one */
3817 assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
3829 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
3846 assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
3853 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3856 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(var));
3877 /* because the constraint's are merged it is not possible that one constraint contains a negated
3878 * variable of another and because all variables in cons1 are in cons this should be really the same
3894 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]));
3909 /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
3911 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros == nvars && consdata->nfixedones != 1 ) /*lint !e641*/
3913 SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
3919 /* could already be deleted because the constraint was included in another set partition constraint */
3923 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
3931 /* due to fixings in cons0 mark overlapping invalid for checking with fixedzero variables together */
3940 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
3948 /* if cons has only one unfixed variable which is not in cons1 and cons1 has one variable which does not appaer in
3949 * cons and both constraints are setpartitioning constraints we might aggregate both not overlapping variables and
3952 else if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1 && countofoverlapping[c] == nvars1 - 1 ) /*lint !e641*/
3968 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3987 /* all variables inside the second clique constraint should be either active or negated of an active one */
3988 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3989 /* all variables inside the first clique constraint should be either active or negated of an active one */
3990 assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
4000 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
4013 assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
4018 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4042 /* because the constraint's are merged it is not possible that one constraint contains a negated variable
4050 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]));
4060 /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
4090 /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
4094 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));
4104 /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
4105 BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
4117 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it is dominated by constraint <%s>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons));
4125 /* w.l.o.g. cons is a setpartitioning constraint and countofoverlapping == nvars - oldnfixedzeros - 1 we can
4126 * delete all overlapping variables in cons1 and add the negated variable of the not overlapped variable to cons
4129 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*/
4148 assert((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING) != (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING) || countofoverlapping[c] != nvars - 1 || countofoverlapping[c] != nvars1 - 1); /*lint !e641*/
4154 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
4160 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) /*lint !e641*/
4185 /* iterate over the both cliques variables the "same" time, here we need the backward loop, because we
4201 /* all variables inside the second clique constraint should be either active or negated of an active one */
4202 assert(SCIPvarIsActive(varstochange[v1]) || (SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1]))));
4203 /* all variables inside the first clique constraint should be either active or negated of an active one */
4204 assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4214 assert(SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v])));
4227 assert(SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1])));
4232 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4246 /* because the constraint's are merged it is not possible that one constraint contains a negated variable
4253 SCIPdebugMsg(scip, "-> trying to fix <%s> to 0 because it would exist twice in a constraint\n", SCIPvarGetName(varstochange[v1]));
4267 /* the above fixing is equal to the fixation of varstostay[v] to 1, so we can call presolvePropagateCons() for consstay */
4268 SCIP_CALL( presolvePropagateCons(scip, constostay, FALSE, NULL, NULL, NULL, NULL, nfixedvars, naggrvars, ndelconss, cutoff) );
4274 /* correct local data structure, remove variable from constraint entry where it will be removed */
4277 SCIPdebugMsg(scip, " -> deleting variable <%s> in constraint <%s> number %d, because it will be replaced\n", SCIPvarGetName(varstochange[v1]), SCIPconsGetName(constochange), constochangeidx);
4299 /* all variables inside the first clique constraint should be either active or negated of an active one */
4300 assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4312 SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(constochange), constochangeidx);
4322 SCIP_CALL( addCliqueDataEntry(scip, addvar, constochangeidx, TRUE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4334 /** @todo try another variant by determine lifting variables as the intersection of all cliques variables of the
4345 SCIP_Bool** cliquevalues, /**< pointer to clique values of constraint-variables, either one if the
4372 int nottocheck; /* will be the position for a variable in cons0 which is in negated form in the same clique */
4425 /* check that constraint variables are still correctly sorted, indices of active variables should be decreasing */
4432 /* all variables which we have inside the clique constraint and which can possibly be added should be either active or negated */
4433 assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
4434 assert(SCIPvarIsActive(usefulvars[v1]) || (SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1]))));
4436 /* constraint should during adding of variables stay merged, because for each variable which is added holds that
4437 * the index of this corresponding active variable is pairwise different to all indices of all active
4439 * @note it should not happen that we add one variable and the corresponding counterpart to the same constraint */
4447 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
4459 assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4467 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4473 /* variable index in the constraint is greater than the other one, so check for possible inclusion of the variable */
4485 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4494 assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
4503 /* variable index in the constraint is equal to the index of the other variable, check if these variables are
4504 * negated of each other so memorize the position and check for possible inclusion of the new variable and if
4525 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4537 assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
4546 /* don't decrease v because it might happen that the corresponding negated variable of var is next in
4552 /* if k is smaller than 0 than the possible new variables is in the same clique with all variables of cons,
4558 /* we found a variable which is the negated variable of another one in this clique so we can fix all
4559 * other variable to zero and if it's a partitioning constraint we can also fix the variable of the
4575 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4579 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because we could lift a negated variable of another constraint variable\n", SCIPvarGetName(vars[k]));
4598 assert(SCIPvarIsActive(vars[nottocheck]) || (SCIPvarGetStatus(vars[nottocheck]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[nottocheck]))));
4600 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]));
4601 /* fix the remaining variable to one, due to it's the only one left to satisfy the constraint */
4615 SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to active and negated variable in the same clique constraint\n", SCIPconsGetName(cons), arraypos);
4622 /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4625 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]));
4640 /* we have found a new variable for a set packing constraint cons, so add the found variable to the first constraint */
4652 SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(usefulvars[v1 + 1]), SCIPconsGetName(cons), arraypos);
4662 SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4664 /* we need the new pointer to the variables, because due to adding variables it is possible that we
4665 * did reallocate the variables array inside the constraint, the index v should stay the same because the
4704 assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4720 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4729 assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
4741 /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4744 SCIPdebugMsg(scip, "trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1]));
4771 SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(cons), arraypos);
4781 SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4783 /* we need the new pointer to the variables, because due to adding variables it is possible that we
4784 * did reallocate the variables array inside the constraint, the index v should stay the same because the
4816 SCIP_Bool*const undoneaggrtypes, /**< aggregation type storage, type FALSE means the aggregation is of the
4846 SCIPdebugMsg(scip, "trying to aggregate <%s> %s <%s>%s\n", SCIPvarGetName(var1), undoneaggrtypes[a] ? "=" : "+", SCIPvarGetName(var2), undoneaggrtypes[a] ? "" : " = 1");
4849 /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
4859 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, -1.0, 0.0, cutoff, &redundant, &aggregated) );
4863 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
4872 /* binary variables should always be aggregated, or due to fixation the aggregation is redundant */
4888 /** check whether we can combine or grow cliques so some constraints become redundant or we can fix variables */
4889 /** @todo try another variant, by building up the clique graph and delete unnecessary (transitive closure) edges and do
4909 /* extend cliques/constraints by checking whether some variables are in the same clique, no pairwise clique lifting
4912 SCIP_CONS** usefulconss; /* array with pointers of constraint of setpartitioning and setpacking type */
4913 SCIP_VAR** usefulvars; /* array with pointers of variables in setpartitioning and setpacking constraints */
4914 int** varconsidxs; /* array consisting of constraint indices in which the corresponding variable exists */
4918 SCIP_Bool* cliquevalues = NULL; /* values of clique-variables, either one if the varibale is active or zero if the variable is negated */
4934 SCIP_Bool* undoneaggrtypes; /* storage for not yet performed aggregation type (x = y or x + y = 1) */
4960 susefulvars = 2 * nvars; /* two times because of negated vars, maybe due to deleted variables we need to increase this */
4962 /* a hashmap from varindex to postion in varconsidxs array, because above is still too small */
4965 /* get temporary memory for the aggregation storage, to memorize aggregations which will be performed later, otherwise we would destroy our local data structures */
4972 /* get temporary memory for all clique constraints, all appearing variables and the mapping from variables to constraints */
5005 /* try to create a clique-partition over all binary variables and create these cliques as new setppc constraints
5006 * and add them to the usefulconss array and adjust all necessary data this will hopefully lead to faster
5016 /* add extra clique constraints resulting from the cliquepartition calculation to SCIP and to the local data structure */
5017 SCIP_CALL( addExtraCliques(scip, binvars, nbinvars, cliquepartition, ncliques, usefulconss, &nusefulconss,
5020 /* bad hack, we don't want to count these artificial created constraints if they got deleted, so ndelconss
5021 * can become negative which will be change to zero at the end of this method if it's still negative
5032 /* start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
5035 SCIP_CALL( collectCliqueConss(scip, conss, nconss, usefulconss, &nusefulconss, nfixedvars, ndelconss, nchgcoefs, cutoff) );
5036 /* @Note: Even after the call above some constraints can have fixed variables, because it might happen that caused by
5046 /* @todo: maybe sort them after biggest indices too, or another variant would be to restore the order as they were
5049 /* sort constraints first after type (partitioning before packing) and second after number of variables such that the
5050 * partitioning constraints have increasing number of variables and the packing constraints have decreasing number of
5051 * variables, because we loop from back to front we sort them downwards, so they are the other way around
5055 /* creating all necessary data in array structure, collect all clique constraint variables and occurances */
5056 SCIP_CALL( collectCliqueData(scip, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs, &maxnvars) );
5064 /* sort usefulvars after indices of variables, negated and active counterparts will stand side by side */
5067 /* extend cliques/constraints by checking whether some variables of a second constraint are in the same clique */
5086 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
5089 SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
5100 /* we need to determine the cliquedata in each iteration because we eventual will change it later */
5107 /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5140 SCIP_CALL( checkForOverlapping(scip, cons0, c, c, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex,
5141 varnconss, maxnvarconsidx, varconsidxs, countofoverlapping, conshdlrdata->cliqueshrinking, &chgcons0,
5160 /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5166 /* check cons0 again for redundancy/fixings, because due to fixings in all other constraints it might happen that cons0 is redundant now */
5169 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
5172 SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
5186 /* iterate over the cliques variables and all possible new clique variables at the "same" time, determine starting
5189 * @note: it might be better to start the first round with our computed v1, but maybe it's better to switch to
5193 /* we try to add all variables to the partitioning constraints, to try to fix as much as possible */
5203 /* find start position of variable which we will try to add to our constraint, so we will get better clique constraints */
5204 (void) SCIPsortedvecFindDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, (void*)cons0vars[ncons0vars - 1], nusefulvars, &v1);
5206 /* if constraint is not merged and we found a variable which is negated the same as it's neighbour we have to
5208 if( v1 + 1 < nusefulvars && ((SCIPvarIsNegated(usefulvars[v1 + 1]) && SCIPvarGetNegatedVar(usefulvars[v1 + 1]) == usefulvars[v1]) || (SCIPvarIsNegated(usefulvars[v1]) && SCIPvarGetNegatedVar(usefulvars[v1]) == usefulvars[v1 + 1])) )
5220 assert(SCIPvarIsActive(cons0vars[v]) || (SCIPvarGetStatus(cons0vars[v]) == SCIP_VARSTATUS_NEGATED &&
5229 SCIP_CALL( liftCliqueVariables(scip, cons0, c, usefulvars, &nusefulvars, v1, &cliquevalues, vartoindex, varnconss,
5279 /* check for overlapping constraint after lifting, in the first round we will only check up front */
5280 SCIP_CALL( checkForOverlapping(scip, cons0, c, (conshdlrdata->nclqpresolve > 0) ? nusefulconss : c,
5281 usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs,
5298 /* free temporary memory for constraints, variables and the mapping between them in reverse order as they were
5318 SCIP_CALL( performAggregations(scip, conshdlrdata, undoneaggrvars, undoneaggrtypes, naggregations, naggrvars, cutoff) );
5386 if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
5389 ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING), &infeasible, &nlocalbdchgs) );
5400 /* a two-variable set covering constraint x + y >= 1 yields the implication x == 0 -> y == 1 */
5418 /** perform multi-aggregation on variables resulting from a set-partitioning/-packing constraint */
5422 SCIP_Bool linearconshdlrexist,/**< does the linear constraint handler exist, necessaray for multi-aggregations */
5423 SCIP_VAR** vars, /**< all variables including the variable to which will be multi-aggregated */
5428 )
5445 SCIPdebugMsg(scip, "aggregating %s = 1 - %s\n", SCIPvarGetName(vars[pos]), SCIPvarGetName(vars[nvars - pos - 1]));
5448 SCIP_CALL( SCIPaggregateVars(scip, vars[pos], vars[nvars - pos - 1], 1.0, 1.0, 1.0, infeasible, &redundant, aggregated) );
5472 SCIPdebugMsg(scip, "multi-aggregating binary variable <%s> (locks: [%d,%d]; to %d variables)\n",
5477 SCIP_CALL( SCIPmultiaggregateVar(scip, vars[pos], nvars - 1, tmpvars, scalars, 1.0, infeasible, aggregated) );
5491 /** determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and negated)
5494 * we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint or
5497 * 1. c1: x + y + z = 1, uplocks(x) = 1, downlocks(x) = 1 => x = 1 - y - z and change c1 to y + z <= 1
5499 * 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
5505 * 4. e1: x + y + z == 1 and e2: ~x + u + v (<= or ==) 1, uplocks(x) = (1 or 2), downlocks(x) = 2
5508 * we can also aggregate a variable in a set-packing constraint with only two variables when the uplocks are equal to
5513 * @todo might want to multi-aggregate variables even with more locks, when the fill in is still smaller or equal to
5587 if( (nuplocks == 1 && ndownlocks <= 1) || (nuplocks <= 1 && ndownlocks == 1) || (nuplocks <= 2 && ndownlocks <= 2 && SCIPvarGetNegatedVar(binvars[v]) != NULL) )
5618 /* determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and
5621 * we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint
5692 /* if the constraint was not merged and consists of a variable with its negation, the constraint is redundant */
5713 SCIPdebugMsg(scip, "empty set partition constraint <%s> led to infeasibility\n", SCIPconsGetName(cons));
5719 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));
5729 SCIPdebugMsg(scip, "deleting redundant set-partition constraint <%s>\n", SCIPconsGetName(cons));
5739 if( !donotaggr && consdata->nvars == 2 && dualpresolvingenabled && (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
5747 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
5755 SCIPdebugMsg(scip, "dualpresolve, aggregating %s + %s = 1, in set-packing constraint %s\n", SCIPvarGetName(var), SCIPvarGetName(consdata->vars[1]), SCIPconsGetName(cons));
5758 SCIP_CALL( SCIPaggregateVars(scip, var, consdata->vars[1], 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
5778 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
5786 SCIPdebugMsg(scip, "dualpresolve, aggregating %s + %s = 1, in set-packing constraint %s\n", SCIPvarGetName(var), SCIPvarGetName(consdata->vars[0]), SCIPconsGetName(cons));
5789 SCIP_CALL( SCIPaggregateVars(scip, var, consdata->vars[0], 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
5806 else if( !donotaggr && consdata->nvars == 2 && (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING )
5810 SCIPdebugMsg(scip, "aggregating %s + %s = 1, in set-partition constraint %s\n", SCIPvarGetName(consdata->vars[0]), SCIPvarGetName(consdata->vars[1]), SCIPconsGetName(cons));
5813 SCIP_CALL( SCIPaggregateVars(scip, consdata->vars[0], consdata->vars[1], 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );