prop_symmetry.c
Go to the documentation of this file.
34 * - It allows to compute symmetries of the problem and to store this information in adequate form. The symmetry
47 * - We treat implicit integer variables as if they were continuous/real variables. The reason is that there is currently
48 * no distinction between implicit integer and implicit binary. Moreover, currently implicit integer variables hurt
49 * our code more than continuous/real variables (we basically do not handle integral variables at all).
50 * - We do not copy symmetry information, since it is not clear how this information transfers. Moreover, copying
51 * symmetry might inhibit heuristics. But note that solving a sub-SCIP might then happen without symmetry information!
58 * - The code automatically detects whether symmetry substructures like symresacks or orbitopes are present and possibly
61 * - We try to compute symmetry as late as possible and then add constraints based on this information.
62 * - Currently, we only allocate memory for pointers to symresack constraints for group generators. If further
71 * The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the
72 * 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
73 * variables in the orbit is fixed to 0 or 1, respectively. Different from Margot, the subgroup is obtained by filtering
76 * @pre All variable fixings applied by other components are required to be strict, i.e., if one variable is fixed to
77 * a certain value v, all other variables in the same variable orbit can be fixed to v as well, c.f.@n
78 * F. Margot: Symmetry in integer linear programming. 50 Years of Integer Programming, 647-686, Springer 2010.
81 * (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
82 * setppc constraint handler may fix \f$(x_1,x_2) = (1,0)\f$. However, since both variables are symmetric, this setting
83 * is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would
84 * declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different
85 * values). To avoid this situation, we have to assume that all non-strict settings fix variables globally, i.e., we
86 * can take care of it by taking variables into account that have been globally fixed to 1. In fact, it suffices to
87 * consider one kind of global fixings since stabilizing one kind prevents an orbit to contain variables that have
90 * @pre All non-strict settings are global settings, since otherwise, we cannot (efficiently) take care of them.
92 * @pre No non-strict setting algorithm is interrupted early (e.g., by a time or iteration limit), since this may lead to
93 * wrong decisions by orbital fixing as well. For example, if cons_setppc in the above toy example starts by fixing
94 * \f$x_2 = 0\f$ and is interrupted afterwards, orbital fixing detects that the orbit \f$\{x_1, x_2\}\f$ contains
95 * one variable that is fixed to 0, and thus, it fixes \f$x_1\f$ to 0 as well. Thus, after these reductions, every
96 * feasible solution has objective 0 which is not optimal. This situation would not occur if the non-strict setting is
97 * complete, because then \f$x_1\f$ is globally fixed to 1, and thus, is stabilized in orbital fixing.
99 * Note that orbital fixing might lead to wrong results if it is called in repropagation of a node, because the path
100 * from the node to the root might have been changed. Thus, the stabilizers of global 1-fixing and 1-branchings of the
101 * initial propagation and repropagation might differ, which may cause conflicts. For this reason, orbital fixing cannot
104 * @note If, besides orbital fixing, also symmetry handling constraints shall be added, orbital fixing is only applied
111 * D. Salvagnin: Symmetry Breaking Inequalities from the Schreier-Sims table. CPAIOR 2018 Proceedings, 521-529, 2018.
113 * These inequalities are computed as follows. Throughout these procedure a set of so-called leaders is maintained.
114 * 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.
115 * the symmetry group of the mixed-integer program. For each variable \f$x_j\f$ in the orbit of \f$x_i\f$, the
116 * inequality \f$x_i \geq x_j\f$ is a valid symmetry handling inequality, which can be added to the mixed-integer
117 * 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
118 * compute the pointwise stabilizer of the leader set. In the next step, select a new variable, compute its orbit
119 * w.r.t. the stabilizer group of the leaders, add the inequalities based on this orbit, and add the new leader
120 * to the set of leaders. This procedure is iterated until the pointwise stabilizer group of the leaders has become
131 * @todo Order rows of orbitopes (in particular packing/partitioning) w.r.t. cliques in conflict graph.
136 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
167 #define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
169 #define PROP_PRESOL_PRIORITY -10000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers) */
170 #define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
171 #define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
175 #define DEFAULT_MAXGENERATORS 1500 /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
176 #define DEFAULT_CHECKSYMMETRIES FALSE /**< Should all symmetries be checked after computation? */
177 #define DEFAULT_DISPLAYNORBITVARS FALSE /**< Should the number of variables affected by some symmetry be displayed? */
178 #define DEFAULT_USECOLUMNSPARSITY FALSE /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
180 #define DEFAULT_COMPRESSSYMMETRIES TRUE /**< Should non-affected variables be removed from permutation to save memory? */
181 #define DEFAULT_COMPRESSTHRESHOLD 0.5 /**< Compression is used if percentage of moved vars is at most the threshold. */
182 #define DEFAULT_SYMFIXNONBINARYVARS FALSE /**< Whether all non-binary variables shall be not affected by symmetries if OF is active? */
186 #define DEFAULT_CONSSADDLP TRUE /**< Should the symmetry breaking constraints be added to the LP? */
188 #define DEFAULT_DETECTORBITOPES TRUE /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
189 #define DEFAULT_DETECTSUBGROUPS TRUE /**< Should we try to detect orbitopes in subgroups of the symmetry group? */
190 #define DEFAULT_ADDWEAKSBCS TRUE /**< Should we add weak SBCs for enclosing orbit of symmetric subgroups? */
191 #define DEFAULT_ADDSTRONGSBCS FALSE /**< Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used? */
192 #define DEFAULT_ADDCONSSTIMING 2 /**< timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) */
193 #define DEFAULT_MAXNCONSSSUBGROUP 500000 /**< Maximum number of constraints up to which subgroup structures are detected */
194 #define DEFAULT_USEDYNAMICPROP TRUE /**< whether dynamic propagation should be used for full orbitopes */
195 #define DEFAULT_PREFERLESSROWS TRUE /**< Shall orbitopes with less rows be preferred in detection? */
198 #define DEFAULT_OFSYMCOMPTIMING 2 /**< timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call) */
200 #define DEFAULT_RECOMPUTERESTART 0 /**< Recompute symmetries after a restart has occurred? (0 = never, 1 = always, 2 = if OF found reduction) */
203 #define DEFAULT_SSTTIEBREAKRULE 1 /**< index of tie break rule for selecting orbit for Schreier Sims constraints? */
204 #define DEFAULT_SSTLEADERRULE 0 /**< index of rule for selecting leader variables for Schreier Sims constraints? */
205 #define DEFAULT_SSTLEADERVARTYPE 14 /**< bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);
207 #define DEFAULT_ADDCONFLICTCUTS TRUE /**< Should Schreier Sims constraints be added if we use a conflict based rule? */
209 #define DEFAULT_SSTMIXEDCOMPONENTS TRUE /**< Should Schreier Sims constraints be added if a symmetry component contains variables of different types? */
213 #define EVENTHDLR_SYMMETRY_DESC "filter global variable fixing event handler for orbital fixing"
219 #define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING /**< output of the statistics table is only printed from this stage onwards */
223 #define MAXGENNUMERATOR 64000000 /**< determine maximal number of generators by dividing this number by the number of variables */
224 #define SCIP_SPECIALVAL 1.12345678912345e+19 /**< special floating point value for handling zeros in bound disjunctions */
225 #define COMPRESSNVARSLB 25000 /**< lower bound on the number of variables above which compression could be performed */
251 int** permstrans; /**< pointer to store transposed permutation generators as (npermvars x nperms) matrix */
256 int nmovedimplintpermvars; /**< number of implicitly integer variables moved by any permutation */
258 SCIP_Shortbool* nonbinpermvarcaptured; /**< array to store which non-binary variables have been captured
269 unsigned* componentblocked; /**< array to store which symmetry methods have been applied to a component using
278 int maxgenerators; /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
280 SCIP_Bool displaynorbitvars; /**< Whether the number of variables in non-trivial orbits shall be computed */
281 SCIP_Bool compresssymmetries; /**< Should non-affected variables be removed from permutation to save memory? */
282 SCIP_Real compressthreshold; /**< Compression is used if percentage of moved vars is at most the threshold. */
286 SCIP_Bool usecolumnsparsity; /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
288 SCIP_Bool symfixnonbinaryvars; /**< Whether all non-binary variables shall be not affected by symmetries if OF is active? */
296 int addconsstiming; /**< timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) */
303 SCIP_Bool detectorbitopes; /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
304 SCIP_Bool detectsubgroups; /**< Should we try to detect orbitopes in subgroups of the symmetry group? */
305 SCIP_Bool addweaksbcs; /**< Should we add weak SBCs for enclosing orbit of symmetric subgroups? */
306 SCIP_Bool addstrongsbcs; /**< Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used? */
310 int maxnconsssubgroup; /**< maximum number of constraints up to which subgroup structures are detected */
326 int recomputerestart; /**< Recompute symmetries after a restart has occured? (0 = never, 1 = always, 2 = if OF found reduction) */
327 int ofsymcomptiming; /**< timing of orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call) */
332 SCIP_Bool offoundreduction; /**< whether orbital fixing has found a reduction since the last time computing symmetries */
346 SCIP_Bool addconflictcuts; /**< Should Schreier Sims constraints be added if we use a conflict based rule? */
348 SCIP_Bool sstmixedcomponents; /**< Should Schreier Sims constraints be added if a symmetry component contains variables of different types? */
369 /** exec the event handler for handling global variable bound changes (necessary for orbital fixing)
371 * Global variable fixings during the solving process might arise because parts of the tree are pruned or if certain
372 * preprocessing steps are performed that do not correspond to strict setting algorithms. Since these fixings might be
373 * caused by or be in conflict with orbital fixing, they can be in conflict with the symmetry handling decisions of
374 * orbital fixing in the part of the tree that is not pruned. Thus, we have to take global fixings into account when
379 {
455 {
468 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 0 :%11d\n", tabledata->propdata->nfixedzero);
469 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " vars fixed to 1 :%11d\n", tabledata->propdata->nfixedone);
479 {
504 * Compare the types of two variables according to objective, lower and upper bound, variable type, and column sparsity.
508 {
548 return SCIPhashFour(SCIPrealHashCode(k->obj), SCIPrealHashCode(k->lb), SCIPrealHashCode((double) k->nconss), SCIPrealHashCode(k->ub));
553 {
557 };
562 {
565 };
579 {
613 {
640 {
757 if ( SCIPgetNRuns(scip) == propdata->lastrestart || propdata->lastrestart == 0 || SCIPgetNRuns(scip) == 1 )
826 /* If symmetry is computed before presolving, it might happen that some variables are turned into binary
827 * variables, for which no event has been catched. Since there currently is no way of checking whether a var
831 SCIP_CALL( SCIPdropVarEvent(scip, propdata->permvars[i], SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED,
857 SCIPfreeBlockMemoryArray(scip, &propdata->nonbinpermvarcaptured, propdata->npermvars - propdata->nbinpermvars);
989 /* if orbital fixing runs exclusively, propdata->perms was already freed in determineSymmetry() */
1124 (SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS || SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT) )
1130 /** Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.
1138 SCIP_Real** scalars, /**< pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c */
1157 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, *nvars, constant, &requiredsize, TRUE) );
1164 SCIP_CALL( SCIPgetProbvarLinearSum(scip, *vars, *scalars, nvars, requiredsize, constant, &requiredsize, TRUE) );
1185 SCIP_Real* linvals, /**< array of linear coefficients values (or NULL if all linear coefficient values are 1) */
1248 /* check whether we have to resize; note that we have to add 2 * nvars since two inequalities may be added */
1255 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matidx), matrixdata->nmaxmatcoef, newsize) );
1256 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matrhsidx), matrixdata->nmaxmatcoef, newsize) );
1257 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matvaridx), matrixdata->nmaxmatcoef, newsize) );
1258 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &(matrixdata->matcoef), matrixdata->nmaxmatcoef, newsize) );
1259 SCIPdebugMsg(scip, "Resized matrix coefficients from %d to %d.\n", matrixdata->nmaxmatcoef, newsize);
1291 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1304 /* add negative of equation; increases chance to detect symmetry, but might increase time to compute symmetry. */
1310 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1352 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1381 assert( 0 <= SCIPvarGetProbindex(vars[j]) && SCIPvarGetProbindex(vars[j]) < SCIPgetNVars(scip) );
1404 * We need the matrix and rhs in the original order in order to speed up the comparison process. The matrix is needed
1443 /* create hashmaps for variable permutation and constraints in non-linear part array for occuring variables */
1523 if ( matrixdata->rhssense[r1] == matrixdata->rhssense[r2] && SCIPisEQ(scip, matrixdata->rhscoef[r1], matrixdata->rhscoef[r2]) )
1531 while ( j < matrixdata->nmatcoef && matrixdata->matrhsidx[j] == r2 && SCIPisEQ(scip, permrow[matrixdata->matvaridx[j]], matrixdata->matcoef[j] ) )
1619 SCIP_CALL( SCIPsimplifyExpr(scip, permutedexpr, &permutedexpr, &success, &infeasible, NULL, NULL) );
1710 return propdata->conshdlr_nonlinear != NULL && SCIPconshdlrGetNActiveConss(propdata->conshdlr_nonlinear) > 0;
1725 int* nmovedvars, /**< pointer to store number of vars affected by symmetry (if usecompression) or NULL */
1726 SCIP_Bool* binvaraffected, /**< pointer to store whether a binary variable is affected by symmetry */
1728 SCIP_Real compressthreshold, /**< if percentage of moved vars is at most threshold, compression is done */
1825 /* detect whether binary variable is affected by symmetry and count number of binary permvars */
1849 SCIP_Bool compresssymmetries, /**< Should non-affected variables be removed from permutation to save memory? */
1850 SCIP_Real compressthreshold, /**< Compression is used if percentage of moved vars is at most the threshold. */
1855 SCIP_Bool usecolumnsparsity, /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
1861 int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
1866 SCIP_Bool* binvaraffected, /**< pointer to store wether a binary variable is affected by symmetry */
1963 SCIPdebugMsg(scip, "Detecting %ssymmetry on %d variables and %d constraints.\n", local ? "local " : "", nvars, nactiveconss);
1966 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &vars, SCIPgetVars(scip), nvars) ); /*lint !e666*/
1971 /* use a staggered scheme for allocating space for non-zeros of constraint matrix since it can become large */
2058 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLinear(scip, cons), SCIPgetValsLinear(scip, cons),
2071 /* SCIPgetBinVarsLinking returns the number of binary variables, but we also need the integer variable */
2081 /* set final entry of vars and vals to the linking variable and its coefficient, respectively */
2098 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_EQUATION, &matrixdata, nconssforvar) );
2101 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, -SCIPinfinity(scip), 1.0, SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2104 SCIP_CALL( collectCoefficients(scip, doubleequations, linvars, 0, nconsvars, 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2137 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nconsvars, (SCIP_Real) SCIPgetRhsXor(scip, cons),
2138 (SCIP_Real) SCIPgetRhsXor(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_XOR, &matrixdata, nconssforvar) );
2192 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsLogicor(scip, cons), 0, SCIPgetNVarsLogicor(scip, cons),
2193 1.0, SCIPinfinity(scip), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2207 SCIP_CALL( collectCoefficients(scip, doubleequations, SCIPgetVarsKnapsack(scip, cons), consvals, nconsvars, -SCIPinfinity(scip),
2208 (SCIP_Real) SCIPgetCapacityKnapsack(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2218 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, 2, SCIPgetLhsVarbound(scip, cons),
2219 SCIPgetRhsVarbound(scip, cons), SCIPconsIsTransformed(cons), SYM_SENSE_INEQUALITY, &matrixdata, nconssforvar) );
2233 * is of type 1. If the bound disjunction has length two and both disjunctions contain the same variable,
2234 * we say the bound disjunction is of type 2. Further bound disjunctions are possible, but can currently
2245 * Note that problems arise if \fb'_i = 0\f for some variable \fx_i\f, because its coefficient in the
2283 /* stop, we cannot handle bounddisjunctions with more than two variables that contain a variable twice */
2289 " Deactivated symmetry handling methods, there exist constraints that cannot be handled by symmetry methods.\n");
2314 SCIP_CALL( collectCoefficients(scip, doubleequations, consvars, consvals, nbounddisjvars, 0.0, 0.0,
2344 for (expr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); expr = SCIPexpriterGetNext(it)) /*lint !e441*/ /*lint !e440*/
2348 /* for variables, we check whether they appear nonlinearly and store the result in the resp. array */
2352 (*isnonlinvar)[SCIPvarGetProbindex(SCIPgetVarExprVar(expr))] = (SCIPexpriterGetParentDFS(it) != rootexpr || !SCIPisExprSum(scip, rootexpr));
2379 SCIPerrorMessage("Cannot determine symmetries for constraint <%s> of constraint handler <%s>.\n",
2422 SCIP_CALL( SCIPhashtableCreate(&vartypemap, SCIPblkmem(scip), 5 * nvars, SYMhashGetKeyVartype, SYMhashKeyEQVartype, SYMhashKeyValVartype, (void*) scip) );
2442 if ( SymmetryFixVar(fixedtype, var) || (nnlconss > 0 && SCIPhashsetExists(auxvars, (void*) var)) )
2446 SCIPdebugMsg(scip, "Detected variable <%s> of fixed type %d - color %d.\n", SCIPvarGetName(var), SCIPvarGetType(var), matrixdata.nuniquevars - 1);
2477 SCIPdebugMsg(scip, "Detected variable <%s> of new type (probindex: %d, obj: %g, lb: %g, ub: %g, type: %d) - color %d.\n",
2478 SCIPvarGetName(var), SCIPvarGetProbindex(var), vt->obj, vt->lb, vt->ub, vt->type, matrixdata.nuniquevars - 1);
2541 SCIPdebugMsg(scip, "Detected new matrix entry type %f - color: %d\n.", val, matrixdata.nuniquemat);
2575 SCIPdebugMsg(scip, "Detected new rhs type %f, type: %u - color: %d\n", val, sense, matrixdata.nuniquerhs);
2590 SCIPdebugMsg(scip, "Number of detected different variables: %d (total: %d).\n", matrixdata.nuniquevars, nvars);
2591 SCIPdebugMsg(scip, "Number of detected different rhs types: %d (total: %d).\n", matrixdata.nuniquerhs, matrixdata.nrhscoef);
2592 SCIPdebugMsg(scip, "Number of detected different matrix coefficients: %d (total: %d).\n", matrixdata.nuniquemat, matrixdata.nmatcoef);
2594 /* do not compute symmetry if all variables are non-equivalent (unique) or if all matrix coefficients are different */
2595 if ( matrixdata.nuniquevars < nvars && (matrixdata.nuniquemat == 0 || matrixdata.nuniquemat < matrixdata.nmatcoef) )
2598 SCIP_CALL( SYMcomputeSymmetryGenerators(scip, maxgenerators, &matrixdata, &exprdata, nperms, nmaxperms,
2603 if ( checksymmetries && SCIPgetStage(scip) > SCIP_STAGE_INITPRESOLVE && ! SCIPisStopped(scip) )
2610 SCIP_CALL( setSymmetryData(scip, vars, nvars, nbinvars, permvars, npermvars, nbinpermvars, *perms, *nperms,
2664 SYM_SPEC symspecrequire, /**< symmetry specification for which we need to compute symmetries */
2665 SYM_SPEC symspecrequirefixed /**< symmetry specification of variables which must be fixed by symmetries */
2716 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2742 /* do not compute symmetry if there are no binary variables and non-binary variables cannot be handled, but only binary variables would be used */
2765 /* count implicit integer variables as real variables, since we cannot currently handle integral variables well */
2773 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2810 " (%.1fs) symmetry computation skipped: there exist constraints that cannot be handled by symmetry methods.\n",
2831 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2849 SCIP_CALL( computeSymmetryGroup(scip, propdata->doubleequations, propdata->compresssymmetries, propdata->compressthreshold,
2850 maxgenerators, symspecrequirefixed, FALSE, propdata->checksymmetries, propdata->usecolumnsparsity, propdata->conshdlr_nonlinear,
2851 &propdata->npermvars, &propdata->nbinpermvars, &propdata->permvars, &propdata->nperms, &propdata->nmaxperms,
2865 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) could not compute symmetry\n", SCIPgetSolvingTime(scip));
2878 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry present\n", SCIPgetSolvingTime(scip));
2888 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) symmetry computation finished: %d generators found (max: ",
2898 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", log10 of symmetry group size: %.1f", propdata->log10groupsize);
2904 SCIP_CALL( SCIPdetermineNVarsAffectedSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2907 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", number of affected variables: %d)\n", propdata->nmovedvars);
2911 /* exit if no binary variables are affected by symmetry and we cannot handle non-binary symmetries */
2914 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry on binary variables present.\n", SCIPgetSolvingTime(scip));
2920 ! ( ISSSTINTACTIVE(propdata->sstleadervartype) || ISSSTIMPLINTACTIVE(propdata->sstleadervartype)
2925 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) -> no handable symmetry found, free symmetry data.\n",
2944 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation started\n", SCIPgetSolvingTime(scip));
2947 /* we only need the components for orbital fixing, orbitope and subgroup detection, and Schreier Sims constraints */
2951 SCIP_CALL( SCIPcomputeComponentsSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2957 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation finished\n", SCIPgetSolvingTime(scip));
3023 /* Only catch binary variables, since integer variables should be fixed pointwise; implicit integer variables
3028 SCIP_CALL( SCIPcatchVarEvent(scip, propdata->permvars[v], SCIP_EVENTTYPE_GLBCHANGED | SCIP_EVENTTYPE_GUBCHANGED,
3099 /* if Schreier-Sims constraints are enabled, also capture symmetric variables and forbid multi aggregation of handable vars */
3154 /** Checks whether given set of 2-cycle permutations forms an orbitope and if so, builds the variable index matrix.
3156 * If @p activevars == NULL, then the function assumes all permutations of the component are active and therefore all
3159 * We need to keep track of the number of generatored columns, because we might not be able to detect all orbitopes.
3160 * 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
3255 /* in the subgroup case it might happen that a generator has less than ntwocycles many 2-cyles */
3298 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
3335 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
3358 int* ntwocycleperms /**< pointer to store the number of 2-cycle permutations in component compidx */
3400 SCIP_CALL( SCIPisInvolutionPerm(perm, propdata->permvars, npermvars, &(ntwocycles[i]), &nbincycles, FALSE) );
3426 * After execution, @p graphcomponents contains all permvars sorted by their color and component,
3427 * @p graphcompbegins points to the indices where new components in @p graphcomponents start and
3437 int** graphcomponents, /**< buffer to store the components of the graph (ordered var indices) */
3510 /* iteratively handle each swap of perm until an invalid one is found or all edges have been added */
3530 /* another permutation has already merged these variables into one component; store its color */
3549 /* a generator is not allowed to connect two components of the same color, since they depend on each other */
3617 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, k)) == firstcolor );
3618 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, img)) == firstcolor );
3628 * disjoint sets to the arrays graphcomponents, graphcompbegins, and compcolorbegins (see above).
3714 SCIP_Bool mayinteract, /**< whether orbitope's symmetries might interact with other symmetries */
3803 /* it might happen that we cannot detect the orbitope if it is generated by permutations with different
3839 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3851 /* iterate over all columns (elements in orbit), because we cannot see from ngencols which columns
3881 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "suborbitope_%d_%d", graphcoloridx, propdata->norbitopes);
3884 SCIP_ORBITOPETYPE_FULL, nrows, ngencols, FALSE, mayinteract, FALSE, FALSE, propdata->conssaddlp,
3915 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
3968 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "strong_sbcs_%s_%s", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
3989 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize, newsize) );
4014 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
4070 assert( ! SCIPhashmapExists(varsinlexorder, (void*) (long) (*lexorder)[k]) ); /* Use int as pointer */
4075 /* We will store the newest and the largest orbit and activeorb will be used to mark at which entry of the array
4093 /* if the first variable was already contained in another orbit or if there are no variables left anyway, skip the
4142 SCIPdebugMsg(scip, " adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
4154 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "weak_sbcs_%d_%s_%s", symgrpcompidx, SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
4175 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize, newsize) );
4206 /* the leader of the weak inequalities has to be the first element in the lexicographic order */
4254 SCIP_VAR** modifiedpermvars, /**< memory for array of permutation vars w.r.t. new variable ordering */
4290 /* Iterate over leaders and put the l-th leader to the l-th position of the lexicographic order.
4291 * We do this by swapping the l-th leader with the element at position l of the current permvars array. */
4453 /* create arrays for modified permutations in case we adapt the lexicographic order because of suborbitopes */
4468 SCIPdebugMsg(scip, "starting subgroup detection routine for %d components\n", propdata->ncomponents);
4504 /* set the first npermsincomp entries of genorder; the others are not used for this component */
4513 SCIPdebugMsg(scip, "component %d has %d permutations consisting of 2-cycles\n", i, ntwocycleperms);
4541 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "(%s,", SCIPvarGetName(propdata->permvars[k]));
4545 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%s,", SCIPvarGetName(propdata->permvars[j]));
4572 SCIPdebugMsg(scip, " created subgroup detection graph using %d of the permutations\n", nusedperms);
4613 norbitopesincomp = getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
4616 /* if there is just one orbitope satisfying the requirements, handle the full component by symresacks */
4628 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, propdata->perms[propdata->components[propdata->componentbegins[i] + k]],
4674 SCIPdebugMsg(scip, " color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
4726 SCIPdebugMsg(scip, " affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
4739 SCIPdebugMsg(scip, " detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
4746 * It might happen that we cannot generate the orbitope matrix if the orbitope is not generated by permutations
4747 * all having the same number of 2-cycles, e.g., the orbitope generated by (1,2)(4,5), (2,3), (5,6).
4760 /* adapt the first variable per color to be compatible with the created orbiope (upper left variable) */
4800 SCIP_CALL( addStrongSBCsSubgroup(scip, propdata, graphcompbegins, graphcomponents, largestcolorcomp,
4804 if ( ! SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
4851 SCIPdebugMsg(scip, " don't add weak sbcs because all generators were used or the settings forbid it\n");
4853 /* if suborbitopes or strong group actions have been found, potentially add symresacks adapted to
4874 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, modifiedperms[propdata->components[propdata->componentbegins[i] + k]],
4889 SCIPdebugMsg(scip, " add symresack for permutation %d of component %d adapted to suborbitope lexorder\n", k, i);
4930 /** sorts orbitope vars matrix such that rows are sorted increasingly w.r.t. minimum variable index in row;
5020 int* componentbegins, /**< array containing begin positions of components in components array */
5109 /* no or different number of 2-cycles or not all vars binary: permutations cannot generate orbitope */
5130 SCIP_CALL( SCIPallocBufferArray(scip, &orbitopevaridx[j], npermsincomponent + 1) ); /*lint !e866*/
5169 SCIP_CALL( SCIPgenerateOrbitopeVarsMatrix(scip, &vars, ntwocyclescomp, npermsincomponent + 1, permvars,
5170 npermvars, orbitopevaridx, columnorder, nusedelems, rowisbinary, &infeasibleorbitope, FALSE, NULL, NULL, NULL) );
5176 SCIPdebugMsg(scip, "found an orbitope of size %d x %d in component %d\n", ntwocyclescomp, npermsincomponent + 1, i);
5181 SCIP_CALL( SCIPsortOrbitope(scip, orbitopevaridx, vars, nbincyclescomp, npermsincomponent + 1) );
5224 SCIP_VAR** graphvars, /**< variables encoded in conflict graph (either all vars or permvars) */
5373 SCIP_Bool* success /**< pointer to store whether conflict graph could be created successfully */
5401 SCIPdebugMsg(scip, "Could not find setppc conshdlr --> construction of conflict graph aborted.\n");
5410 SCIPdebugMsg(scip, "No setppc constraints present --> construction of conflict graph aborted.\n");
5482 SCIPdebugMsg(scip, "Construction of conflict graph terminated; %d conflicts detected.\n", nedges);
5531 int* componentbegins, /**< array containing begin positions of components in components array */
5572 /* adapt natural variable order to a variable order that is compatible with Schreier Sims constraints */
5585 SCIP_CALL( adaptSymmetryDataSST(scip, perms, modifiedperms, nperms, permvars, modifiedpermvars, npermvars,
5651 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, modifiedperms[permidx], modifiedpermvars, npermvars, FALSE,
5656 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[permidx], permvars, npermvars, FALSE,
5700 SCIP_Shortbool* orbitvarinconflict, /**< indicator whether orbitvar is in conflict with orbit leader */
5734 /* variables in conflict with leader are fixed and not treated by a cut; trailing -1 to not count the leader */
5856 SCIP_HASHMAP* varmap, /**< map from variable to node label in conflict graph or NULL if useconflictgraph == FALSE */
5867 SCIP_Shortbool* orbitvarinconflict, /**< array to store whether a var in the orbit is conflicting with leader */
5868 int* norbitvarinconflict, /**< pointer to store number of vars in the orbit in conflict with leader */
5913 if ( leaderrule == (int) SCIP_LEADERRULE_FIRSTINORBIT || leaderrule == (int) SCIP_LEADERRULE_LASTINORBIT )
5981 leader = SCIPhashmapGetImageInt(varmap, permvars[orbits[orbitbegins[*orbitidx] + *leaderidx]]);
5987 if ( *success && tiebreakrule == (int) SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT && nconflictvars > 0 )
6055 leader = SCIPhashmapGetImageInt(varmap, permvars[orbits[orbitbegins[*orbitidx] + *leaderidx]]);
6288 /* initialize array indicating whether permutations shall not be considered for orbit permutations */
6339 SCIP_CALL( updateSymInfoConflictGraphSST(scip, conflictgraph, vars, nvars, permvars, npermvars, FALSE,
6344 if ( (leaderrule == SCIP_LEADERRULE_MAXCONFLICTSINORBIT || leaderrule == SCIP_LEADERRULE_MAXCONFLICTS)
6347 if ( (leaderrule == SCIP_LEADERRULE_MAXCONFLICTSINORBIT || leaderrule == SCIP_LEADERRULE_MAXCONFLICTS)
6352 if ( tiebreakrule == SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT && selectedtype != SCIP_VARTYPE_BINARY )
6357 permvars, npermvars, orbits, orbitbegins, norbits, propdata->sstleaderrule, propdata->ssttiebreakrule, selectedtype,
6358 &orbitidx, &orbitleaderidx, orbitvarinconflict, &norbitvarinconflict, conflictgraphcreated, &success) );
6364 assert( 0 <= orbitleaderidx && orbitleaderidx < orbitbegins[orbitidx + 1] - orbitbegins[orbitidx] );
6365 SCIPdebugMsg(scip, "%d\t\t%d\t\t%d\n", orbitidx, orbitleaderidx, orbitbegins[orbitidx + 1] - orbitbegins[orbitidx]);
6369 orbits, orbitbegins, orbitidx, orbitleaderidx, orbitvarinconflict, norbitvarinconflict, &nchanges, conflictgraphcreated) );
6371 ++norbitleadercomponent[propdata->vartocomponent[orbits[orbitbegins[orbitidx] + orbitleaderidx]]];
6395 /* if Schreier Sims constraints have been added, store that Schreier Sims has been used for this component */
6471 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
6475 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
6478 /* if there is no symmetry compatible with OF, check whether there are more general symmetries */
6486 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_INTEGER | SYM_SPEC_REAL, 0) );
6491 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_INTEGER | SYM_SPEC_REAL, 0) );
6500 SCIPdebugMsg(scip, "Symmetry propagator: problem is linear and no symmetry on binary variables has been found, turning symretope constraints off.\n");
6504 assert( hasNonlinearConstraints(propdata) || propdata->binvaraffected || propdata->sstenabled );
6514 SCIP_CALL( detectOrbitopes(scip, propdata, propdata->components, propdata->componentbegins, propdata->ncomponents) );
6532 if ( propdata->ncompblocked < propdata->ncomponents && propdata->detectsubgroups && propdata->symconsenabled )
6536 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &propdata->genlinconss, propdata->genlinconsssize) );
6559 SCIP_CALL( addSymresackConss(scip, prop, propdata->components, propdata->componentbegins, propdata->ncomponents) );
6562 /* free symmetry conss if no orbitope/symresack constraints have been found (may happen if Schreier-Sims constraints are active) */
6579 * Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the
6580 * stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that
6581 * has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be
6720 * The variables are added to bg1 and bg1list, which are prefilled with the variables globally fixed to 1.
6760 /* If we stopped due to a solving limit, it might happen that a non-root node has no domain changes, in all other
6859 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
6863 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
6865 assert( hasNonlinearConstraints(propdata) || propdata->binvaraffected || ! propdata->ofenabled );
6903 SCIP_CALL( computeBranchingVariables(scip, npermvars, propdata->permvarmap, bg1, bg1list, &nbg1) );
6958 /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
6961 (SCIPvarGetType(varv) == SCIP_VARTYPE_IMPLINT && SCIPvarGetType(varimg) == SCIP_VARTYPE_CONTINUOUS &&
6964 (SCIPvarGetType(varv) == SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(varimg) == SCIP_VARTYPE_IMPLINT &&
7017 /* check whether moved variables have the same type (might have been aggregated in the meanwhile) */
7020 (SCIPvarGetType(varv) == SCIP_VARTYPE_IMPLINT && SCIPvarGetType(varimg) == SCIP_VARTYPE_CONTINUOUS &&
7023 (SCIPvarGetType(varv) == SCIP_VARTYPE_CONTINUOUS && SCIPvarGetType(varimg) == SCIP_VARTYPE_IMPLINT &&
7040 * Note that variables globally fixed to 1 are not resetted, since the loop starts at propdata->nbg1. */
7052 orbits, orbitbegins, &norbits, components, componentbegins, vartocomponent, propdata->componentblocked, ncomponents, propdata->nmovedpermvars) );
7059 SCIPdebugMsg(scip, "Perform orbital fixing on %d orbits (%d active perms).\n", norbits, nactiveperms);
7060 SCIP_CALL( performOrbitalFixing(scip, permvars, nbinpermvars, orbits, orbitbegins, norbits, infeasible, &nfixedzero, &nfixedone) );
7081 /** presolving initialization method of propagator (called when presolving is about to begin) */
7102 else if ( SCIPgetNRuns(scip) > propdata->lastrestart && isSymmetryRecomputationRequired(scip, propdata) )
7120 /* otherwise compute symmetry if timing requests it; fix non-binary potential branching variables */
7123 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
7127 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
7136 /** presolving deinitialization method of propagator (called after presolving has been finished) */
7152 /* guarantee that symmetries are computed (and handled) if the solving process has not been interrupted
7154 if ( (propdata->symconsenabled || propdata->sstenabled) && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN )
7159 /* if timing requests it, guarantee that symmetries are computed even if presolving is disabled */
7160 if ( propdata->ofenabled && propdata->ofsymcomptiming <= 1 && SCIPgetStatus(scip) == SCIP_STATUS_UNKNOWN )
7165 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
7169 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
7204 assert( 0 <= propdata->addconsstiming && propdata->addconsstiming <= SYM_COMPUTETIMING_AFTERPRESOL );
7205 if ( propdata->addconsstiming > SYM_COMPUTETIMING_DURINGPRESOL && ! SCIPisPresolveFinished(scip) )
7237 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss - noldngenconns;
7243 SCIP_CALL( SCIPpresolCons(scip, propdata->genorbconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7244 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7245 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7250 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genorbconss[i]));
7257 SCIP_CALL( SCIPpresolCons(scip, propdata->genlinconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7258 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7259 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7264 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genlinconss[i]));
7273 SCIP_CALL( SCIPpresolCons(scip, propdata->sstconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7274 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7275 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7280 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->sstconss[i]));
7284 SCIPdebugMsg(scip, "Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
7290 assert( 0 <= propdata->ofsymcomptiming && propdata->ofsymcomptiming <= SYM_COMPUTETIMING_AFTERPRESOL );
7291 if ( propdata->ofenabled && propdata->performpresolving && propdata->ofsymcomptiming <= SYM_COMPUTETIMING_DURINGPRESOL )
7318 /* otherwise compute symmetry early if timing requests it; fix non-binary potential branching variables */
7321 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY, SYM_SPEC_INTEGER | SYM_SPEC_REAL) );
7325 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_REAL, SYM_SPEC_INTEGER) );
7370 else if ( SCIPgetNRuns(scip) > propdata->lastrestart && isSymmetryRecomputationRequired(scip, propdata) )
7416 {
7452 * Note that this is relatively difficult to obtain: One needs to include all bounds of variables that are responsible
7453 * for creating the orbit in which the variables that was propagated lies. This includes all variables that are moved
7572 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &(propdata->eventhdlr), EVENTHDLR_SYMMETRY_NAME, EVENTHDLR_SYMMETRY_DESC,
7586 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolSymmetry, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
7598 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
7644 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving)",
7650 "timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)",
7660 "recompute symmetries after a restart has occured? (0 = never, 1 = always, 2 = if OF found reduction)",
7690 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
7695 "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)",
7700 "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)",
7705 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: impl. int; 8: continuous);" \
7721 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
7742 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, SYMsymmetryGetName(), SYMsymmetryGetDesc()) );
7756 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix (or NULL)*/
7757 int*** permstrans, /**< pointer to store permutation generators as (npermvars x nperms) matrix (or NULL)*/
7759 SCIP_Bool* binvaraffected, /**< pointer to store whether binary variables are affected (or NULL) */
7761 int** componentbegins, /**< pointer to store begin positions of components in components array (or NULL) */
7762 int** vartocomponent, /**< pointer to store assignment from variable to its component (or NULL) */
7774 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:766
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:279
Definition: type_symmetry.h:63
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:5692
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
Definition: type_result.h:42
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:500
static SCIP_RETCODE propagateOrbitalFixing(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nprop)
Definition: prop_symmetry.c:6816
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5209
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:1773
Definition: type_symmetry.h:124
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:56
Definition: type_symmetry.h:56
Definition: type_symmetry.h:87
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11184
Definition: struct_scip.h:68
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:5528
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2496
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:5222
static SCIP_Bool isLeadervartypeCompatible(SCIP_VAR *var, int leadervartype)
Definition: prop_symmetry.c:717
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:886
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
static SCIP_DECL_TABLEFREE(tableFreeOrbitalfixing)
Definition: prop_symmetry.c:479
Definition: type_symmetry.h:57
SCIP_EXPR * SCIPexpriterGetParentDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:739
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3361
SCIP_Real SCIPgetLhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5361
int SCIPgetNVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5424
Definition: struct_var.h:160
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:7751
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:1734
Definition: type_symmetry.h:115
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
Definition: type_result.h:58
static SCIP_RETCODE addSSTConss(SCIP *scip, SCIP_PROPDATA *propdata, int *nchgbds)
Definition: prop_symmetry.c:6101
Definition: cons_setppc.h:89
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3382
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7730
Definition: type_result.h:47
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:499
SCIP_Real * SCIPgetBoundsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3424
static SCIP_RETCODE freeSymmetryData(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:802
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:104
Definition: type_symmetry.h:62
Definition: struct_misc.h:149
Definition: struct_var.h:207
Definition: struct_var.h:91
static SCIP_DECL_PROPRESPROP(propRespropSymmetry)
Definition: prop_symmetry.c:7458
static SCIP_RETCODE detectOrbitopes(SCIP *scip, SCIP_PROPDATA *propdata, int *components, int *componentbegins, int ncomponents)
Definition: prop_symmetry.c:5017
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:163
Definition: type_message.h:54
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4556
static SCIP_RETCODE freeConflictGraphSST(SCIP *scip, SCIP_DIGRAPH **conflictgraph, int nnodes)
Definition: prop_symmetry.c:5491
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3023
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
Definition: type_symmetry.h:89
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3708
Definition: type_var.h:62
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3141
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3766
int SCIPgetSymmetryNGenerators(SCIP *scip)
Definition: prop_symmetry.c:7851
Definition: cons_setppc.h:88
static SCIP_RETCODE SCIPsortOrbitope(SCIP *scip, int **orbitopevaridx, SCIP_VAR ***vars, int nrows, int ncols)
Definition: prop_symmetry.c:4935
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5326
SCIP_VAR ** SCIPgetVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13754
Definition: type_symmetry.h:61
Constraint handler for AND constraints, .
static SCIP_RETCODE detectAndHandleSubgroups(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:4414
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:447
SCIP_VAR * SCIPgetVarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5407
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:2662
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
static SCIP_RETCODE checkSymmetriesAreSymmetries(SCIP *scip, SYM_SPEC fixedtype, SYM_MATRIXDATA *matrixdata, int nperms, int **perms)
Definition: prop_symmetry.c:1409
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:83
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18461
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:682
static SCIP_DECL_PROPINITPRE(propInitpreSymmetry)
Definition: prop_symmetry.c:7084
static SCIP_RETCODE getActiveVariables(SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
Definition: prop_symmetry.c:1136
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
Definition: struct_tree.h:141
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
Definition: scip_datastructures.c:617
Definition: type_symmetry.h:86
Definition: prop_symmetry.c:553
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:2245
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:4004
public functions to work with algebraic expressions
Definition: struct_symmetry.h:44
interface for symmetry computations
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: scip_expr.c:1734
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3372
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:3169
Constraint handler for "or" constraints, .
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
static int getNSymhandableConss(SCIP *scip, SCIP_CONSHDLR *conshdlr_nonlinear)
Definition: prop_symmetry.c:1667
Definition: type_symmetry.h:58
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
Definition: struct_misc.h:137
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:263
static SCIP_RETCODE chooseOrderOfGenerators(SCIP *scip, SCIP_PROPDATA *propdata, int compidx, int **genorder, int *ntwocycleperms)
Definition: prop_symmetry.c:3354
SCIP_Real SCIPgetRhsVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5384
Definition: type_result.h:44
SCIP_Real * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linking.c:3733
Definition: struct_cons.h:46
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2567
SCIP_Bool SCIPisOrbitalfixingEnabled(SCIP *scip)
Definition: prop_symmetry.c:7831
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5206
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:6724
Definition: struct_cons.h:126
static SCIP_DECL_TABLEOUTPUT(tableOutputOrbitalfixing)
Definition: prop_symmetry.c:455
Definition: type_expr.h:700
void * SCIPdigraphGetNodeData(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7667
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Definition: type_lp.h:56
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:2352
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3739
Definition: type_symmetry.h:125
void SCIPdigraphSetNodeData(SCIP_DIGRAPH *digraph, void *dataptr, int node)
Definition: misc.c:7683
SCIP_RETCODE SCIPincludePropSymmetry(SCIP *scip)
Definition: prop_symmetry.c:7494
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4772
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8721
SCIP_VAR ** SCIPgetVarsLogicor(SCIP *scip, SCIP_CONS *cons)
Definition: cons_logicor.c:5447
static SCIP_DECL_HASHGETKEY(SYMhashGetKeyVartype)
Definition: prop_symmetry.c:498
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:3699
SCIP_EXPR * SCIPgetExprNonlinear(SCIP_CONS *cons)
Definition: cons_nonlinear.c:12262
internal miscellaneous methods
Definition: prop_symmetry.c:562
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11157
Definition: type_retcode.h:42
Definition: cons_setppc.h:87
Definition: type_stat.h:42
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:3910
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:1744
propagator for symmetry handling
Definition: type_result.h:51
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
Definition: struct_expr.h:202
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:5852
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:5367
SCIP_RETCODE SCIPcreateDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
Definition: scip_datastructures.c:654
static SCIP_RETCODE delSymConss(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:1033
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
Definition: misc.c:11254
static int getNOrbitopesInComp(SCIP_VAR **permvars, int *graphcomponents, int *graphcompbegins, int *compcolorbegins, int ncompcolors, int symcompsize)
Definition: prop_symmetry.c:4331
SCIP_RETCODE SCIPgetConsVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int varssize, SCIP_Bool *success)
Definition: scip_cons.c:2523
Definition: struct_prop.h:46
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2311
Definition: type_retcode.h:43
SCIP_Longint SCIPgetCapacityKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13674
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:1586
Definition: struct_expr.h:104
SCIP_VAR * SCIPgetVbdvarVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5430
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:7604
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7715
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:584
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:1716
Definition: type_var.h:64
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition: var.c:17177
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1416
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9454
constraint handler for nonlinear constraints specified by algebraic expressions
Definition: type_var.h:63
Definition: type_message.h:52
static SCIP_Bool checkSymmetryDataFree(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:668
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition: symmetry.c:533
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2482
SCIP_Bool SYMcanComputeSymmetry(void)
Definition: compute_symmetry_bliss.cpp:959
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition: var.c:17215
Definition: type_set.h:49
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:4249
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:857
SCIP_Real SCIPgetVbdcoefVarbound(SCIP *scip, SCIP_CONS *cons)
Definition: cons_varbound.c:5453
Definition: type_symmetry.h:126
Constraint handler for linear constraints in their most general form, .
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2557
SCIP_RETCODE SCIPvarGetOrigvarSum(SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: var.c:12782
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:995
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:970
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4633
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:636
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9431
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition: expriter.c:663
Definition: type_set.h:48
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:17851
Constraint handler for XOR constraints, .
SCIP_RETCODE SCIPprintNodeRootPath(SCIP *scip, SCIP_NODE *node, FILE *file)
Definition: scip_tree.c:529
Definition: struct_misc.h:89
Definition: type_symmetry.h:104
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:312
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5449
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18548
methods for handling symmetries
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
Definition: cons_linking.c:3664
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:311
SCIP_VAR * SCIPgetResultantOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2224
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1119
SCIP_EXPRITER_STAGE SCIPexpriterGetStageDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:695
SCIP_BOUNDTYPE * SCIPgetBoundtypesBounddisjunction(SCIP *scip, SCIP_CONS *cons)
Definition: cons_bounddisjunction.c:3403
SCIP_VAR * SCIPgetLinkvarLinking(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linking.c:3641
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3749
int SCIPgetNVarsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13731
public methods for data structures
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:167
Definition: type_retcode.h:54
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:1847
Definition: type_set.h:53
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2608
Definition: struct_symmetry.h:78
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:6586
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:1182
static SCIP_Bool hasNonlinearConstraints(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:1705
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
Definition: scip_general.c:713
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:3670
Definition: struct_misc.h:277
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18572
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:473
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
static SCIP_RETCODE setSymmetryMethodEnabledValues(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:775
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
Definition: cons_nonlinear.c:12790
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3105
Definition: type_retcode.h:52
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3230
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:247
constraint handler for bound disjunction constraints
void SCIPfreeDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset)
Definition: scip_datastructures.c:669
Definition: objbenders.h:43
static SCIP_Bool SymmetryFixVar(SYM_SPEC fixedtype, SCIP_VAR *var)
Definition: prop_symmetry.c:1115
SCIP_Longint * SCIPgetWeightsKnapsack(SCIP *scip, SCIP_CONS *cons)
Definition: cons_knapsack.c:13777
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:199
Definition: struct_misc.h:219
static SCIP_DECL_PROPEXITPRE(propExitpreSymmetry)
Definition: prop_symmetry.c:7139
Definition: struct_symmetry.h:101
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18524
static SCIP_DECL_HASHKEYVAL(SYMhashKeyValVartype)
Definition: prop_symmetry.c:543
static SCIP_RETCODE tryAddSymmetryHandlingConss(SCIP *scip, SCIP_PROP *prop, int *nchgbds, SCIP_Bool *earlyterm)
Definition: prop_symmetry.c:6424
static SCIP_Bool isSymmetryRecomputationRequired(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:746
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
Definition: cons_linear.c:18437
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:139
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:3432
Definition: type_result.h:48
Definition: struct_event.h:204
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:57
Definition: type_var.h:83
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:114
Definition: type_symmetry.h:59
Definition: type_var.h:67
Definition: type_symmetry.h:60