All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
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*/
39 #define CONSHDLR_ENFOPRIORITY -700000 /**< priority of the constraint handler for constraint enforcing */
40 #define CONSHDLR_CHECKPRIORITY -700000 /**< priority of the constraint handler for checking feasibility */
41 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
42 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
43 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
45 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
46 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
47 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
48 #define CONSHDLR_DELAYPRESOL FALSE /**< should presolving method be delayed, if other presolvers found reductions? */
49 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
53 #define LINCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of linear constraints */
54 #define QUADCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of linear constraints */
57 #define EVENTHDLR_DESC "bound change event handler for set partitioning / packing / covering constraints"
63 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
65 #define HASHSIZE_SETPPCCONS 131101 /**< minimal size of hash table in setppc constraint tables */
66 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
68 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
70 /*#define VARUSES*/ /* activate variable usage counting, that is necessary for LP and pseudo branching */
71 /*#define BRANCHLP*/ /* BRANCHLP is only useful if the ENFOPRIORITY is set to a positive value */
76 #define DEFAULT_NPSEUDOBRANCHES 2 /**< number of children created in pseudo branching (0: disable branching) */
79 #define DEFAULT_CLIQUELIFTING FALSE /**< should we try to lift variables into other clique constraints, fix
83 #define DEFAULT_ADDVARIABLESASCLIQUES FALSE/**< should we try to generate extra clique constraint out of all binary
86 #define DEFAULT_CLIQUESHRINKING TRUE /**< should we try to shrink the number of variables in a clique constraints, by
90 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
100 SCIP_CONSHDLR* conshdlrlinear; /**< pointer to linear constraint handler or NULL if not included */
105 int npseudobranches; /**< number of children created in pseudo branching (0 to disable branching) */
113 SCIP_Bool enablecliquelifting;/**< check whether we have enough changes to run the lifting procedure again */
117 SCIP_Bool addvariablesascliques;/**< should we try to generate extra clique constraint out of all binary
122 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
123 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
139 unsigned int cliqueadded:1; /**< was the set partitioning / packing constraint already added as clique? */
141 unsigned int changed:1; /**< was constraint changed since last redundancy round in preprocessing? */
155 /** compares two active constraints of type set partitioning or set packing such that a "-1" is return if
157 * 2. both constraints are set partitioning constraints and the second has more! variables than the first or
158 * 3. both constraints are set packing constraints and the second has less! variables than the first
188 (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) || /*lint !e641*/
189 (consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars) ) /*lint !e641*/
191 else if( (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars) ) /*lint !e641*/
195 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*/
200 /** sort constraints first after type (partitioning before packing before covering) and second after number of
201 * variables such that the partitioning constraints have increasing number of variables and the packing constraints
209 /** compares two setppc constraints such that a "-1" is return if the first constraint is active and
212 * 3. both constraints are set partitioning constraints and the second has more! variables than the first or
213 * 4. both constraints are set packing constraints and the second has less! variables than the first
247 assert(SCIP_SETPPCTYPE_PARTITIONING < SCIP_SETPPCTYPE_PACKING && SCIP_SETPPCTYPE_PACKING < SCIP_SETPPCTYPE_COVERING);
251 (((SCIP_SETPPCTYPE)consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) ||
252 ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars))) )
254 else if( ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_COVERING || (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars)) )
258 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*/
263 /** sort constraints first after type (partitioning before packing before covering) and second after number of
264 * variables such that the partitioning constraints have increasing number of variables and the packing constraints
343 /** creates constraint handler data for set partitioning / packing / covering constraint handler */
368 /** frees constraint handler data for set partitioning / packing / covering constraint handler */
404 /* if the variable is the negation of a problem variable, count the varuses in the problem variable */
532 SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
535 SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
558 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
565 (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
604 SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
607 SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
626 SCIP_CONSDATA** consdata /**< pointer to store the set partitioning / packing / covering constraint */
773 SCIPdebugMessage(" -> converting <%s> into setppc type %d\n", SCIPconsGetName(cons), setppctype);
850 * - SCIP_EVENTTYPE_BOUNDCHANGED: Is used to count the number of variable fixed locally to zero and one. That helps
855 * - SCIP_EVENTTYPE_VARFIXED: Is used to get informed if a variable of the constraint was aggregated which means was
1026 if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR )
1116 /** in case a part (more than one variable) in the setppc constraint is independent of every else (is locked only by
1128 * (ii) a variable x has exactly 0 uplocks and arbitrary downlocks and a variable y has exactly 1 downlock and
1140 * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 1 downlock and
1149 * - fix the variable with the smallest object coefficient to one if the object coefficient is negative or zero
1152 * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 0 downlocks and
1158 * Note: the following dual reduction for set covering and set packing constraints is already performed by the presolver
1161 * - if a variable in a set covering constraint is only locked by that constraint and has negative or zero
1164 * - if a variable in a set packing constraint is only locked by that constraint and has positive or zero
1167 * Note: all dual reduction (ii) could also be performed by the "domcol" presolver, but cause the pairwise comparison of
1168 * columns is only done heuristically (and here it should be even cheaper) we perform them here (too)
1177 SCIP_RESULT* result /**< pointer to store the result SCIP_SUCCESS, if presolving was performed */
1205 /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
1206 * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are
1217 /* modifiable non-covering constraints cannot be deleted if one variable is fixed to one, because the propagation for
1229 /* we don't want to consider small constraints (note that the constraints can be modifiable, so we can't delete this
1263 /* check if we can apply the dual reduction; therefore count the number of variables where the setppc has the only
1296 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1328 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1357 /* if we got a set covering constraint and not all variables are locked from this constraint it might not get
1358 * redundant (which is case if it is not possible to fix at least one variable to one), we fix all redundant
1372 /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1383 assert(SCIPvarGetNLocksDown(var) == SCIPvarGetNLocksDown(activevar) && SCIPvarGetNLocksUp(var) == SCIPvarGetNLocksUp(activevar));
1395 /* if variables has a negative objective contribution, and is uplocked by another constraint we cannot fix
1405 SCIPdebugMessage(" -> dual-fixed dominated variable <%s> == %g\n", SCIPvarGetName(var), fixval);
1411 /* if all variables but the domination variable is fixed and the constraint is not modifiables or the constraint is a
1412 * covering constraint and the bestobjval is less than or equal to zero, we can fix the domination variable (with best
1415 if( ((*nfixedvars - noldfixed == nvars - 1) && !SCIPconsIsModifiable(cons)) || (setppctype == SCIP_SETPPCTYPE_COVERING && bestobjval <= 0.0) )
1417 /* in case of a set packing constraint with positive objective values, all variables can be fixed to zero; in all
1420 if( (setppctype == SCIP_SETPPCTYPE_PACKING && bestobjval > 0.0 && SCIPvarGetNLocksDown(vars[idx]) == 0) || setppctype != SCIP_SETPPCTYPE_PACKING || bestobjval <= 0.0 )
1431 SCIPdebugMessage(" -> dual-fixed best variable <%s> == %g\n", SCIPvarGetName(vars[idx]), fixval);
1508 assert(SCIPvarIsActive(var1) || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_FIXED);
1518 assert(SCIPvarIsActive(var2) || SCIPvarGetStatus(var2) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var2) == SCIP_VARSTATUS_FIXED);
1587 SCIP_CALL( delCoefPos(scip, cons, v) ); /* only some changed behind position v-1, so it's okay */
1652 if( SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_MULTAGGR || (SCIPvarGetStatus(repvar) == SCIP_VARSTATUS_NEGATED && SCIPvarGetStatus(SCIPvarGetNegatedVar(repvar)) == SCIP_VARSTATUS_MULTAGGR) )
1669 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, nconsvars, &constant, &requiredsize, TRUE) );
1676 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1691 SCIPerrorMessage("try to resolve a multi-aggregation with a non-binary variable <%s>\n", consvars[v2]);
1728 SCIPdebugMessage("trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(consdata->vars[v2]));
1753 if( ndelconss != NULL && (nfixedvars != NULL || consdata->nvars == 1 || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING) )
1779 assert(SCIPvarIsActive(consvars[v2]) || (SCIPvarGetStatus(consvars[v2]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(consvars[v2]))));
1794 /* it might happen that there are more than one multi-aggregated variable, so we need to get the whole probvar sum over all variables */
1798 /* memory needed is at least old number of variables - 1 + number of variables in first multi-aggregation */
1814 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, size, &constant, &requiredsize, TRUE) );
1816 /* if space was not enough(we found another multi-aggregation), we need to resize the buffers */
1822 SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1886 SCIPwarningMessage(scip, "setppc constraint <%s> has a multi-aggregated variable, which was not resolved and therefore could lead to aborts\n", SCIPconsGetName(cons));
1909 #if 0 /* if variable 'var' was multiaggregated to repvar, than repvar could have been fixed already */
1926 /** analyzes conflicting assignment on given constraint where all of the variables where assigned to zero,
1932 SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
1939 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
1947 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1960 /** analyzes conflicting assignment on given constraint where two of the variables where assigned to one,
1966 SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
1974 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
1982 /* initialize conflict analysis, and add the two variables assigned to one to conflict candidate queue */
2001 /** checks constraint for violation only looking at the fixed variables, applies further fixings if possible */
2009 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
2034 /*SCIPdebugMessage("processing constraint <%s> with respect to fixed variables (%d fixed to 0.0, %d fixed to 1.0)\n",
2063 SCIPdebugMessage(" -> fixing all other variables to zero in set packing/partitioning constraint <%s>\n",
2067 * this could result in additional variables fixed to one due to aggregations; in this case, the
2078 assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
2097 /* the fixed to one variable must have been found, and at least one variable must have been fixed */
2108 SCIPdebugMessage(" -> disabling set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2128 SCIPdebugMessage(" -> conflict on set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2143 * - a set partitioning or covering constraint is infeasible, and if it's unmodifiable, the node
2159 SCIPdebugMessage(" -> set covering/partitioning constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2178 * - an unmodifiable set partitioning or covering constraint is feasible and can be disabled after the
2207 assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
2210 SCIPdebugMessage(" -> fixing remaining variable <%s> to one in set covering/partitioning constraint <%s>\n",
2237 SCIP_CONSDATA* consdata, /**< set partitioning / packing / covering constraint to be checked */
2252 sumbound = ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING ? 1.0 : 1.0 + 2*SCIPfeastol(scip));
2253 for( v = 0; v < nvars && sum < sumbound; ++v ) /* if sum >= sumbound, the feasibility is clearly decided */
2312 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, SCIPconsGetHdlr(cons), SCIPconsGetName(cons), lhs, rhs,
2315 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row, consdata->nvars, consdata->vars, 1.0) );
2390 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2463 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2508 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
2634 /* @todo: maybe sort cliques and accordingly the variables so it will be faster to add the constraints */
2643 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "extra_clq_%d_round_%d", cliquepartition[c], nrounds);
2657 /* @todo: try to find a good value for what are enough variables to create this constraint, maybe at least
2702 /** start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
2743 /* we only want to consider constraints with either active or negated of active variables, applyfixings removes
2744 * aggregated and fixed variables to zero, processFixings removes fixings to one but no aggregation
2776 /* @todo: check for covering constraints with only two variables which are equal to a packing constraint with
2780 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
2790 /** creating all necessary data in array structure, collect all clique constraint variables and occurances,
2801 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
2803 int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
2837 /* here we should have no covering constraints anymore and the constraint data should be merged */
2838 assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
2858 assert(SCIPvarIsActive(var) || (SCIPvarIsNegated(var) && SCIPvarIsActive(SCIPvarGetNegationVar(var))));
2872 SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
2880 /* the number of occurances of a variable is not limited by the locks (so maybe we have to increase memory),
2881 * because for examples converted cuts are not check and therefore they have no locks on their variables */
2885 SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
2905 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
2906 int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
2951 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
2953 int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
2972 assert(SCIPvarGetNegatedVar(addvar) != NULL && SCIPhashmapExists(vartoindex, (void*) SCIPvarGetNegatedVar(addvar)));
2974 /* @note because we can only have created a negated variable, and we already alloacted enough memory for
2977 SCIPsortedvecInsertDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, addvar, nusefulvars, NULL);
2984 SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
2995 SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3008 /** check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3016 SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3020 SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3024 int*const naggregations, /**< pointer to store number of aggregations which are not yet performed;
3027 int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3067 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3069 SCIPdebugMessage("empty set-partition/-covering constraint <%s> found -> cutoff\n", SCIPconsGetName(cons));
3097 SCIPdebugMessage(" -> deleting set-covering constraint <%s>, at least two variables are fixed to 1\n", SCIPconsGetName(cons));
3104 SCIPdebugMessage("set partitioning / packing constraint <%s> is infeasible, %d variables fixed to one\n", SCIPconsGetName(cons), consdata->nfixedones);
3116 if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING && consdata->nfixedzeros < nvars - 1 ) /*lint !e641*/
3124 SCIPdebugMessage("trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(vars[v]));
3142 if( !SCIPconsIsModifiable(cons) || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3145 SCIPdebugMessage(" -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3160 /* all variables were fixed to zero then either delete the constraint or stop with infeasibility */
3169 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3171 SCIPdebugMessage("set partitioning / covering constraint <%s> is infeasible\n", SCIPconsGetName(cons));
3178 SCIPdebugMessage(" -> deleting set-packing constraint <%s>, all variables are fixed to zero\n", SCIPconsGetName(cons));
3186 /* all but one variable were fixed to zero then delete the constraint and for setpartition fix the remaining variable to 1 */
3196 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3204 SCIPdebugMessage("trying to fix <%s> to 1 due to it's the last unfixed variable is the set-partitioning/covering constraint\n", SCIPvarGetName(vars[v]));
3225 SCIPdebugMessage(" -> deleting constraint <%s>, all %svariables are fixed\n", SCIPconsGetName(cons), consdata->setppctype == (int) SCIP_SETPPCTYPE_PACKING ? "but one " : "");
3233 /* all but two variable were fixed to zero in a setpartitioning constraint then delete the constraint and
3236 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros + 2 == nvars ) /*lint !e641*/
3265 SCIPdebugMessage("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));
3268 /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
3276 SCIP_CALL( SCIPaggregateVars(scip, var, vars[v], 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
3297 SCIPdebugMessage(" -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3310 SCIPdebugMessage("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));
3320 /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
3321 BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
3333 SCIPdebugMessage(" -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3344 /* we should never be here, because the last to unfixed variables should have been either aggregated or a cutoff
3365 int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3367 int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
3368 int*const countofoverlapping, /**< the amount of variables of cons which overlap in all other constraint */
3373 SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3376 SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3380 int*const naggregations, /**< pointer to store number of aggregations which are not yet performed; */
3381 int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3464 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3467 SCIP_CALL( presolvePropagateCons(scip, cons1, FALSE, undoneaggrvars, undoneaggrtypes, naggregations, saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
3492 SCIPdebugMessage("constraint <%s> overlaps with constraint <%s> by %d variables\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), countofoverlapping[c]);
3513 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3532 /* all variables inside the second clique constraint should be either active or negated of an active one */
3533 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3561 assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
3568 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3574 SCIPdebugMessage("trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));
3591 /* because the constraint's are merged it is not possible that one constraint contains a negated
3607 SCIPdebugMessage("trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));
3623 /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
3625 if( consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nfixedzeros == nvars1 && consdata1->nfixedones != 1 ) /*lint !e641*/
3627 SCIPdebugMessage("all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
3635 SCIPdebugMessage(" -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
3641 /* could already be deleted because the constraint was included in another set partition constraint */
3645 SCIPdebugMessage(" -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
3654 * @note that zero fixations from above can only appear through a set-partitioning constraint, this means if
3655 * cons was the set-partitioning constraint only variables which are not in this constraint could be fixed
3656 * to zero, and this also means that the overlapping variables in this particular case are still active or
3658 * later on it could be possible that even variables in cons are fixed to zero, which can lead to wrong
3659 * results when checking if countofoverlapping[c] + consdata1->nfixedzeros == nvars1, because a fixed
3662 else if( (!overlapdestroyed && countofoverlapping[c] + consdata1->nfixedzeros == nvars1) || countofoverlapping[c] == nvars1 )
3678 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3697 /* all variables inside the second clique constraint should be either active or negated of an active one */
3698 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3699 /* all variables inside the first clique constraint should be either active or negated of an active one */
3700 assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
3712 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
3729 assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
3736 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3739 SCIPdebugMessage("trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(var));
3760 /* because the constraint's are merged it is not possible that one constraint contains a negated
3761 * variable of another and because all variables in cons1 are in cons this should be really the same
3777 SCIPdebugMessage("trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars[v]));
3792 /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
3794 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros == nvars && consdata->nfixedones != 1 ) /*lint !e641*/
3796 SCIPdebugMessage("all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
3802 /* could already be deleted because the constraint was included in another set partition constraint */
3806 SCIPdebugMessage(" -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
3814 /* due to fixings in cons0 mark overlapping invalid for checking with fixedzero variables together */
3823 SCIPdebugMessage(" -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
3831 /* if cons has only one unfixed variable which is not in cons1 and cons1 has one variable which does not appaer in
3832 * cons and both constraints are setpartitioning constraints we might aggregate both not overlapping variables and
3835 else if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1 && countofoverlapping[c] == nvars1 - 1 ) /*lint !e641*/
3851 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3870 /* all variables inside the second clique constraint should be either active or negated of an active one */
3871 assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3872 /* all variables inside the first clique constraint should be either active or negated of an active one */
3873 assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
3883 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
3896 assert(SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1])));
3901 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3925 /* because the constraint's are merged it is not possible that one constraint contains a negated variable
3933 SCIPdebugMessage("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]));
3943 /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
3973 /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
3977 SCIPdebugMessage("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));
3987 /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
3988 BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
4000 SCIPdebugMessage(" -> deleting constraint <%s> number <%d> because it is dominated by constraint <%s>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons));
4008 /* w.l.o.g. cons is a setpartitioning constraint and countofoverlapping == nvars - oldnfixedzeros - 1 we can
4009 * delete all overlapping variables in cons1 and add the negated variable of the not overlapped variable to cons
4012 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*/
4031 assert((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING) != (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING) || countofoverlapping[c] != nvars - 1 || countofoverlapping[c] != nvars1 - 1); /*lint !e641*/
4037 /* sorting array after indices of variables, negated and active counterparts would stand side by side */
4043 if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) /*lint !e641*/
4068 /* iterate over the both cliques variables the "same" time, here we need the backward loop, because we
4084 /* all variables inside the second clique constraint should be either active or negated of an active one */
4085 assert(SCIPvarIsActive(varstochange[v1]) || (SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1]))));
4086 /* all variables inside the first clique constraint should be either active or negated of an active one */
4087 assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4097 assert(SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v])));
4110 assert(SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1])));
4115 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4129 /* because the constraint's are merged it is not possible that one constraint contains a negated variable
4136 SCIPdebugMessage("-> trying to fix <%s> to 0 because it would exist twice in a constraint\n", SCIPvarGetName(varstochange[v1]));
4150 /* the above fixing is equal to the fixation of varstostay[v] to 1, so we can call presolvePropagateCons() for consstay */
4151 SCIP_CALL( presolvePropagateCons(scip, constostay, FALSE, NULL, NULL, NULL, NULL, nfixedvars, naggrvars, ndelconss, cutoff) );
4157 /* correct local data structure, remove variable from constraint entry where it will be removed */
4160 SCIPdebugMessage(" -> deleting variable <%s> in constraint <%s> number %d, because it will be replaced\n", SCIPvarGetName(varstochange[v1]), SCIPconsGetName(constochange), constochangeidx);
4182 /* all variables inside the first clique constraint should be either active or negated of an active one */
4183 assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4195 SCIPdebugMessage(" -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(constochange), constochangeidx);
4205 SCIP_CALL( addCliqueDataEntry(scip, addvar, constochangeidx, TRUE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4217 /** @todo try another variant by determine lifting variables as the intersection of all cliques variables of the
4228 SCIP_Bool** cliquevalues, /**< pointer to clique values of constraint-variables, either one if the
4255 int nottocheck; /* will be the position for a variable in cons0 which is in negated form in the same clique */
4308 /* check that constraint variables are still correctly sorted, indices of active variables should be decreasing */
4315 /* all variables which we have inside the clique constraint and which can possibly be added should be either active or negated */
4316 assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
4317 assert(SCIPvarIsActive(usefulvars[v1]) || (SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1]))));
4319 /* constraint should during adding of variables stay merged, because for each variable which is added holds that
4320 * the index of this corresponding active variable is pairwise different to all indices of all active
4322 * @note it should not happen that we add one variable and the corresponding counterpart to the same constraint */
4330 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v])));
4342 assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4350 /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4356 /* variable index in the constraint is greater than the other one, so check for possible inclusion of the variable */
4368 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4377 assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
4386 /* variable index in the constraint is equal to the index of the other variable, check if these variables are
4387 * negated of each other so memorize the position and check for possible inclusion of the new variable and if
4408 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4420 assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
4429 /* don't decrease v because it might happen that the corresponding negated variable of var is next in
4435 /* if k is smaller than 0 than the possible new variables is in the same clique with all variables of cons,
4441 /* we found a variable which is the negated variable of another one in this clique so we can fix all
4442 * other variable to zero and if it's a partitioning constraint we can also fix the variable of the
4458 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4462 SCIPdebugMessage("trying to fix <%s> to 0 because we could lift a negated variable of another constraint variable\n", SCIPvarGetName(vars[k]));
4481 assert(SCIPvarIsActive(vars[nottocheck]) || (SCIPvarGetStatus(vars[nottocheck]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[nottocheck]))));
4483 SCIPdebugMessage("trying to fix <%s> to 1 due to this setpartitioning variable is with its negated in the same clique\n", SCIPvarGetName(vars[nottocheck]));
4484 /* fix the remaining variable to one, due to it's the only one left to satisfy the constraint */
4498 SCIPdebugMessage(" -> deleting constraint <%s> number <%d> due to active and negated variable in the same clique constraint\n", SCIPconsGetName(cons), arraypos);
4505 /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4508 SCIPdebugMessage("trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1 + 1]));
4523 /* we have found a new variable for a set packing constraint cons, so add the found variable to the first constraint */
4535 SCIPdebugMessage(" -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(usefulvars[v1 + 1]), SCIPconsGetName(cons), arraypos);
4545 SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4547 /* we need the new pointer to the variables, because due to adding variables it is possible that we
4548 * did reallocate the variables array inside the constraint, the index v should stay the same because the
4587 assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4603 assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4612 assert(SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k])));
4624 /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4627 SCIPdebugMessage("trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1]));
4654 SCIPdebugMessage(" -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(cons), arraypos);
4664 SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4666 /* we need the new pointer to the variables, because due to adding variables it is possible that we
4667 * did reallocate the variables array inside the constraint, the index v should stay the same because the
4699 SCIP_Bool*const undoneaggrtypes, /**< aggregation type storage, type FALSE means the aggregation is of the
4729 SCIPdebugMessage("trying to aggregate <%s> %s <%s>%s\n", SCIPvarGetName(var1), undoneaggrtypes[a] ? "=" : "+", SCIPvarGetName(var2), undoneaggrtypes[a] ? "" : " = 1");
4732 /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
4742 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, -1.0, 0.0, cutoff, &redundant, &aggregated) );
4746 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
4755 /* binary variables should always be aggregated, or due to fixation the aggregation is redundant */
4771 /** check whether we can combine or grow cliques so some constraints become redundant or we can fix variables */
4772 /** @todo try another variant, by building up the clique graph and delete unnecessary (transitive closure) edges and do
4792 /* extend cliques/constraints by checking whether some variables are in the same clique, no pairwise clique lifting
4795 SCIP_CONS** usefulconss; /* array with pointers of constraint of setpartitioning and setpacking type */
4796 SCIP_VAR** usefulvars; /* array with pointers of variables in setpartitioning and setpacking constraints */
4797 int** varconsidxs; /* array consisting of constraint indices in which the corresponding variable exists */
4801 SCIP_Bool* cliquevalues; /* values of clique-variables, either one if the varibale is active or zero if the variable is negated */
4818 SCIP_Bool* undoneaggrtypes; /* storage for not yet performed aggregation type (x = y or x + y = 1) */
4844 susefulvars = 2 * nvars; /* two times because of negated vars, maybe due to deleted variables we need to increase this */
4846 /* a hashmap from varindex to postion in varconsidxs array, because above is still too small */
4847 SCIP_CALL( SCIPhashmapCreate(&vartoindex, SCIPblkmem(scip), SCIPcalcHashtableSize(5 * nvars)) );
4849 /* get temporary memory for the aggregation storage, to memorize aggregations which will be performed later, otherwise we would destroy our local data structures */
4856 /* get temporary memory for all clique constraints, all appearing variables and the mapping from variables to constraints */
4890 /* try to create a clique-partition over all binary variables and create these cliques as new setppc constraints
4891 * and add them to the usefulconss array and adjust all necessary data this will hopefully lead to faster
4901 /* add extra clique constraints resulting from the cliquepartition calculation to SCIP and to the local data structure */
4902 SCIP_CALL( addExtraCliques(scip, binvars, nbinvars, cliquepartition, ncliques, usefulconss, &nusefulconss,
4905 /* bad hack, we don't want to count these artificial created constraints if they got deleted, so ndelconss
4906 * can become negative which will be change to zero at the end of this method if it's still negative
4917 /* start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
4920 SCIP_CALL( collectCliqueConss(scip, conss, nconss, usefulconss, &nusefulconss, nfixedvars, ndelconss, nchgcoefs, cutoff) );
4921 /* @Note: Even after the call above some constraints can have fixed variables, because it might happen that caused by
4931 /* @todo: maybe sort them after biggest indices too, or another variant would be to restore the order as they were
4934 /* sort constraints first after type (partitioning before packing) and second after number of variables such that the
4935 * partitioning constraints have increasing number of variables and the packing constraints have decreasing number of
4936 * variables, because we loop from back to front we sort them downwards, so they are the other way around
4940 /* creating all necessary data in array structure, collect all clique constraint variables and occurances */
4941 SCIP_CALL( collectCliqueData(scip, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs, &maxnvars) );
4950 /* sort usefulvars after indices of variables, negated and active counterparts will stand side by side */
4953 /* extend cliques/constraints by checking whether some variables of a second constraint are in the same clique */
4972 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
4975 SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
4986 /* we need to determine the cliquedata in each iteration because we eventual will change it later */
4993 /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5026 SCIP_CALL( checkForOverlapping(scip, cons0, c, c, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex,
5027 varnconss, maxnvarconsidx, varconsidxs, countofoverlapping, conshdlrdata->cliqueshrinking, &chgcons0,
5046 /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5052 /* check cons0 again for redundancy/fixings, because due to fixings in all other constraints it might happen that cons0 is redundant now */
5055 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
5058 SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
5072 /* iterate over the cliques variables and all possible new clique variables at the "same" time, determine starting
5075 * @note: it might be better to start the first round with our computed v1, but maybe it's better to switch to
5079 /* we try to add all variables to the partitioning constraints, to try to fix as much as possible */
5089 /* find start position of variable which we will try to add to our constraint, so we will get better clique constraints */
5090 (void) SCIPsortedvecFindDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, (void*)cons0vars[ncons0vars - 1], nusefulvars, &v1);
5092 /* if constraint is not merged and we found a variable which is negated the same as it's neighbour we have to
5094 if( v1 + 1 < nusefulvars && ((SCIPvarIsNegated(usefulvars[v1 + 1]) && SCIPvarGetNegatedVar(usefulvars[v1 + 1]) == usefulvars[v1]) || (SCIPvarIsNegated(usefulvars[v1]) && SCIPvarGetNegatedVar(usefulvars[v1]) == usefulvars[v1 + 1])) )
5106 assert(SCIPvarIsActive(cons0vars[v]) || (SCIPvarGetStatus(cons0vars[v]) == SCIP_VARSTATUS_NEGATED &&
5115 SCIP_CALL( liftCliqueVariables(scip, cons0, c, usefulvars, &nusefulvars, v1, &cliquevalues, vartoindex, varnconss,
5165 /* check for overlapping constraint after lifting, in the first round we will only check up front */
5166 SCIP_CALL( checkForOverlapping(scip, cons0, c, (conshdlrdata->nclqpresolve > 0) ? nusefulconss : c,
5167 usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs,
5187 /* free temporary memory for constraints, variables and the mapping between them in reverse order as they were
5208 SCIP_CALL( performAggregations(scip, conshdlrdata, undoneaggrvars, undoneaggrtypes, naggregations, naggrvars, cutoff) );
5276 if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
5278 SCIP_CALL( SCIPaddClique(scip, consdata->vars, NULL, consdata->nvars, &infeasible, &nlocalbdchgs) );
5289 /* a two-variable set covering constraint x + y >= 1 yields the implication x == 0 -> y == 1 */
5307 /** perform multi-aggregation on variables resulting from a set-partitioning/-packing constraint */
5338 SCIPdebugMessage("aggregating %s = 1 - %s\n", SCIPvarGetName(vars[pos]), SCIPvarGetName(vars[nvars - pos - 1]));
5341 SCIP_CALL( SCIPaggregateVars(scip, vars[pos], vars[nvars - pos - 1], 1.0, 1.0, 1.0, infeasible, &redundant, aggregated) );
5365 SCIPdebugMessage("multi-aggregating binary variable <%s> (locks: [%d,%d]; to %d variables)\n", SCIPvarGetName(vars[pos]), SCIPvarGetNLocksDown(vars[pos]), SCIPvarGetNLocksUp(vars[pos]), nvars - 1);
5368 SCIP_CALL( SCIPmultiaggregateVar(scip, vars[pos], nvars - 1, tmpvars, scalars, 1.0, infeasible, aggregated) );
5382 /** determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and negated)
5385 * we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint or
5388 * 1. c1: x + y + z = 1, uplocks(x) = 1, downlocks(x) = 1 => x = 1 - y - z and change c1 to y + z <= 1
5390 * 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
5396 * 4. e1: x + y + z == 1 and e2: ~x + u + v (<= or ==) 1, uplocks(x) = (1 or 2), downlocks(x) = 2
5399 * we can also aggregate a variable in a set-packing constraint with only two variables when the uplocks are equal to
5404 * @todo might want to multi-aggregate variables even with more locks, when the fill in is still smaller or equal to
5478 if( (nuplocks == 1 && ndownlocks <= 1) || (nuplocks <= 1 && ndownlocks == 1) || (nuplocks <= 2 && ndownlocks <= 2 && SCIPvarGetNegatedVar(binvars[v]) != NULL) )
5489 SCIP_CALL( SCIPhashmapCreate(&vartoindex, SCIPblkmem(scip), SCIPcalcHashtableSize(5 * nposvars)) );
5510 /* determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and
5513 * we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint
5583 /* if the constraint was not merged and consists of a variable with its negation, the constraint is redundant */
5604 SCIPdebugMessage("empty set partition constraint <%s> led to infeasibility\n", SCIPconsGetName(cons));
5610 SCIPdebugMessage("fixing <%s> to 1 because this variable is the last variable in a set partition constraint <%s>\n", SCIPvarGetName(consdata->vars[0]), SCIPconsGetName(cons));
5630 if( !donotaggr && consdata->nvars == 2 && dualpresolvingenabled && (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
5638 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
5646 SCIPdebugMessage("dualpresolve, aggregating %s + %s = 1, in set-packing constraint %s\n", SCIPvarGetName(var), SCIPvarGetName(consdata->vars[1]), SCIPconsGetName(cons));
5649 SCIP_CALL( SCIPaggregateVars(scip, var, consdata->vars[1], 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
5669 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
5677 SCIPdebugMessage("dualpresolve, aggregating %s + %s = 1, in set-packing constraint %s\n", SCIPvarGetName(var), SCIPvarGetName(consdata->vars[0]), SCIPconsGetName(cons));
5680 SCIP_CALL( SCIPaggregateVars(scip, var, consdata->vars[0], 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
5701 SCIPdebugMessage("aggregating %s + %s = 1, in set-partition constraint %s\n", SCIPvarGetName(consdata->vars[0]), SCIPvarGetName(consdata->vars[1]), SCIPconsGetName(cons));
5704 SCIP_CALL( SCIPaggregateVars(scip, consdata->vars[0], consdata->vars[1], 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
5729 /* if the following condition does not hold, we have an unmerged constraint, and we might need to merge it first */
5740 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
5745 assert((SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED && nuplocks >= 0 && ndownlocks >= 1) || (nuplocks >= 1 && ndownlocks >= 0));
5747 if( dualpresolvingenabled && (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING && (nuplocks == 1 || ndownlocks == 1) && nuplocks + ndownlocks <= 2 )
5749 assert((SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED && nuplocks <= 1 && ndownlocks == 1) || (nuplocks == 1 && ndownlocks <= 1));
5776 SCIP_CALL( multiAggregateBinvar(scip, linearconshdlrexist, consdata->vars, consdata->nvars, v, &infeasible, &aggregated) );
5823 /* if the following assert fails, the constraint was not merged, or something really strange happened */
5835 /* if two variables in one constraint might be multi-aggregated, it might happen that this constraint was already removed */
5844 /* it might be that due to other multi-aggregations the constraint has fewer variables than when we
5851 /* if the following assert is raised, then the constraint is redundant and we do not need to aggregate
5867 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(negvar) == SCIP_VARSTATUS_NEGATED);
5891 SCIP_CALL( multiAggregateBinvar(scip, linearconshdlrexist, consdata->vars, consdata->nvars, v, &infeasible, &aggregated) );
5895 SCIP_CALL( multiAggregateBinvar(scip, linearconshdlrexist, aggrconsdata->vars, aggrconsdata->nvars, varindex, &infeasible, &aggregated) );
5904 SCIP_CALL( multiAggregateBinvar(scip, linearconshdlrexist, aggrconsdata->vars, aggrconsdata->nvars, varindex, &infeasible, &aggregated) );
5908 SCIP_CALL( multiAggregateBinvar(scip, linearconshdlrexist, consdata->vars, consdata->nvars, v, &infeasible, &aggregated) );
5923 else if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && nuplocks == 1 && ndownlocks == 1 )
5928 SCIP_CALL( multiAggregateBinvar(scip, linearconshdlrexist, consdata->vars, consdata->nvars, v, &infeasible, &aggregated) );
5946 /* if we have two times the same variable in a set-partitioning constraint, so we cannot aggregate this */
5953 assert(SCIPconsIsDeleted(usefulconss[considxs[image - 1]]) || chgtype[considxs[image - 1]] || (0 <= posincons[image - 1] && posincons[image - 1] < SCIPconsGetData(usefulconss[considxs[image - 1]])->nvars));
5986 /* if we have two times the same variable in a set-partitioning constraint, so we cannot aggregate this */
5999 /* if the following assert fails, the constraint was not merged, or something really strange happened */
6011 /* if two variables in one constraint might be multi-aggregated, it might happen that this constraint was
6020 /* must not multi-aggregate variables that are locked more then twice by all setppc constraints */
6022 (SCIP_SETPPCTYPE)aggrconsdata->setppctype == SCIP_SETPPCTYPE_PACKING && nuplocks + ndownlocks > 2 )
6028 /* we already remove a variable before, so our positioning information might be wrong, so we need to walk
6049 SCIP_CALL( multiAggregateBinvar(scip, linearconshdlrexist, consdata->vars, consdata->nvars, v, &infeasible, &aggregated) );
6060 /* @note it might have happened that we have a variable at hand which exists actually in a set-packing
6061 * constraint and due to some other aggregation we increased the number of locks and reached this
6071 SCIPdebugMessage("multi-aggregating in two set-partitioning or one set-partitioning and -packing constraint\n");
6074 SCIP_CALL( multiAggregateBinvar(scip, linearconshdlrexist, aggrconsdata->vars, aggrconsdata->nvars, varindex, &infeasible, &aggregated) );
6092 if( ((nuplocks == 1 && ndownlocks == 0) || (nuplocks == 0 && ndownlocks == 1)) && (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
6097 else if( nuplocks == 1 && ndownlocks == 1 && (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING )
6102 SCIPdebugMessage("changing constraint <%s> from set-partitioning to set-packing, due to multi-aggregation\n", SCIPconsGetName(cons));
6113 SCIPdebugMessage("1: deleting redundant constraint <%s>, due to multi-aggregation\n", SCIPconsGetName(usefulconss[deleteconsindex]));
6121 SCIPdebugMessage("2: deleting redundant constraint <%s>, due to multi-aggregation\n", SCIPconsGetName(cons));
6148 /** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
6195 /* get constraint from current hash table with same variables as cons0 and with coefficients either equal or negated
6207 /* constraint found: create a new constraint with same coefficients and best left and right hand side;
6225 if( consdata1->setppctype != SCIP_SETPPCTYPE_PARTITIONING && consdata0->setppctype != consdata1->setppctype ) /*lint !e641*/
6232 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
6342 || SCIPvarGetIndex(consdata1->vars[v1]) > SCIPvarGetIndex(consdata0->vars[consdata0->nvars-1]));
6409 SCIPerrorMessage("invalid setppc type <%d> of constraint <%s>\n", consdata1->setppctype, SCIPconsGetName(cons1));
6432 SCIPerrorMessage("invalid setppc type <%d> of constraint <%s>\n", consdata1->setppctype, SCIPconsGetName(cons1));
6459 SCIPerrorMessage("invalid setppc type <%d> of constraint <%s>\n", consdata1->setppctype, SCIPconsGetName(cons1));
6465 SCIPerrorMessage("invalid setppc type <%d> of constraint <%s>\n", consdata0->setppctype, SCIPconsGetName(cons0));
6518 for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff) && SCIPconsIsActive(cons0); ++c )
6611 /* one is a covering, the other one a packing constraint: replace them by a single partitioning constraint */
6612 assert((consdata0->setppctype == SCIP_SETPPCTYPE_COVERING && consdata1->setppctype == SCIP_SETPPCTYPE_PACKING)
6613 || (consdata1->setppctype == SCIP_SETPPCTYPE_COVERING && consdata0->setppctype == SCIP_SETPPCTYPE_PACKING)); /*lint !e641*/
6626 SCIPdebugMessage("setppc constraint <%s> is contained in <%s>\n", SCIPconsGetName(cons0), SCIPconsGetName(cons1));
6629 SCIP_CALL( processContainedCons(scip, cons0, cons1, cutoff, nfixedvars, ndelconss, nchgsides) );
6634 SCIPdebugMessage("setppc constraint <%s> is contained in <%s>\n", SCIPconsGetName(cons1), SCIPconsGetName(cons0));
6637 SCIP_CALL( processContainedCons(scip, cons1, cons0, cutoff, nfixedvars, ndelconss, nchgsides) );
6701 SCIP_SETPPCTYPE setppctype, /**< type of constraint: set partitioning, packing, or covering constraint */
6720 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
6722 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
6754 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
6788 SCIP_SETPPCTYPE setppctype, /**< type of constraint: set partitioning, packing, or covering constraint */
6807 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
6809 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
6838 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
6852 /* check, if linear constraint can be upgraded to set partitioning, packing, or covering constraint
6853 * - all set partitioning / packing / covering constraints consist only of binary variables with a
6860 * - a set partitioning constraint has left hand side of +1.0, and right hand side of +1.0 : x(S) == 1.0
6862 * - a set packing constraint has left hand side of -infinity, and right hand side of +1.0 : x(S) <= 1.0
6864 * - a set covering constraint has left hand side of +1.0, and right hand side of +infinity: x(S) >= 1.0
6867 if( nposbin + nnegbin + nposimplbin + nnegimplbin == nvars && ncoeffspone + ncoeffsnone == nvars )
6871 if( SCIPisEQ(scip, lhs, rhs) && (SCIPisEQ(scip, lhs, 1.0 - ncoeffsnone) || SCIPisEQ(scip, lhs, ncoeffspone - 1.0)) )
6873 SCIPdebugMessage("upgrading constraint <%s> to set partitioning constraint\n", SCIPconsGetName(cons));
6875 /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
6878 /* create the set partitioning constraint (an automatically upgraded constraint is always unmodifiable) */
6880 SCIP_CALL( createNormalizedSetppc(scip, upgdcons, SCIPconsGetName(cons), nvars, vars, vals, mult,
6890 SCIPdebugMessage("upgrading constraint <%s> to set packing constraint\n", SCIPconsGetName(cons));
6892 /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
6895 /* create the set packing constraint (an automatically upgraded constraint is always unmodifiable) */
6897 SCIP_CALL( createNormalizedSetppc(scip, upgdcons, SCIPconsGetName(cons), nvars, vars, vals, mult,
6907 SCIPdebugMessage("upgrading constraint <%s> to set covering constraint\n", SCIPconsGetName(cons));
6909 /* check, if we have to multiply with -1 (negate the positive vars) or with +1 (negate the negative vars) */
6912 /* create the set covering constraint (an automatically upgraded constraint is always unmodifiable) */
6914 SCIP_CALL( createNormalizedSetppc(scip, upgdcons, SCIPconsGetName(cons), nvars, vars, vals, mult,
6946 SCIPdebugMessage("try to upgrade quadratic constraint <%s> to setpacking constraint ...\n", SCIPconsGetName(cons));
6967 if( SCIPvarGetType(term->var1) != SCIP_VARTYPE_BINARY || SCIPvarGetType(term->var2) != SCIP_VARTYPE_BINARY )
6979 coefx = quadvarterms[0].lincoef + quadvarterms[0].sqrcoef; /* for binary variables, we can treat sqr coef as lin coef */
6980 coefy = quadvarterms[1].lincoef + quadvarterms[0].sqrcoef; /* for binary variables, we can treat sqr coef as lin coef */
7028 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
7057 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
7106 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
7127 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
7173 /* if constraint belongs to transformed problem space, drop bound change events on variables */
7217 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
7220 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
7235 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
7267 SCIPdebugMessage("separating %d/%d set partitioning / packing / covering constraints\n", nusefulconss, nconss);
7310 SCIPdebugMessage("separating %d/%d set partitioning / packing / covering constraints\n", nusefulconss, nconss);
7341 /** if fractional variables exist, chooses a set S of them and branches on (i) x(S) == 0, and (ii) x(S) >= 1 */
7346 SCIP_RESULT* result /**< pointer to store the result SCIP_BRANCHED, if branching was applied */
7364 /**@todo use a better set partitioning / packing / covering branching on LP solution (use SOS branching) */
7386 /* sort fractional variables by number of uses in enabled set partitioning / packing / covering constraints */
7407 /* if none of the fractional variables is member of a set partitioning / packing / covering constraint,
7418 /* select the first variables from the sorted candidate list, until MAXBRANCHWEIGHT is reached;
7433 /* @todo instead of taking the minimum into account try other variants like the maximum and the average */
7434 /* calculate priorities and estimates by adding up/taking the minimum of all single priorities/estimates */
7469 SCIPdebugMessage("fixing variable <%s> to 1.0 in right child node\n", SCIPvarGetName(sortcands[0]));
7478 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "BSB%"SCIP_LONGINT_FORMAT, SCIPgetNTotalNodes(scip));
7489 SCIPdebugMessage("binary set branching: nselcands=%d/%d, weight(S)=%g, A={", nselcands, nlpcands, branchweight);
7491 SCIPdebugPrintf(" %s[%g]", SCIPvarGetName(sortcands[i]), SCIPgetSolVal(scip, NULL, sortcands[i]));
7513 SCIP_RESULT* result /**< pointer to store the result SCIP_BRANCHED, if branching was applied */
7530 /**@todo use a better set partitioning / packing / covering branching on pseudo solution (use SOS branching) */
7558 /* sort unfixed variables by number of uses in enabled set partitioning / packing / covering constraints */
7583 /* if none of the unfixed variables is member of a set partitioning / packing / covering constraint,
7594 /* @todo instead of taking the minimum into account try other variants like the maximum and the average */
7612 SCIP_CALL( SCIPcreateChild(scip, &node, (SCIP_Real)nbranchcands, MIN(minestzero, estone[i])) );
7662 SCIPdebugMessage("LP enforcing %d set partitioning / packing / covering constraints\n", nconss);
7721 /* if the solution is infeasible anyway due to objective value, skip the constraint processing and branch directly */
7731 SCIPdebugMessage("pseudo enforcing %d set partitioning / packing / covering constraints\n", nconss);
7757 /* at least one constraint is violated by pseudo solution and we didn't find a better way to resolve this:
7810 SCIPinfoMessage(scip, NULL, "violation: the right hand side is violated by by %.15g\n", ABS(sum - 1));
7838 SCIPdebugMessage("propagating %d/%d set partitioning / packing / covering constraints\n", nmarkedconss, nconss);
7848 /* do not propagate constraints with multi-aggregated variables, which should only happen in probing mode,
7905 conshdlrdata->enablecliquelifting = conshdlrdata->enablecliquelifting || conshdlrdata->updatedsetppctype
7906 || conshdlrdata->noldfixedvars != SCIPgetNFixedVars(scip) || conshdlrdata->noldimpls != SCIPgetNImplications(scip)
7931 /*SCIPdebugMessage("presolving set partitioning / packing / covering constraint <%s>\n", SCIPconsGetName(cons));*/
7934 if( consdata->nfixedzeros > 0 || nnewaggrvars > 0 || nnewaddconss > 0 || *naggrvars > oldnaggrvars || (nrounds == 0 && SCIPgetNRuns(scip) > 1) )
7983 /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
7986 SCIP_CALL( presolvePropagateCons(scip, cons, TRUE, NULL, NULL, NULL, NULL, nfixedvars, naggrvars, ndelconss, &cutoff) );
8037 if( oldnfixedvars < *nfixedvars || oldnaggrvars < *naggrvars || oldndelconss < *ndelconss || oldnchgcoefs < *nchgcoefs )
8042 /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
8043 SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, ndelconss, nchgsides) );
8048 /* determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and
8051 if( nconss > 1 && ((conshdlrdata->nsetpart > 0 && !SCIPdoNotMultaggr(scip) && conshdlrdata->conshdlrlinear != NULL) || (conshdlrdata->dualpresolving && conshdlrdata->nsetpart < nconss && !SCIPdoNotAggr(scip))) )
8053 SCIP_CALL( removeDoubleAndSingletonsAndPerformDualpresolve(scip, conss, nconss, conshdlrdata->dualpresolving, conshdlrdata->conshdlrlinear != NULL, nfixedvars, naggrvars, ndelconss, nchgcoefs, nchgsides, &cutoff) );
8060 else if( oldnfixedvars < *nfixedvars || oldnaggrvars < *naggrvars || oldndelconss < *ndelconss )
8067 if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars && *ndelconss == oldndelconss &&
8071 SCIP_CALL( addCliques(scip, conss, nconss, firstclique, lastclique, naddconss, ndelconss, nchgbds, &cutoff) );
8083 SCIP_CALL( preprocessCliques(scip, conshdlrdata, conss, nconss, nrounds, &firstchange, &firstclique,
8092 else if( oldnfixedvars < *nfixedvars || oldnaggrvars < *naggrvars || oldndelconss < *ndelconss || oldnchgcoefs < *nchgcoefs )
8118 npaircomparisons += (SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange);
8120 SCIP_CALL( removeRedundantConstraints(scip, conss, firstchange, c, &cutoff, nfixedvars, ndelconss, nchgsides) );
8129 if( (*ndelconss - oldndelconss + *nfixedvars - oldnfixedvars) / ((SCIP_Real)npaircomparisons) < MINGAINPERNMINCOMPARISONS )
8142 SCIP_CALL( addCliques(scip, conss, nconss, MIN(firstclique, nconss), MIN(lastclique, nconss), naddconss, ndelconss,
8175 SCIPdebugMessage("conflict resolving method of set partitioning / packing / covering constraint handler\n");
8185 /* the inference constraint is a set partitioning or covering constraint with the inference variable infered to 1.0:
8211 /* the inference constraint is a set partitioning or packing constraint with the inference variable infered to 0.0:
8289 SCIPdebugMessage("activation information for set partitioning / packing / covering constraint <%s>\n",
8292 /* we only might add the constraint to the propagation list, when we are not activating it in probing mode */
8321 SCIPdebugMessage("deactivation information for set partitioning / packing / covering constraint <%s>\n",
8408 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode, global, valid) );
8451 SCIP_CALL( SCIPparseVarsLinearsum(scip, str, vars, coefs, &nvars, coefssize, &requsize, &endptr, success) );
8460 SCIP_CALL( SCIPparseVarsLinearsum(scip, str, vars, coefs, &nvars, coefssize, &requsize, &endptr, success) );
8461 assert(!*success || requsize <= coefssize); /* if successful, then should have had enough space now */
8485 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
8489 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
8493 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
8530 /** constraint method of constraint handler which returns the number of variables (if possible) */
8561 /*debugMessage("Exec method of bound change event handler for set partitioning / packing / covering constraints\n");*/
8599 /* one variable was changed to a negated or aggregated variable, so maybe we can merge again */
8600 if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_FIXED && SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 )
8620 if( (eventtype & SCIP_EVENTTYPE_BOUNDTIGHTENED) && (consdata->nfixedones >= 1 || consdata->nfixedzeros >= consdata->nvars - 1) )
8658 /* for two (binary) variables we will create a set packing constraint and add the clique information of the conflict is global */
8692 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cf%d_%"SCIP_LONGINT_FORMAT, SCIPgetNRuns(scip), SCIPgetNConflictConssApplied(scip));
8705 SCIPdebugMessage("new clique of conflict constraint %s led to %d fixings\n", consname, ncliquebdchgs);
8744 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cf%d_%"SCIP_LONGINT_FORMAT, SCIPgetNRuns(scip), SCIPgetNConflictConssApplied(scip));
8766 /** creates the handler for set partitioning / packing / covering constraints and includes it in SCIP */
8780 SCIP_CALL( SCIPincludeConflicthdlrBasic(scip, NULL, CONFLICTHDLR_NAME, CONFLICTHDLR_DESC, CONFLICTHDLR_PRIORITY,
8809 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSetppc, CONSHDLR_MAXPREROUNDS, CONSHDLR_DELAYPRESOL) );
8811 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSetppc, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
8814 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSetppc, consSepasolSetppc, CONSHDLR_SEPAFREQ,
8822 /* include the linear constraint to setppc constraint upgrade in the linear constraint handler */
8823 SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdSetppc, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) );
8828 SCIP_CALL( SCIPincludeQuadconsUpgrade(scip, quadraticUpgdSetppc, QUADCONSUPGD_PRIORITY, TRUE, CONSHDLR_NAME) );
8851 " should we try to lift variables into other clique constraints, fix variables, aggregate them, and also shrink the amount of variables in clique constraints",
8855 "should we try to generate extra cliques out of all binary variables to maybe fasten redundant constraint detection",
8859 "should we try to shrink the number of variables in a clique constraints, by replacing more than one variable by only one",
8867 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
8893 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
8895 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
8901 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode);
8907 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
8925 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
8951 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
8953 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
8959 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode);
8965 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
8984 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
9010 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
9012 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
9018 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode);
9024 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
9126 /** gets the dual solution of the set partitioning / packing / covering constraint in the current LP */
9150 /** gets the dual Farkas value of the set partitioning / packing / covering constraint in the current infeasible LP */
|