prop_symmetry.c
Go to the documentation of this file.
25 * - It allows to compute symmetries of the problem and to store this information in adequate form. The symmetry
38 * - We treat implicit integer variables as if they were continuous/real variables. The reason is that there is currently
39 * no distinction between implicit integer and implicit binary. Moreover, currently implicit integer variables hurt
40 * our code more than continuous/real variables (we basically do not handle integral variables at all).
41 * - We do not copy symmetry information, since it is not clear how this information transfers. Moreover, copying
42 * symmetry might inhibit heuristics. But note that solving a sub-SCIP might then happen without symmetry information!
49 * - The code automatically detects whether symmetry substructures like symresacks or orbitopes are present and possibly
52 * - We try to compute symmetry as late as possible and then add constraints based on this information.
53 * - Currently, we only allocate memory for pointers to symresack constraints for group generators. If further
62 * The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the
63 * variables globally fixed or branched to 1. Then one can fix all variables in an orbit to 0 or 1 if one of the other
64 * variables in the orbit is fixed to 0 or 1, respectively. Different from Margot, the subgroup is obtained by filtering
67 * @pre All variable fixings applied by other components are required to be strict, i.e., if one variable is fixed to
68 * a certain value v, all other variables in the same variable orbit can be fixed to v as well, c.f.@n
69 * F. Margot: Symmetry in integer linear programming. 50 Years of Integer Programming, 647-686, Springer 2010.
72 * (x,y) \in \{0,1\}^{2 + n}\} \f$. Since \f$x_1\f$ and \f$x_2\f$ are independent from the remaining problem, the
73 * setppc constraint handler may fix \f$(x_1,x_2) = (1,0)\f$. However, since both variables are symmetric, this setting
74 * is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would
75 * declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different
76 * values). To avoid this situation, we have to assume that all non-strict settings fix variables globally, i.e., we
77 * can take care of it by taking variables into account that have been globally fixed to 1. In fact, it suffices to
78 * consider one kind of global fixings since stabilizing one kind prevents an orbit to contain variables that have
81 * @pre All non-strict settings are global settings, since otherwise, we cannot (efficiently) take care of them.
83 * @pre No non-strict setting algorithm is interrupted early (e.g., by a time or iteration limit), since this may lead to
84 * wrong decisions by orbital fixing as well. For example, if cons_setppc in the above toy example starts by fixing
85 * \f$x_2 = 0\f$ and is interrupted afterwards, orbital fixing detects that the orbit \f$\{x_1, x_2\}\f$ contains
86 * one variable that is fixed to 0, and thus, it fixes \f$x_1\f$ to 0 as well. Thus, after these reductions, every
87 * feasible solution has objective 0 which is not optimal. This situation would not occur if the non-strict setting is
88 * complete, because then \f$x_1\f$ is globally fixed to 1, and thus, is stabilized in orbital fixing.
90 * Note that orbital fixing might lead to wrong results if it is called in repropagation of a node, because the path
91 * from the node to the root might have been changed. Thus, the stabilizers of global 1-fixing and 1-branchings of the
92 * initial propagation and repropagation might differ, which may cause conflicts. For this reason, orbital fixing cannot
95 * @note If, besides orbital fixing, also symmetry handling constraints shall be added, orbital fixing is only applied
102 * D. Salvagnin: Symmetry Breaking Inequalities from the Schreier-Sims table. CPAIOR 2018 Proceedings, 521-529, 2018.
104 * These inequalities are computed as follows. Throughout these procedure a set of so-called leaders is maintained.
105 * Initially the set of leaders is empty. In a first step, select a variable \f$x_i\f$ and compute its orbit w.r.t.
106 * the symmetry group of the mixed-integer program. For each variable \f$x_j\f$ in the orbit of \f$x_i\f$, the
107 * inequality \f$x_i \geq x_j\f$ is a valid symmetry handling inequality, which can be added to the mixed-integer
108 * program. We call \f$x_i\f$ the leader of this inequality. Add the leader \f$x_i\f$ to the set of leaders and
109 * compute the pointwise stabilizer of the leader set. In the next step, select a new variable, compute its orbit
110 * w.r.t. the stabilizer group of the leaders, add the inequalities based on this orbit, and add the new leader
111 * to the set of leaders. This procedure is iterated until the pointwise stabilizer group of the leaders has become
122 * @todo Order rows of orbitopes (in particular packing/partitioning) w.r.t. cliques in conflict graph.
127 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
158 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
160 #define PROP_PRESOL_PRIORITY -10000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers) */
161 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
162 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
166 #define DEFAULT_MAXGENERATORS 1500 /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
167 #define DEFAULT_CHECKSYMMETRIES FALSE /**< Should all symmetries be checked after computation? */
168 #define DEFAULT_DISPLAYNORBITVARS FALSE /**< Should the number of variables affected by some symmetry be displayed? */
169 #define DEFAULT_USECOLUMNSPARSITY FALSE /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
171 #define DEFAULT_COMPRESSSYMMETRIES TRUE /**< Should non-affected variables be removed from permutation to save memory? */
172 #define DEFAULT_COMPRESSTHRESHOLD 0.5 /**< Compression is used if percentage of moved vars is at most the threshold. */
173 #define DEFAULT_SYMFIXNONBINARYVARS FALSE /**< Whether all non-binary variables shall be not affected by symmetries if OF is active? */
177 #define DEFAULT_CONSSADDLP TRUE /**< Should the symmetry breaking constraints be added to the LP? */
179 #define DEFAULT_DETECTORBITOPES TRUE /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
180 #define DEFAULT_DETECTSUBGROUPS TRUE /**< Should we try to detect orbitopes in subgroups of the symmetry group? */
181 #define DEFAULT_ADDWEAKSBCS TRUE /**< Should we add weak SBCs for enclosing orbit of symmetric subgroups? */
182 #define DEFAULT_ADDSTRONGSBCS FALSE /**< Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used? */
183 #define DEFAULT_ADDCONSSTIMING 2 /**< timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) */
184 #define DEFAULT_MAXNCONSSSUBGROUP 500000 /**< Maximum number of constraints up to which subgroup structures are detected */
185 #define DEFAULT_USEDYNAMICPROP TRUE /**< whether dynamic propagation should be used for full orbitopes */
186 #define DEFAULT_PREFERLESSROWS TRUE /**< Shall orbitopes with less rows be preferred in detection? */
189 #define DEFAULT_OFSYMCOMPTIMING 2 /**< timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call) */
191 #define DEFAULT_RECOMPUTERESTART 0 /**< Recompute symmetries after a restart has occurred? (0 = never, 1 = always, 2 = if OF found reduction) */
194 #define DEFAULT_SSTTIEBREAKRULE 1 /**< index of tie break rule for selecting orbit for Schreier Sims constraints? */
195 #define DEFAULT_SSTLEADERRULE 0 /**< index of rule for selecting leader variables for Schreier Sims constraints? */
196 #define DEFAULT_SSTLEADERVARTYPE 14 /**< bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);
198 #define DEFAULT_ADDCONFLICTCUTS TRUE /**< Should Schreier Sims constraints be added if we use a conflict based rule? */
200 #define DEFAULT_SSTMIXEDCOMPONENTS TRUE /**< Should Schreier Sims constraints be added if a symmetry component contains variables of different types? */
204 #define EVENTHDLR_SYMMETRY_DESC "filter global variable fixing event handler for orbital fixing"
210 #define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING /**< output of the statistics table is only printed from this stage onwards */
214 #define MAXGENNUMERATOR 64000000 /**< determine maximal number of generators by dividing this number by the number of variables */
215 #define SCIP_SPECIALVAL 1.12345678912345e+19 /**< special floating point value for handling zeros in bound disjunctions */
216 #define COMPRESSNVARSLB 25000 /**< lower bound on the number of variables above which compression could be performed */
242 int** permstrans; /**< pointer to store transposed permutation generators as (npermvars x nperms) matrix */
247 int nmovedimplintpermvars; /**< number of implicitly integer variables moved by any permutation */
249 SCIP_Shortbool* nonbinpermvarcaptured; /**< array to store which non-binary variables have been captured
260 unsigned* componentblocked; /**< array to store which symmetry methods have been applied to a component using
269 int maxgenerators; /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
271 SCIP_Bool displaynorbitvars; /**< Whether the number of variables in non-trivial orbits shall be computed */
272 SCIP_Bool compresssymmetries; /**< Should non-affected variables be removed from permutation to save memory? */
273 SCIP_Real compressthreshold; /**< Compression is used if percentage of moved vars is at most the threshold. */
277 SCIP_Bool usecolumnsparsity; /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
279 SCIP_Bool symfixnonbinaryvars; /**< Whether all non-binary variables shall be not affected by symmetries if OF is active? */
287 int addconsstiming; /**< timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) */
294 SCIP_Bool detectorbitopes; /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
295 SCIP_Bool detectsubgroups; /**< Should we try to detect orbitopes in subgroups of the symmetry group? */
296 SCIP_Bool addweaksbcs; /**< Should we add weak SBCs for enclosing orbit of symmetric subgroups? */
297 SCIP_Bool addstrongsbcs; /**< Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used? */
301 int maxnconsssubgroup; /**< maximum number of constraints up to which subgroup structures are detected */
317 int recomputerestart; /**< Recompute symmetries after a restart has occured? (0 = never, 1 = always, 2 = if OF found reduction) */
318 int ofsymcomptiming; /**< timing of orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call) */
323 SCIP_Bool offoundreduction; /**< whether orbital fixing has found a reduction since the last time computing symmetries */
337 SCIP_Bool addconflictcuts; /**< Should Schreier Sims constraints be added if we use a conflict based rule? */
339 SCIP_Bool sstmixedcomponents; /**< Should Schreier Sims constraints be added if a symmetry component contains variables of different types? */
360 /** exec the event handler for handling global variable bound changes (necessary for orbital fixing)
362 * Global variable fixings during the solving process might arise because parts of the tree are pruned or if certain
363 * preprocessing steps are performed that do not correspond to strict setting algorithms. Since these fixings might be
364 * caused by or be in conflict with orbital fixing, they can be in conflict with the symmetry handling decisions of
365 * orbital fixing in the part of the tree that is not pruned. Thus, we have to take global fixings into account when
370 {
446 {
459 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 0 :%11d\n", tabledata->propdata->nfixedzero);
460 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 1 :%11d\n", tabledata->propdata->nfixedone);
470 {
495 * Compare the types of two variables according to objective, lower and upper bound, variable type, and column sparsity.
499 {
539 return SCIPhashFour(SCIPrealHashCode(k->obj), SCIPrealHashCode(k->lb), SCIPrealHashCode((double) k->nconss), SCIPrealHashCode(k->ub));
544 {
548 };
553 {
556 };
570 {
604 {
631 {
748 if ( SCIPgetNRuns(scip) == propdata->lastrestart || propdata->lastrestart == 0 || SCIPgetNRuns(scip) == 1 )
817 /* If symmetry is computed before presolving, it might happen that some variables are turned into binary
818 * variables, for which no event has been catched. Since there currently is no way of checking whether a var
822 SCIP_CALL( SCIPdropVarEvent(scip, propdata->permvars[i], SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED,
848 SCIPfreeBlockMemoryArray(scip, &propdata->nonbinpermvarcaptured, propdata->npermvars - propdata->nbinpermvars);
980 /* if orbital fixing runs exclusively, propdata->perms was already freed in determineSymmetry() */
1115 (SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT) )
1121 /** Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.
1129 SCIP_Real** scalars, /**< pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
1148 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
1155 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
1176 SCIP_Real* linvals, /**< array of linear coefficients values (or NULL if all linear coefficient values are 1) */
1239 /* check whether we have to resize; note that we have to add 2 * nvars since two inequalities may be added */
1246 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matidx), matrixdata->nmaxmatcoef, newsize) );
1247 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matrhsidx), matrixdata->nmaxmatcoef, newsize) );
1248 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matvaridx), matrixdata->nmaxmatcoef, newsize) );
1249 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matcoef), matrixdata->nmaxmatcoef, newsize) );
1250 SCIPdebugMsg(scip, "Resized matrix coefficients from %d to %d.\n", matrixdata->nmaxmatcoef, newsize);
1282 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1295 /* add negative of equation; increases chance to detect symmetry, but might increase time to compute symmetry. */
1301 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1343 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1372 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1395 * We need the matrix and rhs in the original order in order to speed up the comparison process. The matrix is needed
1434 /* create hashmaps for variable permutation and constraints in non-linear part array for occuring variables */
1514 if ( matrixdata->rhssense[r1] == matrixdata->rhssense[r2] && SCIPisEQ(scip, matrixdata->rhscoef[r1], matrixdata->rhscoef[r2]) )
1522 while ( j < matrixdata->nmatcoef && matrixdata->matrhsidx[j] == r2 && SCIPisEQ(scip, permrow[matrixdata->matvaridx[j]], matrixdata->matcoef[j] ) )
1610 SCIP_CALL( SCIPsimplifyExpr(scip, permutedexpr, &permutedexpr, &success, &infeasible, NULL, NULL) );
1701 return propdata->conshdlr_nonlinear != NULL && SCIPconshdlrGetNActiveConss(propdata->conshdlr_nonlinear) > 0;
1716 int* nmovedvars, /**< pointer to store number of vars affected by symmetry (if usecompression) or NULL */
1717 SCIP_Bool* binvaraffected, /**< pointer to store whether a binary variable is affected by symmetry */
1719 SCIP_Real compressthreshold, /**< if percentage of moved vars is at most threshold, compression is done */
1816 /* detect whether binary variable is affected by symmetry and count number of binary permvars */
1840 SCIP_Bool compresssymmetries, /**< Should non-affected variables be removed from permutation to save memory? */
1841 SCIP_Real compressthreshold, /**< Compression is used if percentage of moved vars is at most the threshold. */
1846 SCIP_Bool usecolumnsparsity, /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
1852 int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1857 SCIP_Bool* binvaraffected, /**< pointer to store wether a binary variable is affected by symmetry */
1954 SCIPdebugMsg(scip, "Detecting %ssymmetry on %d variables and %d constraints.\n", local ? "local " : "", nvars, nactiveconss);
1957 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &vars, SCIPgetVars(scip), nvars) ); /*lint !e666*/
1962 /* use a staggered scheme for allocating space for non-zeros of constraint matrix since it can become large */
2049 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons),
2062 /* SCIPgetBinVarsLinking returns the number of binary variables, but we also need the integer variable */
2072 /* set final entry of vars and vals to the linking variable and its coefficient, respectively */
2089 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_EQUATION, &matrixdata, nconssforvar) );
2092 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, -SCIPinfinity(scip), 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2095 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2128 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nconsvars, (SCIP_Real) SCIPgetRhsXor(scip, cons),
2129 (SCIP_Real) SCIPgetRhsXor(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_XOR, &matrixdata, nconssforvar) );
2183 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLogicor(scip, cons), 0, SCIPgetNVarsLogicor(scip, cons),
2184 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2198 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsKnapsack(scip, cons), consvals, nconsvars, -SCIPinfinity(scip),
2199 (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2209 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
2210 SCIPgetRhsVarbound(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2224 * is of type 1. If the bound disjunction has length two and both disjunctions contain the same variable,
2225 * we say the bound disjunction is of type 2. Further bound disjunctions are possible, but can currently
2236 * Note that problems arise if \fb'_i = 0\f for some variable \fx_i\f, because its coefficient in the
2274 /* stop, we cannot handle bounddisjunctions with more than two variables that contain a variable twice */
2280 " Deactivated symmetry handling methods, there exist constraints that cannot be handled by symmetry methods.\n");
2305 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nbounddisjvars, 0.0, 0.0,
2335 for (expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
2339 /* for variables, we check whether they appear nonlinearly and store the result in the resp. array */
2343 (*isnonlinvar)[SCIPvarGetProbindex(SCIPgetVarExprVar(expr))] = (SCIPexpriterGetParentDFS(it) != rootexpr || !SCIPisExprSum(scip, rootexpr));
2370 SCIPerrorMessage("Cannot determine symmetries for constraint <%s> of constraint handler <%s>.\n",
2413 SCIP_CALL( SCIPhashtableCreate(&vartypemap, SCIPblkmem(scip), 5 * nvars, SYMhashGetKeyVartype, SYMhashKeyEQVartype, SYMhashKeyValVartype, (void*) scip) );
2433 if ( SymmetryFixVar(fixedtype, var) || (nnlconss > 0 && SCIPhashsetExists(auxvars, (void*) var)) )
2437 SCIPdebugMsg(scip, "Detected variable <%s> of fixed type %d - color %d.\n", SCIPvarGetName(var), SCIPvarGetType(var), matrixdata.nuniquevars - 1);
2468 SCIPdebugMsg(scip, "Detected variable <%s> of new type (probindex: %d, obj: %g, lb: %g, ub: %g, type: %d) - color %d.\n",
2469 SCIPvarGetName(var), SCIPvarGetProbindex(var), vt->obj, vt->lb, vt->ub, vt->type, matrixdata.nuniquevars - 1);
2532 SCIPdebugMsg(scip, "Detected new matrix entry type %f - color: %d\n.", val, matrixdata.nuniquemat);
2566 SCIPdebugMsg(scip, "Detected new rhs type %f, type: %u - color: %d\n", val, sense, matrixdata.nuniquerhs);
2581 SCIPdebugMsg(scip, "Number of detected different variables: %d (total: %d).\n", matrixdata.nuniquevars, nvars);
2582 SCIPdebugMsg(scip, "Number of detected different rhs types: %d (total: %d).\n", matrixdata.nuniquerhs, matrixdata.nrhscoef);
2583 SCIPdebugMsg(scip, "Number of detected different matrix coefficients: %d (total: %d).\n", matrixdata.nuniquemat, matrixdata.nmatcoef);
2585 /* do not compute symmetry if all variables are non-equivalent (unique) or if all matrix coefficients are different */
2586 if ( matrixdata.nuniquevars < nvars && (matrixdata.nuniquemat == 0 || matrixdata.nuniquemat < matrixdata.nmatcoef) )
2589 SCIP_CALL( SYMcomputeSymmetryGenerators(scip, maxgenerators, &matrixdata, &exprdata, nperms, nmaxperms,
2594 if ( checksymmetries && SCIPgetStage(scip) > SCIP_STAGE_INITPRESOLVE && ! SCIPisStopped(scip) )
2601 SCIP_CALL( setSymmetryData(scip, vars, nvars, nbinvars, permvars, npermvars, nbinpermvars, *perms, *nperms,
2655 SYM_SPEC symspecrequire, /**< symmetry specification for which we need to compute symmetries */
2656 SYM_SPEC symspecrequirefixed /**< symmetry specification of variables which must be fixed by symmetries */
2707 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2733 /* do not compute symmetry if there are no binary variables and non-binary variables cannot be handled, but only binary variables would be used */
2756 /* count implicit integer variables as real variables, since we cannot currently handle integral variables well */
2764 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2801 " (%.1fs) symmetry computation skipped: there exist constraints that cannot be handled by symmetry methods.\n",
2822 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2840 SCIP_CALL( computeSymmetryGroup(scip, propdata->doubleequations, propdata->compresssymmetries, propdata->compressthreshold,
2841 maxgenerators, symspecrequirefixed, FALSE, propdata->checksymmetries, propdata->usecolumnsparsity, propdata->conshdlr_nonlinear,
2842 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvars, &propdata->nperms, &propdata->nmaxperms,
2856 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) could not compute symmetry\n", SCIPgetSolvingTime(scip));
2869 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry present\n", SCIPgetSolvingTime(scip));
2879 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) symmetry computation finished: %d generators found (max: ",
2889 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", log10 of symmetry group size: %.1f", propdata->log10groupsize);
2895 SCIP_CALL( SCIPdetermineNVarsAffectedSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2898 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", number of affected variables: %d)\n", propdata->nmovedvars);
2902 /* exit if no binary variables are affected by symmetry and we cannot handle non-binary symmetries */
2905 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry on binary variables present.\n", SCIPgetSolvingTime(scip));
2911 ! ( ISSSTINTACTIVE(propdata->sstleadervartype) || ISSSTIMPLINTACTIVE(propdata->sstleadervartype)
2916 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) -> no handable symmetry found, free symmetry data.\n",
2935 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation started\n", SCIPgetSolvingTime(scip));
2938 /* we only need the components for orbital fixing, orbitope and subgroup detection, and Schreier Sims constraints */
2942 SCIP_CALL( SCIPcomputeComponentsSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2948 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation finished\n", SCIPgetSolvingTime(scip));
3014 /* Only catch binary variables, since integer variables should be fixed pointwise; implicit integer variables
3019 SCIP_CALL( SCIPcatchVarEvent(scip, propdata->permvars[v], SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED,
3090 /* if Schreier-Sims constraints are enabled, also capture symmetric variables and forbid multi aggregation of handable vars */
3145 /** Checks whether given set of 2-cycle permutations forms an orbitope and if so, builds the variable index matrix.
3147 * If @p activevars == NULL, then the function assumes all permutations of the component are active and therefore all
3150 * We need to keep track of the number of generatored columns, because we might not be able to detect all orbitopes.
3151 * For example (1,2), (2,3), (3,4), (3,5) defines the symmetric group on {1,2,3,4,5}, but the generators we expect
3246 /* in the subgroup case it might happen that a generator has less than ntwocycles many 2-cyles */
3289 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
3326 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
3349 int* ntwocycleperms /**< pointer to store the number of 2-cycle permutations in component compidx */
3391 SCIP_CALL( SCIPisInvolutionPerm(perm, propdata->permvars, npermvars, &(ntwocycles[i]), &nbincycles, FALSE) );
3417 * After execution, @p graphcomponents contains all permvars sorted by their color and component,
3418 * @p graphcompbegins points to the indices where new components in @p graphcomponents start and
3428 int** graphcomponents, /**< buffer to store the components of the graph (ordered var indices) */
3501 /* iteratively handle each swap of perm until an invalid one is found or all edges have been added */
3521 /* another permutation has already merged these variables into one component; store its color */
3540 /* a generator is not allowed to connect two components of the same color, since they depend on each other */
3608 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, k)) == firstcolor );
3609 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, img)) == firstcolor );
3619 * disjoint sets to the arrays graphcomponents, graphcompbegins, and compcolorbegins (see above).
3705 SCIP_Bool mayinteract, /**< whether orbitope's symmetries might interact with other symmetries */
3794 /* it might happen that we cannot detect the orbitope if it is generated by permutations with different
3830 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3842 /* iterate over all columns (elements in orbit), because we cannot see from ngencols which columns
3872 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "suborbitope_%d_%d", graphcoloridx, propdata->norbitopes);
3875 SCIP_ORBITOPETYPE_FULL, nrows, ngencols, FALSE, mayinteract, FALSE, FALSE, propdata->conssaddlp,
3906 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
3959 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "strong_sbcs_%s_%s", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
3980 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize, newsize) );
4005 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
4061 assert( ! SCIPhashmapExists(varsinlexorder, (void*) (long) (*lexorder)[k]) ); /* Use int as pointer */
4066 /* We will store the newest and the largest orbit and activeorb will be used to mark at which entry of the array
4084 /* if the first variable was already contained in another orbit or if there are no variables left anyway, skip the
4133 SCIPdebugMsg(scip, " adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
4145 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "weak_sbcs_%d_%s_%s", symgrpcompidx, SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
4166 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize, newsize) );
4197 /* the leader of the weak inequalities has to be the first element in the lexicographic order */
4245 SCIP_VAR** modifiedpermvars, /**< memory for array of permutation vars w.r.t. new variable ordering */
4281 /* Iterate over leaders and put the l-th leader to the l-th position of the lexicographic order.
4282 * We do this by swapping the l-th leader with the element at position l of the current permvars array. */
4444 /* create arrays for modified permutations in case we adapt the lexicographic order because of suborbitopes */
4459 SCIPdebugMsg(scip, "starting subgroup detection routine for %d components\n", propdata->ncomponents);
4495 /* set the first npermsincomp entries of genorder; the others are not used for this component */
4504 SCIPdebugMsg(scip, "component %d has %d permutations consisting of 2-cycles\n", i, ntwocycleperms);
4532 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "(%s,", SCIPvarGetName(propdata->permvars[k]));
4536 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%s,", SCIPvarGetName(propdata->permvars[j]));
4563 SCIPdebugMsg(scip, " created subgroup detection graph using %d of the permutations\n", nusedperms);
4604 norbitopesincomp = getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
4607 /* if there is just one orbitope satisfying the requirements, handle the full component by symresacks */
4619 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, propdata->perms[propdata->components[propdata->componentbegins[i] + k]],
4665 SCIPdebugMsg(scip, " color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
4717 SCIPdebugMsg(scip, " affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
4730 SCIPdebugMsg(scip, " detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
4737 * It might happen that we cannot generate the orbitope matrix if the orbitope is not generated by permutations
4738 * all having the same number of 2-cycles, e.g., the orbitope generated by (1,2)(4,5), (2,3), (5,6).
4751 /* adapt the first variable per color to be compatible with the created orbiope (upper left variable) */
4791 SCIP_CALL( addStrongSBCsSubgroup(scip, propdata, graphcompbegins, graphcomponents, largestcolorcomp,
4795 if ( ! SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
4842 SCIPdebugMsg(scip, " don't add weak sbcs because all generators were used or the settings forbid it\n");
4844 /* if suborbitopes or strong group actions have been found, potentially add symresacks adapted to
4865 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, modifiedperms[propdata->components[propdata->componentbegins[i] + k]],
4880 SCIPdebugMsg(scip, " add symresack for permutation %d of component %d adapted to suborbitope lexorder\n", k, i);
4921 /** sorts orbitope vars matrix such that rows are sorted increasingly w.r.t. minimum variable index in row;
5011 int* componentbegins, /**< array containing begin positions of components in components array */
5100 /* no or different number of 2-cycles or not all vars binary: permutations cannot generate orbitope */
5121 SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx[j], npermsincomponent + 1) ); /*lint !e866*/
5160 SCIP_CALL( SCIPgenerateOrbitopeVarsMatrix(scip, &vars, ntwocyclescomp, npermsincomponent + 1, permvars,
5161 npermvars, orbitopevaridx, columnorder, nusedelems, rowisbinary, &infeasibleorbitope, FALSE, NULL, NULL, NULL) );
5167 SCIPdebugMsg(scip, "found an orbitope of size %d x %d in component %d\n", ntwocyclescomp, npermsincomponent + 1, i);
5172 SCIP_CALL( SCIPsortOrbitope(scip, orbitopevaridx, vars, nbincyclescomp, npermsincomponent + 1) );
5215 SCIP_VAR** graphvars, /**< variables encoded in conflict graph (either all vars or permvars) */
5364 SCIP_Bool* success /**< pointer to store whether conflict graph could be created successfully */
5392 SCIPdebugMsg(scip, "Could not find setppc conshdlr --> construction of conflict graph aborted.\n");
5401 SCIPdebugMsg(scip, "No setppc constraints present --> construction of conflict graph aborted.\n");
5473 SCIPdebugMsg(scip, "Construction of conflict graph terminated; %d conflicts detected.\n", nedges);
5522 int* componentbegins, /**< array containing begin positions of components in components array */
5563 /* adapt natural variable order to a variable order that is compatible with Schreier Sims constraints */
5576 SCIP_CALL( adaptSymmetryDataSST(scip, perms, modifiedperms, nperms, permvars, modifiedpermvars, npermvars,
5642 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, modifiedperms[permidx], modifiedpermvars, npermvars, FALSE,
5647 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[permidx], permvars, npermvars, FALSE,
5691 SCIP_Shortbool* orbitvarinconflict, /**< indicator whether orbitvar is in conflict with orbit leader */
5725 /* variables in conflict with leader are fixed and not treated by a cut; trailing -1 to not count the leader */
5847 SCIP_HASHMAP* varmap, /**< map from variable to node label in conflict graph or NULL if useconflictgraph == FALSE */
5858 SCIP_Shortbool* orbitvarinconflict, /**< array to store whether a var in the orbit is conflicting with leader */
5859 int* norbitvarinconflict, /**< pointer to store number of vars in the orbit in conflict with leader */
5904 if ( leaderrule == (int) SCIP_LEADERRULE_FIRSTINORBIT || leaderrule == (int) SCIP_LEADERRULE_LASTINORBIT )
5972 leader = SCIPhashmapGetImageInt(varmap, permvars[orbits[orbitbegins[*orbitidx] + *leaderidx]]);
5978 if ( *success && tiebreakrule == (int) SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT && nconflictvars > 0 )
6046 leader = SCIPhashmapGetImageInt(varmap, permvars[orbits[orbitbegins[*orbitidx] + *leaderidx]]);
6279 /* initialize array indicating whether permutations shall not be considered for orbit permutations */
6330 SCIP_CALL( updateSymInfoConflictGraphSST(scip, conflictgraph, vars, nvars, permvars, npermvars, FALSE,
6335 if ( (leaderrule == SCIP_LEADERRULE_MAXCONFLICTSINORBIT || leaderrule == SCIP_LEADERRULE_MAXCONFLICTS)
6338 if ( (leaderrule == SCIP_LEADERRULE_MAXCONFLICTSINORBIT || leaderrule == SCIP_LEADERRULE_MAXCONFLICTS)
6343 if ( tiebreakrule == SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT && selectedtype != SCIP_VARTYPE_BINARY )
6348 permvars, npermvars, orbits, orbitbegins, norbits, propdata->sstleaderrule, propdata->ssttiebreakrule, selectedtype,
6349 &orbitidx, &orbitleaderidx, orbitvarinconflict, &norbitvarinconflict, conflictgraphcreated, &success) );
6355 assert( 0 <= orbitleaderidx && orbitleaderidx < orbitbegins[orbitidx + 1] - orbitbegins[orbitidx] );
6356 SCIPdebugMsg(scip, "%d\t\t%d\t\t%d\n", orbitidx, orbitleaderidx, orbitbegins[orbitidx + 1] - orbitbegins[orbitidx]);
6360 orbits, orbitbegins, orbitidx, orbitleaderidx, orbitvarinconflict, norbitvarinconflict, &nchanges, conflictgraphcreated) );
6362 ++norbitleadercomponent[propdata->vartocomponent[orbits[orbitbegins[orbitidx] + orbitleaderidx]]];
6386 /* if Schreier Sims constraints have been added, store that Schreier Sims has been used for this component */
6462 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
6466 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
6469 /* if there is no symmetry compatible with OF, check whether there are more general symmetries */
6477 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_INTEGER | SYM_SPEC_REAL, 0) );
6482 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_INTEGER | SYM_SPEC_REAL, 0) );
6491 SCIPdebugMsg(scip, "Symmetry propagator: problem is linear and no symmetry on binary variables has been found, turning symretope constraints off.\n");
6495 assert( hasNonlinearConstraints(propdata) || propdata->binvaraffected || propdata->sstenabled );
6505 SCIP_CALL( detectOrbitopes(scip, propdata, propdata->components, propdata->componentbegins, propdata->ncomponents) );
6523 if ( propdata->ncompblocked < propdata->ncomponents && propdata->detectsubgroups && propdata->symconsenabled )
6527 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize) );
6550 SCIP_CALL( addSymresackConss(scip, prop, propdata->components, propdata->componentbegins, propdata->ncomponents) );
6553 /* free symmetry conss if no orbitope/symresack constraints have been found (may happen if Schreier-Sims constraints are active) */
6570 * Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the
6571 * stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that
6572 * has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be
6711 * The variables are added to bg1 and bg1list, which are prefilled with the variables globally fixed to 1.
6751 /* If we stopped due to a solving limit, it might happen that a non-root node has no domain changes, in all other
6850 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
6854 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
6856 assert( hasNonlinearConstraints(propdata) || propdata->binvaraffected || ! propdata->ofenabled );
6894 SCIP_CALL( computeBranchingVariables(scip, npermvars, propdata->permvarmap, bg1, bg1list, &nbg1) );
6949 /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
6952 (SCIPvarGetType(varv) == SCIP_VARTYPE_IMPLINT && SCIPvarGetType(varimg) == SCIP_VARTYPE_CONTINUOUS &&
6955 (SCIPvarGetType(varv) == SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(varimg) == SCIP_VARTYPE_IMPLINT &&
7008 /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
7011 (SCIPvarGetType(varv) == SCIP_VARTYPE_IMPLINT && SCIPvarGetType(varimg) == SCIP_VARTYPE_CONTINUOUS &&
7014 (SCIPvarGetType(varv) == SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(varimg) == SCIP_VARTYPE_IMPLINT &&
7031 * Note that variables globally fixed to 1 are not resetted, since the loop starts at propdata->nbg1. */
7043 orbits, orbitbegins, &norbits, components, componentbegins, vartocomponent, propdata->componentblocked, ncomponents, propdata->nmovedpermvars) );
7050 SCIPdebugMsg(scip, "Perform orbital fixing on %d orbits (%d active perms).\n", norbits, nactiveperms);
7051 SCIP_CALL( performOrbitalFixing(scip, permvars, nbinpermvars, orbits, orbitbegins, norbits, infeasible, &nfixedzero, &nfixedone) );
7072 /** presolving initialization method of propagator (called when presolving is about to begin) */
7093 else if ( SCIPgetNRuns(scip) > propdata->lastrestart && isSymmetryRecomputationRequired(scip, propdata) )
7111 /* otherwise compute symmetry if timing requests it; fix non-binary potential branching variables */
7114 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
7118 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
7127 /** presolving deinitialization method of propagator (called after presolving has been finished) */
7143 /* guarantee that symmetries are computed (and handled) if the solving process has not been interrupted
7145 if ( (propdata->symconsenabled || propdata->sstenabled) && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN )
7150 /* if timing requests it, guarantee that symmetries are computed even if presolving is disabled */
7151 if ( propdata->ofenabled && propdata->ofsymcomptiming <= 1 && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN )
7156 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
7160 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
7195 assert( 0 <= propdata->addconsstiming && propdata->addconsstiming <= SYM_COMPUTETIMING_AFTERPRESOL );
7196 if ( propdata->addconsstiming > SYM_COMPUTETIMING_DURINGPRESOL && ! SCIPisPresolveFinished(scip) )
7228 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss - noldngenconns;
7234 SCIP_CALL( SCIPpresolCons(scip, propdata->genorbconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7235 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7236 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7241 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genorbconss[i]));
7248 SCIP_CALL( SCIPpresolCons(scip, propdata->genlinconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7249 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7250 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7255 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genlinconss[i]));
7264 SCIP_CALL( SCIPpresolCons(scip, propdata->sstconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7265 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7266 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7271 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->sstconss[i]));
7275 SCIPdebugMsg(scip, "Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
7281 assert( 0 <= propdata->ofsymcomptiming && propdata->ofsymcomptiming <= SYM_COMPUTETIMING_AFTERPRESOL );
7282 if ( propdata->ofenabled && propdata->performpresolving && propdata->ofsymcomptiming <= SYM_COMPUTETIMING_DURINGPRESOL )
7309 /* otherwise compute symmetry early if timing requests it; fix non-binary potential branching variables */
7312 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
7316 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
7361 else if ( SCIPgetNRuns(scip) > propdata->lastrestart && isSymmetryRecomputationRequired(scip, propdata) )
7407 {
7443 * Note that this is relatively difficult to obtain: One needs to include all bounds of variables that are responsible
7444 * for creating the orbit in which the variables that was propagated lies. This includes all variables that are moved
7563 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(propdata->eventhdlr), EVENTHDLR_SYMMETRY_NAME, EVENTHDLR_SYMMETRY_DESC,
7577 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolSymmetry, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
7589 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
7635 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)",
7641 "timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)",
7651 "recompute symmetries after a restart has occured? (0 = never, 1 = always, 2 = if OF found reduction)",
7681 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
7686 "rule to select the orbit in Schreier Sims inequalities (variable in 0: minimum size orbit; 1: maximum size orbit; 2: orbit with most variables in conflict with leader)",
7691 "rule to select the leader in an orbit (0: first var; 1: last var; 2: var having most conflicting vars in orbit; 3: var having most conflicting vars in problem)",
7696 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);" \
7712 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
7733 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, SYMsymmetryGetName(), SYMsymmetryGetDesc()) );
7747 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix (or NULL)*/
7748 int*** permstrans, /**< pointer to store permutation generators as (npermvars x nperms) matrix (or NULL)*/
7750 SCIP_Bool* binvaraffected, /**< pointer to store whether binary variables are affected (or NULL) */
7752 int** componentbegins, /**< pointer to store begin positions of components in components array (or NULL) */
7753 int** vartocomponent, /**< pointer to store assignment from variable to its component (or NULL) */
7765 assert( ncomponents != NULL || (components == NULL && componentbegins == NULL && vartocomponent == NULL) );
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, SCIP_Bool transposed, int **components, int **componentbegins, int **vartocomponent, unsigned **componentblocked, int *ncomponents)
Definition: symmetry.c:757
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:270
Definition: type_symmetry.h:54
static SCIP_RETCODE addSSTConssOrbitAndUpdateSST(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_PROPDATA *propdata, SCIP_VAR **permvars, int *orbits, int *orbitbegins, int orbitidx, int orbitleaderidx, SCIP_Shortbool *orbitvarinconflict, int norbitvarinconflict, int *nchgbds, SCIP_Bool useconflictgraph)
Definition: prop_symmetry.c:5683
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:90
Definition: type_result.h:33
void SCIPsortIntIntPtr(int *intarray1, int *intarray2, void **ptrarray, int len)
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:491
static SCIP_RETCODE propagateOrbitalFixing(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nprop)
Definition: prop_symmetry.c:6807
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5200
SCIP_RETCODE SCIPsimplifyExpr(SCIP *scip, SCIP_EXPR *rootexpr, SCIP_EXPR **simplified, SCIP_Bool *changed, SCIP_Bool *infeasible, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1762
Definition: type_symmetry.h:115
SCIP_RETCODE SCIPincludeTable(SCIP *scip, const char *name, const char *desc, SCIP_Bool active, SCIP_DECL_TABLECOPY((*tablecopy)), SCIP_DECL_TABLEFREE((*tablefree)), SCIP_DECL_TABLEINIT((*tableinit)), SCIP_DECL_TABLEEXIT((*tableexit)), SCIP_DECL_TABLEINITSOL((*tableinitsol)), SCIP_DECL_TABLEEXITSOL((*tableexitsol)), SCIP_DECL_TABLEOUTPUT((*tableoutput)), SCIP_TABLEDATA *tabledata, int position, SCIP_STAGE earlieststage)
Definition: scip_table.c:47
Definition: type_symmetry.h:47
Definition: type_symmetry.h:78
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11175
Definition: struct_scip.h:59
Constraint handler for variable bound constraints .
static SCIP_RETCODE addSymresackConss(SCIP *scip, SCIP_PROP *prop, int *components, int *componentbegins, int ncomponents)
Definition: prop_symmetry.c:5519
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2487
static SCIP_RETCODE updateSymInfoConflictGraphSST(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_VAR **permvars, int npermvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *varmap, int *orbits, int *orbitbegins, int norbits)
Definition: prop_symmetry.c:5213
static SCIP_Bool isLeadervartypeCompatible(SCIP_VAR *var, int leadervartype)
Definition: prop_symmetry.c:708
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:345
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:117
static SCIP_DECL_TABLEFREE(tableFreeOrbitalfixing)
Definition: prop_symmetry.c:470
Definition: type_symmetry.h:48
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:730
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3352
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5352
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5415
Definition: struct_var.h:151
SCIP_RETCODE SCIPgetSymmetry(SCIP *scip, int *npermvars, SCIP_VAR ***permvars, SCIP_HASHMAP **permvarmap, int *nperms, int ***perms, int ***permstrans, SCIP_Real *log10groupsize, SCIP_Bool *binvaraffected, int **components, int **componentbegins, int **vartocomponent, int *ncomponents)
Definition: prop_symmetry.c:7742
SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_symresack.c:1725
Definition: type_symmetry.h:106
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:88
Definition: type_result.h:49
static SCIP_RETCODE addSSTConss(SCIP *scip, SCIP_PROPDATA *propdata, int *nchgbds)
Definition: prop_symmetry.c:6092
Definition: cons_setppc.h:80
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3373
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7721
Definition: type_result.h:38
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:490
SCIP_Real * SCIPgetBoundsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3415
static SCIP_RETCODE freeSymmetryData(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:793
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:95
Definition: type_symmetry.h:53
Definition: struct_misc.h:140
Definition: struct_var.h:198
Definition: struct_var.h:82
static SCIP_DECL_PROPRESPROP(propRespropSymmetry)
Definition: prop_symmetry.c:7449
static SCIP_RETCODE detectOrbitopes(SCIP *scip, SCIP_PROPDATA *propdata, int *components, int *componentbegins, int ncomponents)
Definition: prop_symmetry.c:5008
SCIP_RETCODE SCIPcomputeOrbitsFilterSym(SCIP *scip, int npermvars, int **permstrans, int nperms, SCIP_Shortbool *inactiveperms, int *orbits, int *orbitbegins, int *norbits, int *components, int *componentbegins, int *vartocomponent, unsigned *componentblocked, int ncomponents, int nmovedpermvars)
Definition: symmetry.c:154
Definition: type_message.h:45
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4547
static SCIP_RETCODE freeConflictGraphSST(SCIP *scip, SCIP_DIGRAPH **conflictgraph, int nnodes)
Definition: prop_symmetry.c:5482
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3014
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
Definition: type_symmetry.h:80
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3699
Definition: type_var.h:53
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3132
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3757
int SCIPgetSymmetryNGenerators(SCIP *scip)
Definition: prop_symmetry.c:7842
Definition: cons_setppc.h:79
static SCIP_RETCODE SCIPsortOrbitope(SCIP *scip, int **orbitopevaridx, SCIP_VAR ***vars, int nrows, int ncols)
Definition: prop_symmetry.c:4926
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5317
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13745
Definition: type_symmetry.h:52
Constraint handler for AND constraints, .
static SCIP_RETCODE detectAndHandleSubgroups(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:4405
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:123
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:438
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5398
Constraint handler for the set partitioning / packing / covering constraints .
static SCIP_RETCODE determineSymmetry(SCIP *scip, SCIP_PROPDATA *propdata, SYM_SPEC symspecrequire, SYM_SPEC symspecrequirefixed)
Definition: prop_symmetry.c:2653
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:111
static SCIP_RETCODE checkSymmetriesAreSymmetries(SCIP *scip, SYM_SPEC fixedtype, SYM_MATRIXDATA *matrixdata, int nperms, int **perms)
Definition: prop_symmetry.c:1400
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:74
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18450
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:673
static SCIP_DECL_PROPINITPRE(propInitpreSymmetry)
Definition: prop_symmetry.c:7075
static SCIP_RETCODE getActiveVariables(SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
Definition: prop_symmetry.c:1127
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
Definition: struct_tree.h:132
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
Definition: scip_datastructures.c:608
Definition: type_symmetry.h:77
Definition: prop_symmetry.c:544
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2236
static SCIP_RETCODE addWeakSBCsSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int ncompcolors, int *chosencomppercolor, int *firstvaridxpercolor, int symgrpcompidx, int *naddedconss, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
Definition: prop_symmetry.c:3995
public functions to work with algebraic expressions
Definition: struct_symmetry.h:35
interface for symmetry computations
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: scip_expr.c:1723
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3363
void SCIPsortIntPtr(int *intarray, void **ptrarray, int len)
constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric gro...
constraint handler for symresack constraints
static SCIP_RETCODE checkTwoCyclePermsAreOrbitope(SCIP *scip, SCIP_VAR **permvars, int npermvars, int **perms, int *activeperms, int ntwocycles, int nactiveperms, int **orbitopevaridx, int *columnorder, int *nusedelems, int *nusedcols, SCIP_Shortbool *rowisbinary, SCIP_Bool *isorbitope, SCIP_Shortbool *activevars)
Definition: prop_symmetry.c:3160
Constraint handler for "or" constraints, .
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:133
static int getNSymhandableConss(SCIP *scip, SCIP_CONSHDLR *conshdlr_nonlinear)
Definition: prop_symmetry.c:1658
Definition: type_symmetry.h:49
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:96
Definition: struct_misc.h:128
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
Definition: scip_prop.c:254
static SCIP_RETCODE chooseOrderOfGenerators(SCIP *scip, SCIP_PROPDATA *propdata, int compidx, int **genorder, int *ntwocycleperms)
Definition: prop_symmetry.c:3345
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5375
Definition: type_result.h:35
SCIP_Real * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linking.c:3724
Definition: struct_cons.h:37
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2558
SCIP_Bool SCIPisOrbitalfixingEnabled(SCIP *scip)
Definition: prop_symmetry.c:7822
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5197
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
static SCIP_RETCODE computeBranchingVariables(SCIP *scip, int nvars, SCIP_HASHMAP *varmap, SCIP_Shortbool *bg1, int *bg1list, int *nbg1)
Definition: prop_symmetry.c:6715
Definition: struct_cons.h:117
static SCIP_DECL_TABLEOUTPUT(tableOutputOrbitalfixing)
Definition: prop_symmetry.c:446
Definition: type_expr.h:691
void * SCIPdigraphGetNodeData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7658
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Definition: type_lp.h:47
SCIP_RETCODE SCIPpresolCons(SCIP *scip, SCIP_CONS *cons, int nrounds, SCIP_PRESOLTIMING presoltiming, int nnewfixedvars, int nnewaggrvars, int nnewchgvartypes, int nnewchgbds, int nnewholes, int nnewdelconss, int nnewaddconss, int nnewupgdconss, int nnewchgcoefs, int nnewchgsides, int *nfixedvars, int *naggrvars, int *nchgvartypes, int *nchgbds, int *naddholes, int *ndelconss, int *naddconss, int *nupgdconss, int *nchgcoefs, int *nchgsides, SCIP_RESULT *result)
Definition: scip_cons.c:2343
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3730
Definition: type_symmetry.h:116
void SCIPdigraphSetNodeData(SCIP_DIGRAPH *digraph, void *dataptr, int node)
Definition: misc.c:7674
SCIP_RETCODE SCIPincludePropSymmetry(SCIP *scip)
Definition: prop_symmetry.c:7485
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4763
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8712
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5438
static SCIP_DECL_HASHGETKEY(SYMhashGetKeyVartype)
Definition: prop_symmetry.c:489
static SCIP_RETCODE addOrbitopeSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *usedperms, int nusedperms, int *compcolorbegins, int *graphcompbegins, int *graphcomponents, int graphcoloridx, int nrows, int ncols, int *firstvaridx, int *compidxfirstrow, int **lexorder, int *nvarslexorder, int *maxnvarslexorder, SCIP_Bool mayinteract, SCIP_Bool *success)
Definition: prop_symmetry.c:3690
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
Definition: cons_nonlinear.c:12250
internal miscellaneous methods
Definition: prop_symmetry.c:553
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:260
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11148
Definition: type_retcode.h:33
Definition: cons_setppc.h:78
Definition: type_stat.h:33
static SCIP_RETCODE addStrongSBCsSubgroup(SCIP *scip, SCIP_PROPDATA *propdata, int *graphcompbegins, int *graphcomponents, int graphcompidx, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
Definition: prop_symmetry.c:3901
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1735
propagator for symmetry handling
Definition: type_result.h:42
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
Definition: struct_expr.h:193
Definition: graph_load.c:93
static SCIP_RETCODE selectOrbitLeaderSSTConss(SCIP *scip, SCIP_DIGRAPH *conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_HASHMAP *varmap, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, int leaderrule, int tiebreakrule, SCIP_VARTYPE leadervartype, int *orbitidx, int *leaderidx, SCIP_Shortbool *orbitvarinconflict, int *norbitvarinconflict, SCIP_Bool useconflictgraph, SCIP_Bool *success)
Definition: prop_symmetry.c:5843
static SCIP_RETCODE createConflictGraphSST(SCIP *scip, SCIP_DIGRAPH **conflictgraph, SCIP_VAR **graphvars, int ngraphvars, SCIP_Bool onlypermvars, SCIP_HASHMAP *permvarmap, SCIP_Bool *success)
Definition: prop_symmetry.c:5358
SCIP_RETCODE SCIPcreateDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
Definition: scip_datastructures.c:645
static SCIP_RETCODE delSymConss(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:1024
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
Definition: misc.c:11245
static int getNOrbitopesInComp(SCIP_VAR **permvars, int *graphcomponents, int *graphcompbegins, int *compcolorbegins, int ncompcolors, int symcompsize)
Definition: prop_symmetry.c:4322
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2514
Definition: struct_prop.h:37
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2300
Definition: type_retcode.h:34
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13665
SCIP_RETCODE SCIPgetConsCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_CONS *sourcecons, SCIP_CONS **targetcons, SCIP_CONSHDLR *sourceconshdlr, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, const char *name, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode, SCIP_Bool global, SCIP_Bool *valid)
Definition: scip_copy.c:1577
Definition: struct_expr.h:95
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5421
constraint handler for linking binary variables to a linking (continuous or integer) variable ...
SCIP_RETCODE SCIPdigraphAddArcSafe(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7595
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7706
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:575
static SCIP_RETCODE setSymmetryData(SCIP *scip, SCIP_VAR **vars, int nvars, int nbinvars, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, int **perms, int nperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool *compressed)
Definition: prop_symmetry.c:1707
Definition: type_var.h:55
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition: var.c:17168
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9441
constraint handler for nonlinear constraints specified by algebraic expressions
Definition: type_var.h:54
Definition: type_message.h:43
static SCIP_Bool checkSymmetryDataFree(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:659
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition: symmetry.c:524
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2473
SCIP_Bool SYMcanComputeSymmetry(void)
Definition: compute_symmetry_bliss.cpp:950
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition: var.c:17206
Definition: type_set.h:40
static SCIP_RETCODE adaptSymmetryDataSST(SCIP *scip, int **origperms, int **modifiedperms, int nperms, SCIP_VAR **origpermvars, SCIP_VAR **modifiedpermvars, int npermvars, int *leaders, int nleaders)
Definition: prop_symmetry.c:4240
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:391
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:848
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5444
Definition: type_symmetry.h:117
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2548
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12773
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, SYM_EXPRDATA *exprdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize)
Definition: compute_symmetry_bliss.cpp:986
SCIP_RETCODE SCIPgenerateOrbitopeVarsMatrix(SCIP *scip, SCIP_VAR ****vars, int nrows, int ncols, SCIP_VAR **permvars, int npermvars, int **orbitopevaridx, int *columnorder, int *nusedelems, SCIP_Shortbool *rowisbinary, SCIP_Bool *infeasible, SCIP_Bool storelexorder, int **lexorder, int *nvarsorder, int *maxnvarsorder)
Definition: symmetry.c:961
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4624
SCIP_RETCODE SCIPextendSubOrbitope(int **suborbitope, int nrows, int nfilledcols, int coltoextend, int *perm, SCIP_Bool leftextension, int **nusedelems, SCIP_VAR **permvars, SCIP_Shortbool *rowisbinary, SCIP_Bool *success, SCIP_Bool *infeasible)
Definition: symmetry.c:627
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9418
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition: expriter.c:654
Definition: type_set.h:39
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_linear.c:17840
Constraint handler for XOR constraints, .
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:520
Definition: struct_misc.h:80
Definition: type_symmetry.h:95
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:303
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5440
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18537
methods for handling symmetries
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
Definition: cons_linking.c:3655
SCIP_RETCODE SCIPcomputeOrbitVar(SCIP *scip, int npermvars, int **perms, int **permstrans, int *components, int *componentbegins, SCIP_Shortbool *ignoredvars, SCIP_Shortbool *varfound, int varidx, int component, int *orbit, int *orbitsize)
Definition: symmetry.c:302
SCIP_VAR * SCIPgetResultantOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2215
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:686
SCIP_BOUNDTYPE * SCIPgetBoundtypesBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3394
SCIP_VAR * SCIPgetLinkvarLinking(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linking.c:3632
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3740
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13722
public methods for data structures
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:158
Definition: type_retcode.h:45
static SCIP_RETCODE computeSymmetryGroup(SCIP *scip, SCIP_Bool doubleequations, SCIP_Bool compresssymmetries, SCIP_Real compressthreshold, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool local, SCIP_Bool checksymmetries, SCIP_Bool usecolumnsparsity, SCIP_CONSHDLR *conshdlr_nonlinear, int *npermvars, int *nbinpermvars, SCIP_VAR ***permvars, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, int *nmovedvars, SCIP_Bool **isnonlinvar, SCIP_Bool *binvaraffected, SCIP_Bool *compressed, SCIP_Bool *success)
Definition: prop_symmetry.c:1838
Definition: type_set.h:44
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2599
Definition: struct_symmetry.h:69
static SCIP_RETCODE performOrbitalFixing(SCIP *scip, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, SCIP_Bool *infeasible, int *nfixedzero, int *nfixedone)
Definition: prop_symmetry.c:6577
static SCIP_RETCODE collectCoefficients(SCIP *scip, SCIP_Bool doubleequations, SCIP_VAR **linvars, SCIP_Real *linvals, int nlinvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool istransformed, SYM_RHSSENSE rhssense, SYM_MATRIXDATA *matrixdata, int *nconssforvar)
Definition: prop_symmetry.c:1173
static SCIP_Bool hasNonlinearConstraints(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:1696
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
Definition: scip_general.c:704
SCIP_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool usedynamicprop, SCIP_Bool mayinteract, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_orbitope.c:3661
Definition: struct_misc.h:268
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18561
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:464
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:102
static SCIP_RETCODE setSymmetryMethodEnabledValues(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:766
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12778
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3096
SCIPallocBlockMemory(scip, subsol))
Definition: type_retcode.h:43
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3221
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:238
constraint handler for bound disjunction constraints
void SCIPfreeDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset)
Definition: scip_datastructures.c:660
Definition: objbenders.h:33
static SCIP_Bool SymmetryFixVar(SYM_SPEC fixedtype, SCIP_VAR *var)
Definition: prop_symmetry.c:1106
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13768
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:190
Definition: struct_misc.h:210
static SCIP_DECL_PROPEXITPRE(propExitpreSymmetry)
Definition: prop_symmetry.c:7130
Definition: struct_symmetry.h:92
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18513
static SCIP_DECL_HASHKEYVAL(SYMhashKeyValVartype)
Definition: prop_symmetry.c:534
static SCIP_RETCODE tryAddSymmetryHandlingConss(SCIP *scip, SCIP_PROP *prop, int *nchgbds, SCIP_Bool *earlyterm)
Definition: prop_symmetry.c:6415
static SCIP_Bool isSymmetryRecomputationRequired(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:737
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18426
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:130
static SCIP_RETCODE buildSubgroupGraph(SCIP *scip, SCIP_PROPDATA *propdata, int *genorder, int ntwocycleperms, int compidx, int **graphcomponents, int **graphcompbegins, int **compcolorbegins, int *ngraphcomponents, int *ncompcolors, int **usedperms, int *nusedperms, int usedpermssize, SCIP_Shortbool *permused)
Definition: prop_symmetry.c:3423
Definition: type_result.h:39
Definition: struct_event.h:195
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:48
Definition: type_var.h:74
SCIP_RETCODE SCIPincludePropBasic(SCIP *scip, SCIP_PROP **propptr, const char *name, const char *desc, int priority, int freq, SCIP_Bool delay, SCIP_PROPTIMING timingmask, SCIP_DECL_PROPEXEC((*propexec)), SCIP_PROPDATA *propdata)
Definition: scip_prop.c:105
Definition: type_symmetry.h:50
Definition: type_var.h:58
Definition: type_symmetry.h:51