prop_symmetry.c
Go to the documentation of this file.
35 * - It allows to compute symmetries of the problem and to store this information in adequate form. The symmetry
39 * - (dynamic) orbitopal reduction, which generalizes (dynamic) orbital fixing. See symmetry_orbitopal.c
40 * - static orbitopal fixing (for binary variable domains) for full orbitopes. See cons_orbitope.c
41 * - static orbitopal fixing (for binary variable domains) for packing-partitioning orbitopes. See cons_orbitope.c
43 * - static lexicographic fixing for binary variable domains (i.e., symresack propagation). See cons_symresack.c
44 * - static lexicographic fixing for binary variable domains on involutions (i.e., orbisacks). See cons_orbisack.c
52 * We do not copy symmetry information, since it is not clear how this information transfers. Moreover, copying
53 * symmetry might inhibit heuristics. But note that solving a sub-SCIP might then happen without symmetry information!
58 * Many common methods are captured by a framework that dynamifies symmetry handling constraints. The ideas are
63 * This paper shows that various symmetry handling methods are compatible under certain conditions, and provides
64 * generalizations to common symmetry handling constraints from binary variable domains to arbitrary variable domains.
65 * This includes symresack propagation, orbitopal fixing, and orbital fixing, that are generalized to
66 * lexicographic reduction, orbitopal reduction and orbital reduction, respectively. For a description and
67 * implementation, see symmetry_lexred.c, symmetry_orbitopal.c and symmetry_orbital.c, respectively.
68 * The static counterparts on binary variable domains are cons_symresack.c and cons_orbisack.c for lexicographic
69 * reduction (cf. symresack propagation), and cons_orbitope.c and cons_orbisack.c for orbitopal reduction
70 * (cf. orbitopal fixing). We refer to the description of tryAddSymmetryHandlingMethods for the order in which these
76 * D. Salvagnin: Symmetry Breaking Inequalities from the Schreier-Sims table. CPAIOR 2018 Proceedings, 521-529, 2018.
78 * These inequalities are computed as follows. Throughout these procedure a set of so-called leaders is maintained.
79 * 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.
80 * the symmetry group of the mixed-integer program. For each variable \f$x_j\f$ in the orbit of \f$x_i\f$, the
81 * inequality \f$x_i \geq x_j\f$ is a valid symmetry handling inequality, which can be added to the mixed-integer
82 * 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
83 * compute the pointwise stabilizer of the leader set. In the next step, select a new variable, compute its orbit
84 * w.r.t. the stabilizer group of the leaders, add the inequalities based on this orbit, and add the new leader
85 * to the set of leaders. This procedure is iterated until the pointwise stabilizer group of the leaders has become
96 * @todo Order rows of orbitopes (in particular packing/partitioning) w.r.t. cliques in conflict graph.
104/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
146#define PROP_DELAY FALSE /**< should propagation method be delayed, if other propagators found reductions? */
148#define PROP_PRESOL_PRIORITY -10000000 /**< priority of the presolving method (>= 0: before, < 0: after constraint handlers) */
149#define PROP_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
150#define PROP_PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
154#define DEFAULT_MAXGENERATORS 1500 /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
155#define DEFAULT_CHECKSYMMETRIES FALSE /**< Should all symmetries be checked after computation? */
156#define DEFAULT_DISPLAYNORBITVARS FALSE /**< Should the number of variables affected by some symmetry be displayed? */
157#define DEFAULT_USECOLUMNSPARSITY FALSE /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
159#define DEFAULT_COMPRESSSYMMETRIES TRUE /**< Should non-affected variables be removed from permutation to save memory? */
160#define DEFAULT_COMPRESSTHRESHOLD 0.5 /**< Compression is used if percentage of moved vars is at most the threshold. */
162#define DEFAULT_ENFORCECOMPUTESYMMETRY FALSE /**< always compute symmetries, even if they cannot be handled */
167#define DEFAULT_CONSSADDLP TRUE /**< Should the symmetry breaking constraints be added to the LP? */
169#define DEFAULT_DETECTDOUBLELEX TRUE /**< Should we check whether the components of the symmetry group can be handled by double lex matrices? */
170#define DEFAULT_DETECTORBITOPES TRUE /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
171#define DEFAULT_DETECTSUBGROUPS TRUE /**< Should we try to detect orbitopes in subgroups of the symmetry group? */
172#define DEFAULT_ADDWEAKSBCS TRUE /**< Should we add weak SBCs for enclosing orbit of symmetric subgroups? */
173#define DEFAULT_ADDSTRONGSBCS FALSE /**< Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used? */
174#define DEFAULT_ADDCONSSTIMING 2 /**< timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) */
175#define DEFAULT_MAXNCONSSSUBGROUP 500000 /**< Maximum number of constraints up to which subgroup structures are detected */
176#define DEFAULT_USEDYNAMICPROP TRUE /**< whether dynamic propagation should be used for full orbitopes */
177#define DEFAULT_PREFERLESSROWS TRUE /**< Shall orbitopes with less rows be preferred in detection? */
178#define DEFAULT_HANDLESIGNEDORBITOPES TRUE /**< Should orbitopes on which proper signed permutations act be handled?" */
179#define DEFAULT_USESIMPLESGNCOMP TRUE /**< Should components consisting of a single full reflection be handled? */
182#define DEFAULT_SYMCOMPTIMING 2 /**< timing of symmetry computation (0 = before presolving, 1 = during presolving, 2 = at first call) */
183#define DEFAULT_PERFORMPRESOLVING 0 /**< Run orbital fixing during presolving? (disabled parameter) */
184#define DEFAULT_RECOMPUTERESTART 0 /**< Recompute symmetries after a restart has occurred? (0 = never) */
187#define DEFAULT_SSTTIEBREAKRULE 1 /**< index of tie break rule for selecting orbit for Schreier Sims constraints? */
188#define DEFAULT_SSTLEADERRULE 0 /**< index of rule for selecting leader variables for Schreier Sims constraints? */
189#define DEFAULT_SSTLEADERVARTYPE 6 /**< bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: continuous);
191#define DEFAULT_ADDCONFLICTCUTS TRUE /**< Should Schreier Sims constraints be added if we use a conflict based rule? */
193#define DEFAULT_SSTMIXEDCOMPONENTS TRUE /**< Should Schreier Sims constraints be added if a symmetry component contains variables of different types? */
194#define DEFAULT_MAXNNEWINVOLUS 100 /**< maximum number of newly generated involutions per symmetry component */
200#define TABLE_EARLIEST_SYMMETRY SCIP_STAGE_SOLVING /**< output of the statistics table is only printed from this stage onwards */
204#define MAXGENNUMERATOR INT_MAX /**< determine maximal number of generators by dividing this number by the number of variables */
205#define COMPRESSNVARSLB 25000 /**< lower bound on the number of variables above which compression could be performed */
206#define DEFAULT_NAUTYMAXLEVEL 10000 /**< terminate symmetry detection using Nauty when depth level of Nauty's search tree exceeds this number
231 int** permstrans; /**< pointer to store transposed permutation generators as (npermvars x nperms) matrix */
240 SCIP_Real* permvardomaincenter; /**< center of variable domains (needed for signed permutations) */
252 unsigned* componentblocked; /**< array to store which symmetry methods have been applied to a component using
254 SCIP_Bool* componenthassignedperm; /**< array to indicate whether a component has a signed permutation */
262 int maxgenerators; /**< limit on the number of generators that should be produced within symmetry detection (0 = no limit) */
264 SCIP_Bool displaynorbitvars; /**< Whether the number of variables in non-trivial orbits shall be computed */
265 SCIP_Bool compresssymmetries; /**< Should non-affected variables be removed from permutation to save memory? */
266 SCIP_Real compressthreshold; /**< Compression is used if percentage of moved vars is at most the threshold. */
270 SCIP_Bool usecolumnsparsity; /**< Should the number of conss a variable is contained in be exploited in symmetry detection? */
272 SCIP_Bool enforcecomputesymmetry; /**< always compute symmetries, even if they cannot be handled */
273 int symtiming; /**< timing of computing and handling symmetries (0 = before presolving, 1 = during presolving, 2 = after presolving) */
274 int maxnnewinvolus; /**< maximum number of newly generated involutions per symmetry component */
288 SCIP_Bool detectdoublelex; /**< Should we check whether the components of the symmetry group can be handled by double lex matrices? */
289 SCIP_Bool detectorbitopes; /**< Should we check whether the components of the symmetry group can be handled by orbitopes? */
290 SCIP_Bool detectsubgroups; /**< Should we try to detect orbitopes in subgroups of the symmetry group? */
291 SCIP_Bool addweaksbcs; /**< Should we add weak SBCs for enclosing orbit of symmetric subgroups? */
292 SCIP_Bool addstrongsbcs; /**< Should we add strong SBCs for enclosing orbit of symmetric subgroups if orbitopes are not used? */
296 int maxnconsssubgroup; /**< maximum number of constraints up to which subgroup structures are detected */
299 SCIP_Bool handlesignedorbitopes; /**< Should orbitopes on which proper signed permutations act be handled?" */
300 SCIP_Bool usesimplesgncomp; /**< Should components consisting of a single full reflection be handled? */
303 int recomputerestart; /**< Recompute symmetries after a restart has occurred? (0 = never, 1 = always, 2 = if symmetry reduction found) */
305 SCIP_Bool symfoundreduction; /**< whether symmetry handling propagation has found a reduction since the last time computing symmetries */
318 SCIP_Bool addconflictcuts; /**< Should Schreier Sims constraints be added if we use a conflict based rule? */
320 SCIP_Bool sstmixedcomponents; /**< Should Schreier Sims constraints be added if a symmetry component contains variables of different types? */
364 SCIP_DECL_SORTPTRCOMP((*compfunc)) /**< comparator function that was used to sort arr1 and arr2; must define a total ordering */
497 SCIPinfoMessage(scip, NULL, "Display permutations as signed permutations (allowing translations)\n");
508 SCIP_CALL( displayCycleOfSymmetry(scip, perm, symtype, i, covered, npermvars, propdata->permvars) );
551 SCIPinfoMessage(scip, NULL, " Symmetries of different components are displayed as permutations.\n\n");
553 SCIPinfoMessage(scip, NULL, " Symmetries of different components are displayed as permutations,\n"
554 " or signed permutations (allowing translations) if the component has signed permutations.\n\n");
564 for (p = propdata->componentbegins[c], cnt = 0; p < propdata->componentbegins[c + 1]; ++p, ++cnt)
571 SCIP_CALL( displayCycleOfSymmetry(scip, perm, symtype, i, covered, npermvars, propdata->permvars) );
626 SCIPinfoMessage(scip, NULL, "%sSymmetry information component %d\n", cidx == 0 ? "" : "\n", cidx);
767 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " #affected vars : %10d (%d bin, %d int, %d cont)\n",
772 SCIP_CALL( SCIPorbitopalReductionGetStatistics(scip, tabledata->propdata->orbitopalreddata, &nred, &ncutoff) );
773 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " orbitopal red. : %10d reductions applied,"
778 SCIP_CALL( SCIPorbitalReductionGetStatistics(scip, tabledata->propdata->orbitalreddata, &nred, &ncutoff) );
779 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " orbital reduction: %10d reductions applied,"
784 SCIP_CALL( SCIPlexicographicReductionGetStatistics(scip, tabledata->propdata->lexreddata, &nred, &ncutoff) );
785 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, file, " lexicographic red: %10d reductions applied,"
790 time = SCIPgetShadowTreeEventHandlerExecutionTime(scip, tabledata->propdata->shadowtreeeventhdlr);
821 SCIP_CALL( SCIPcreateDatatreeInTree(scip, symmetry_stats, &orbitopal_red, "orbitopalreduction", 2) );
823 SCIP_CALL( SCIPorbitopalReductionGetStatistics(scip, tabledata->propdata->orbitopalreddata, &nred, &ncutoff) );
832 SCIP_CALL( SCIPcreateDatatreeInTree(scip, symmetry_stats, &orbital_red, "orbital_reduction", 2) );
834 SCIP_CALL( SCIPorbitalReductionGetStatistics(scip, tabledata->propdata->orbitalreddata, &nred, &ncutoff) );
843 SCIP_CALL( SCIPcreateDatatreeInTree(scip, symmetry_stats, &lex_red, "lexicographicreduction", 2) );
845 SCIP_CALL( SCIPlexicographicReductionGetStatistics(scip, tabledata->propdata->lexreddata, &nred, &ncutoff) );
853 SCIP_Real time = SCIPgetShadowTreeEventHandlerExecutionTime(scip, tabledata->propdata->shadowtreeeventhdlr);
1009 * then by their rhs, then by their total number of nodes, then by the number of operator nodes,
1278/** makes sure that the constraint array (potentially NULL) of given array size is sufficiently large */
1334 int* nmovedvars, /**< pointer to store number of vars affected by symmetry (if usecompression) or NULL */
1335 SCIP_Bool* binvaraffected, /**< pointer to store whether a binary variable is affected by symmetry */
1337 SCIP_Real compressthreshold, /**< if percentage of moved vars is at most threshold, compression is done */
1410 /* iterate over labels and adapt permutation (possibly taking signed permutations into account) */
1456 /* detect whether binary variable is affected by symmetry and count number of binary permvars */
1521/** returns whether all constraint handlers with constraints can provide symmetry information */
1542 if ( ! conshdlrCanProvideSymInformation(conshdlr, symtype) && SCIPconshdlrGetNConss(conshdlr) > 0 )
1552 " Symmetry detection interrupted: constraints of type %s do not provide symmetry information.\n"
1594 SCIPwarningMessage(scip, "Expression handler %s does not implement the EXPRGETSYMDATA callback.\n"
1595 "Computed symmetries might be incorrect if the expression uses different constants or assigns\n"
1811 SCIP_CALL( displayCycleOfSymmetry(scip, perms[p], symtype, i, covered, npermvars, SCIPgetVars(scip)) );
1849 SCIPinfoMessage(scip, NULL, "\tconstraint is %ssymmetric to constraint %d\n\t", !found ? "not " : "", d);
1890 SCIP_Bool compresssymmetries, /**< Should non-affected variables be removed from permutation to save memory? */
1891 SCIP_Real compressthreshold, /**< if percentage of moved vars is at most threshold, compression is done */
1906 SCIP_Bool* binvaraffected, /**< pointer to store whether a binary variable is affected by symmetry */
2000 || (symtype == SYM_SYMTYPE_SIGNPERM && SCIPgetSymgraphNVarcolors(graph) == 2 * SCIPgetNVars(scip)) )
2014 SCIP_CALL( checkSymmetriesAreSymmetries(scip, symtype, *perms, *nperms, SCIPgetNVars(scip), fixedtype) );
2024 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &vars, SCIPgetVars(scip), nvars) ); /*lint !e666*/
2026 SCIP_CALL( setSymmetryData(scip, symtype, vars, nvars, SCIPgetNBinVars(scip), permvars, npermvars, nbinpermvars,
2097 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(propdata->componenthassignedperm), ncomponents) );
2108 if ( isNonstandardPerm(scip, propdata->perms[components[i]], propdata->permvars, propdata->npermvars) )
2143 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation started\n", SCIPgetSolvingTime(scip));
2146 SCIP_CALL( SCIPcomputeComponentsSym(scip, (SYM_SYMTYPE) propdata->symtype, propdata->perms, propdata->nperms,
2147 propdata->permvars, propdata->npermvars, FALSE, &propdata->components, &propdata->componentbegins,
2151 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) component computation finished\n", SCIPgetSolvingTime(scip));
2249 /* check for inferred binary variables among integers and continuous implied integral variables */
2305/** returns whether any allowed symmetry handling method is effective for the problem instance */
2340 if ( ISSSTCONTACTIVE(propdata->sstleadervartype) && SCIPgetNContVars(scip) > 0 ) /*lint !e641*/
2360 SYM_SPEC symspecrequire, /**< symmetry specification for which we need to compute symmetries */
2361 SYM_SPEC symspecrequirefixed /**< symmetry specification of variables which must be fixed by symmetries */
2387 " Deactivated symmetry handling methods, since SCIP was built without symmetry detector (SYM=none).\n");
2410 /* count implicit integer variables as real variables, since we cannot currently handle integral variables well */
2418 " (%.1fs) symmetry computation skipped: type (bin %c, int %c, cont %c) does not match requirements (bin %c, int %c, cont %c).\n",
2442 " (%.1fs) symmetry computation started: requiring (bin %c, int %c, cont %c), (fixed: bin %c, int %c, cont %c)\n",
2478 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) could not compute symmetry\n", SCIPgetSolvingTime(scip));
2487 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) no symmetry present (symcode time: %.2f)\n", SCIPgetSolvingTime(scip), symcodetime);
2495 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " (%.1fs) symmetry computation finished: %d generators found (max: ",
2505 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", log10 of symmetry group size: %.2f", propdata->log10groupsize);
2511 SCIP_CALL( SCIPdetermineNVarsAffectedSym(scip, propdata->perms, propdata->nperms, propdata->permvars,
2514 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, ", number of affected variables: %d)\n", propdata->nmovedvars);
2533/** Checks whether given set of 2-cycle permutations forms an orbitope and if so, builds the variable index matrix.
2535 * If @p activevars == NULL, then the function assumes all permutations of the component are active and therefore all
2538 * We need to keep track of the number of generated columns, because we might not be able to detect all orbitopes.
2539 * 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
2634 /* in the subgroup case it might happen that a generator has less than ntwocycles many 2-cyles */
2677 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
2714 j = 0; /*lint !e850*/ /* reset j since previous permutations can now intersect with the latest added column */
2737 int* ntwocycleperms /**< pointer to store the number of 2-cycle permutations in component compidx */
2779 SCIP_CALL( SCIPisInvolutionPerm(perm, propdata->permvars, npermvars, &(ntwocycles[i]), &nbincycles, FALSE) );
2805 * After execution, @p graphcomponents contains all permvars sorted by their color and component,
2806 * @p graphcompbegins points to the indices where new components in @p graphcomponents start and
2816 int** graphcomponents, /**< buffer to store the components of the graph (ordered var indices) */
2889 /* iteratively handle each swap of perm until an invalid one is found or all edges have been added */
2909 /* another permutation has already merged these variables into one component; store its color */
2928 /* a generator is not allowed to connect two components of the same color, since they depend on each other */
2996 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, k)) == firstcolor );
2997 assert( SCIPdisjointsetFind(comptocolor, SCIPdisjointsetFind(vartocomponent, img)) == firstcolor );
3007 * disjoint sets to the arrays graphcomponents, graphcompbegins, and compcolorbegins (see above).
3185 /* it might happen that we cannot detect the orbitope if it is generated by permutations with different
3225 for (k = compcolorbegins[graphcoloridx]; k < compcolorbegins[graphcoloridx+1] && (*compidxfirstrow) < 0; ++k)
3237 /* iterate over all columns (elements in orbit), because we cannot see from ngencols which columns
3267 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "suborbitope_%d_%d", graphcoloridx, propdata->norbitopes);
3278 SCIPinfoMessage(scip, NULL, " detected subgroup acting as symmetric group on columns of %d x %d matrix\n",
3310 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
3363 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "strong_sbcs_%s_%s", SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
3403 SCIP_Bool storelexorder, /**< whether the lexicographic order induced by the orbitope shall be stored */
3460 assert( ! SCIPhashmapExists(varsinlexorder, (void*) (size_t) (*lexorder)[k]) ); /* Use int as pointer */
3465 /* We will store the newest and the largest orbit and activeorb will be used to mark at which entry of the array
3488 /* if the first variable was already contained in another orbit or if there are no variables left anyway, skip the
3537 SCIPdebugMsg(scip, " adding %d weak sbcs for enclosing orbit of color %d.\n", orbitsize[activeorb]-1, chosencolor);
3549 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "weak_sbcs_%d_%s_%s", symgrpcompidx, SCIPvarGetName(vars[0]), SCIPvarGetName(vars[1]));
3569 SCIPinfoMessage(scip, NULL, " use %d SST cuts for leader %s\n", orbitsize[activeorb] - 1, SCIPvarGetName(vars[0]));
3594 /* the leader of the weak inequalities has to be the first element in the lexicographic order */
3642 SCIP_VAR** modifiedpermvars, /**< memory for array of permutation vars w.r.t. new variable ordering */
3678 /* Iterate over leaders and put the l-th leader to the l-th position of the lexicographic order.
3679 * We do this by swapping the l-th leader with the element at position l of the current permvars array. */
3863 /* create arrays for modified permutations in case we adapt the lexicographic order because of suborbitopes */
3882 /* set the first npermsincomp entries of genorder; the others are not used for this component */
3891 SCIPdebugMsg(scip, "component %d has %d permutations consisting of 2-cycles\n", cidx, ntwocycleperms);
3920 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "(%s,", SCIPvarGetName(propdata->permvars[k]));
3924 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "%s,", SCIPvarGetName(propdata->permvars[j]));
3951 SCIPdebugMsg(scip, " created subgroup detection graph using %d of the permutations\n", nusedperms);
3989 norbitopesincomp = getNOrbitopesInComp(propdata->permvars, graphcomponents, graphcompbegins, compcolorbegins,
3992 /* if there is just one orbitope satisfying the requirements, handle the full component by symresacks */
3999 SCIPinfoMessage(scip, NULL, " detected subgroup acting as symmetric group on columns of 1 x %d matrix\n",
4001 SCIPinfoMessage(scip, NULL, " use %d orbisack constraints to handle column permutations\n", npermsincomp);
4060 SCIPdebugMsg(scip, " color %d has %d components with overall %d variables\n", j, compcolorbegins[j+1] - compcolorbegins[j],
4112 SCIPdebugMsg(scip, " affected types (bin,int,cont): (%d,%d,%d)\n", binaffected, intaffected, contaffected);
4125 SCIPdebugMsg(scip, " detected an orbitope with %d rows and %d columns\n", nbinarycomps, largestcompsize);
4132 * It might happen that we cannot generate the orbitope matrix if the orbitope is not generated by permutations
4133 * all having the same number of 2-cycles, e.g., the orbitope generated by (1,2)(4,5), (2,3), (5,6).
4146 /* adapt the first variable per color to be compatible with the created orbiope (upper left variable) */
4186 SCIP_CALL( addStrongSBCsSubgroup(scip, propdata, graphcompbegins, graphcomponents, largestcolorcomp,
4190 if ( ! SCIPvarIsBinary(propdata->permvars[graphcomponents[graphcompbegins[largestcolorcomp]]]) )
4237 SCIPdebugMsg(scip, " don't add weak sbcs because all generators were used or the settings forbid it\n");
4239 /* if suborbitopes or strong group actions have been found, potentially add symresacks adapted to
4292 SCIPdebugMsg(scip, " add symresack for permutation %d of component %d adapted to suborbitope lexorder\n", k, cidx);
4400 * These lists are sorted (by the address of the constraint), so we only need to check for each i, j in the orbit
4421 /* Check if i and j are overlapping in some clique, where only one of the two could have value 1.
4424 * @todo A better sorted order would be: First constraints with large variables (higher hitting probability)
4524 SCIPdebugMsg(scip, "\tIdentify edges for clique ID: %u; Index: %d).\n", SCIPcliqueGetId(clique),
4551 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*varconflicts)[i].cliques, (*varconflicts)[i].ncliques) );
4594 /* sort the variable cliques by the address, so checkSortedArraysHaveOverlappingEntry can detect intersections */
4597 SCIPsortPtr((void**)(*varconflicts)[i].cliques, sortByPointerValue, (*varconflicts)[i].ncliques);
4610 SCIPdebugMsg(scip, "Construction of conflict graph terminated; %d variable-clique combinations detected.\n",
4707 /* adapt natural variable order to a variable order that is compatible with Schreier Sims constraints */
4720 SCIP_CALL( adaptSymmetryDataSST(scip, perms, modifiedperms, nperms, permvars, modifiedpermvars, npermvars,
4742 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, modifiedperms[permidx], modifiedpermvars, npermvars, FALSE,
4747 SCIP_CALL( SCIPcreateSymbreakCons(scip, &cons, name, perms[permidx], permvars, npermvars, FALSE,
4794 SCIP_Shortbool* orbitvarinconflict, /**< indicator whether orbitvar is in conflict with orbit leader */
4827 /* variables in conflict with leader are fixed and not treated by a cut; trailing -1 to not count the leader */
4843 SCIPinfoMessage(scip, NULL, " use %d SST cuts for leader %s of type ", orbitsize - 1, SCIPvarGetName(leadervar));
4908 /* for signed permutations, we need to adapt the rhs of SST cuts (artificially center variables at 0) */
4910 rhs = propdata->permvardomaincenter[orbits[poscur]] - propdata->permvardomaincenter[orbits[posleader]];
4964 SCIP_CONFLICTDATA* varconflicts, /**< variable conflicts structure, or NULL if we do not use it */
4975 SCIP_Shortbool* orbitvarinconflict, /**< array to store whether a var in the orbit is conflicting with leader */
4976 int* norbitvarinconflict,/**< pointer to store number of vars in the orbit in conflict with leader */
5010 if ( leaderrule == (int) SCIP_LEADERRULE_FIRSTINORBIT || leaderrule == (int) SCIP_LEADERRULE_LASTINORBIT )
5208 SCIP_Bool onlywithcontvars, /**< only handle components that contain continuous variables with SST */
5347 /* loop terminated naturally, so component does not have continuous or implicitly integer variables. */
5376 /* initialize array indicating whether permutations shall not be considered for orbit permutations */
5433 SCIP_CALL( updateSymInfoConflictGraphSST(scip, varconflicts, permvars, npermvars, orbits, orbitbegins,
5440 if ( leaderrule == SCIP_LEADERRULE_MAXCONFLICTSINORBIT && selectedtype != SCIP_VARTYPE_BINARY )
5444 if ( tiebreakrule == SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT && selectedtype != SCIP_VARTYPE_BINARY )
5448 SCIP_CALL( selectOrbitLeaderSSTConss(scip, varconflicts, permvars, npermvars, orbits, orbitbegins, norbits,
5456 assert( 0 <= orbitleaderidx && orbitleaderidx < orbitbegins[orbitidx + 1] - orbitbegins[orbitidx] );
5457 SCIPdebugMsg(scip, "%d\t\t%d\t\t%d\n", orbitidx, orbitleaderidx, orbitbegins[orbitidx + 1] - orbitbegins[orbitidx]);
5461 orbits, orbitbegins, orbitidx, orbitleaderidx, orbitvarinconflict, norbitvarinconflict, &nchanges) );
5483 /* if Schreier Sims constraints have been added, store that Schreier Sims has been used for this component */
5555 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_1row_comp_%d_col%d", partialname, componentid, i);
5560 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 2, consvars, conscoefs, -SCIPinfinity(scip), 0.0,
5561 propdata->conssaddlp, propdata->conssaddlp, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE ) );
5571 /* for only 2 columns, the the component can be completely handled by lexicographic reduction */
5601 SCIP_CALL( SCIPisPackingPartitioningOrbitope(scip, varmatrix, nrows, ncols, &pprows, &npprows, &type) );
5634 SCIP_CALL( SCIPcreateConsOrbitope(scip, &cons, name, ppvarsarrayonlypprows, SCIP_ORBITOPETYPE_PACKING,
5643 /* @todo we add orbitopes to the dynamically sized array `genlinconss` instead of `genorbconss` to ensure
5697/** applies pp-orbitope upgrade if at least 50% of the permutations in a component correspond to pp-orbisacks */
5774 /* For each permvar, introduce an array of setppc constraints (initially NULL) for each variable,
5775 * and populate it with the setppc constraints that it contains. This array follows the ordering by cons ptr address.
5800 &(permvarssetppcconss[varid]), &maxnpermvarssetppcconss[varid], npermvarssetppcconss[varid] + 1) );
5807 /* for all permutations, test involutions on binary variables and test if they are captured by setppc conss */
5825 assert( ( SCIPgetSymInferredVarType(propdata->permvars[i]) == SCIPgetSymInferredVarType(propdata->permvars[j]) ) );
5831 /* i and j are a two-cycle, so we find this once for i and once for j. Only handle this once for i < j. */
5835 if ( !checkSortedArraysHaveOverlappingEntry((void**) permvarssetppcconss[i], npermvarssetppcconss[i],
5841 /* The permutation qualifies if all binary variables are either a reflection or in a 2-cycle. There must be at
5856 /* if at least 50% of such permutations are packing-partitioning type, apply packing upgrade */
5889 assert( SCIPgetSymInferredVarType(propdata->permvars[i]) == SCIPgetSymInferredVarType(propdata->permvars[j]) );
5893 assert( checkSortedArraysHaveOverlappingEntry((void**) permvarssetppcconss[i], npermvarssetppcconss[i],
5906 SCIP_CALL( SCIPcreateConsOrbitope(scip, &cons, name, ppvarsmatrix, SCIP_ORBITOPETYPE_PACKING, nrows, 2,
5912 /* @todo we add orbitopes to the dynamically sized array `genlinconss` instead of `genorbconss` to ensure
5981 /* in this function orbital reduction or dynamic lexicographic reduction propagation must be enabled */
5983 checklexred = ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks;
5998 for (p = propdata->componentbegins[cidx]; p < propdata->componentbegins[cidx] + componentsize; ++p)
6009 componentperms[p] = propdata->perms[propdata->components[propdata->componentbegins[cidx] + p]];
6015 * 1. Get the checkpporbisack param from the parameter hashset. This returns NULL if it is not initialized,
6017 * 2. If the param is not NULL, then we only do the packing-partitioning upgrade step if its value is TRUE.
6018 * Packing-partitioning orbitopes are only implemented for binary orbitopes, so binary variables must be moved.
6028 properperms, nproperperms, FALSE /* we filter proper permutations */, &success, &naddedconss) );
6058 /* handle every permutation in the component with the dynamic lexicographic reduction propagator */
6062 propdata->permvars, propdata->npermvars, componentperms != NULL ? componentperms[p] : properperms[p],
6069 SCIPinfoMessage(scip, NULL, " use lexicographic reduction for %d permutations\n", componentsize);
6080 for (p = propdata->componentbegins[cidx]; p < propdata->componentbegins[cidx + 1] && ! found; ++p)
6089 /* we have found a signed permutation that reflects all variables (the identity is not in perms) */
6180 * Since SST is compatible with static symresacks, the propdata->ncompblocked counter is not the number of
6362 SCIPinfoMessage(scip, NULL, " use static orbitopal reduction on %d x %d matrix\n", nrows, ncols);
6389 /* enforce constraints to be in LP since this seems to have a positive impact for orbitopes with cont. vars */
6390 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 2, consvars, consvals, -SCIPinfinity(scip), 0.0,
6424 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 1, consvars, coef, bound, -SCIPinfinity(scip),
6443 SCIP_CALL( addOrbitopesDynamic(scip, propdata, componentid, partialname, varidxmatrix, nrows, ncols, success) );
6476 SCIP_CALL( SCIPcreateConsOrbitope(scip, &cons, partialname, orbitopematrix, SCIP_ORBITOPETYPE_FULL,
6569 SCIPinfoMessage(scip, NULL, " use static orbitopal reduction on %d x %d matrix\n", nrows, ncols);
6588 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 2, consvars, consvals, -SCIPinfinity(scip), 0.0,
6666 SCIP_CALL( SCIPcreateConsLinear(scip, &cons, name, 1, consvars, coef, bound, -SCIPinfinity(scip),
6805 * (2) If there are multiple column- and row-blocks, just handle classical permutation symmetries.
6817 /* check whether orbitopes can be used to handle column and row swaps (requires equally centered rows/columns) */
6818 if ( isEquallyCenteredOrbitope(scip, propdata->permvardomaincenter, varidxmatrix, 0, nrows, 0, ncols, TRUE) )
6820 if ( isEquallyCenteredOrbitope(scip, propdata->permvardomaincenter, varidxmatrix, 0, nrows, 0, ncols, FALSE) )
6826 /* check whether the signed permutations flip entries within a single column of the orbitope matrix */
6842 /* check whether the signed permutations flip entries within a single column of transposed orbitope matrix */
6919 /* if no symmetries have been handled yet, handle column and row symmetries without signed permutations */
6944 (void) SCIPsnprintf(partialname, SCIP_MAXSTRLEN, "orbitope_component_%d_doublelex_col_%d", id, p);
6946 SCIP_CALL( handleOrbitope(scip, propdata, id, orbitopematrix, nrows, j, partialname, FALSE, TRUE,
6968 (void) SCIPsnprintf(partialname, SCIP_MAXSTRLEN, "orbitope_component_%d_doublelex_row_%d", id, p);
6970 SCIP_CALL( handleOrbitope(scip, propdata, id, orbitopematrix, ncols, i, partialname, FALSE, TRUE,
7047 SCIP_CALL( SCIPdetectSingleOrDoubleLexMatrices(scip, detectsinglelex, perms, nselectedperms, propdata->npermvars,
7087 /* signed permutations can only handle the orbitope if all variables per row have the same domain center */
7090 if ( ! isEquallyCenteredOrbitope(scip, propdata->permvardomaincenter, lexmatrix, 0, nrows, 0, ncols, TRUE) )
7109 /* check whether the signed permutations flip entries within a single column of the orbitope matrix
7116 SCIP_CALL( hasOrbitopeColumnFlip(lexmatrix, 0, nrows, 0, ncols, perms[p], propdata->npermvars, FALSE,
7161 /* if we have not handled the orbitope yet, handle it as unsigned orbitope and the orbitope is large */
7229 if ( !propdata->usedynamicprop && ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->detectsubgroups
7357 permlen = propdata->symtype == (int)SYM_SYMTYPE_PERM ? propdata->npermvars : 2 * propdata->npermvars;
7416 * (also for signed permutations, it is sufficient to iterate over the first propdata->npermvars
7474 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->perms, propdata->nmaxperms, nnewperms) );
7491 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->permstrans[i], propdata->nmaxperms, nnewperms) );
7499 /* shift components array by nnewinvols positions for all components later than the current one */
7500 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->components, propdata->nperms, nnewperms) );
7513 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &propdata->isproperperm, propdata->nperms, nnewperms) );
7546 * 1. If orbitope detection is enabled and the component is an orbitope: Apply one of the following:
7553 * 1.1.4. If none of these standard cases apply, use dynamic orbitopal reduction; cf. symmetry_orbitopal.c
7554 * 1.2. If static symmetry handling methods are used: Use static orbitopal fixing (binary variables only);
7556 * 2. If no dynamic symmetry handling methods are used, and if (orbitopal) subgroup detection is enabled,
7558 * 3. Otherwise, if orbital reduction is enabled, or if dynamic methods are enabled and lexicographic reduction
7561 * 3.2. And, if dynamic methods and lexicographic for single permutations reduction are enabled, use that.
7563 * 5. Otherwise, if possible, add symresacks (lexicographic reduction on binary variables using a static ordering).
7618 /* only run SST cuts on continuous variables orbital reduction or lexicographic reduction is active */
7620 || ( ISSYMRETOPESACTIVE(propdata->usesymmetry) && propdata->usedynamicprop && propdata->addsymresacks );
7692 SCIP_CALL( determineSymmetry(scip, propdata, SYM_SPEC_BINARY | SYM_SPEC_INTEGER | SYM_SPEC_REAL, 0) );
7760 SCIP_CALL( SCIPorbitopalReductionPropagate(scip, propdata->orbitopalreddata, infeasible, &nredlocal, &didrunlocal) );
7767 SCIP_CALL( SCIPorbitalReductionPropagate(scip, propdata->orbitalreddata, infeasible, &nredlocal, &didrunlocal) );
7774 SCIP_CALL( SCIPlexicographicReductionPropagate(scip, propdata->lexreddata, infeasible, &nredlocal, &didrunlocal) );
7788/** presolving initialization method of propagator (called when presolving is about to begin) */
7826/** presolving deinitialization method of propagator (called after presolving has been finished) */
7846 /* guarantee that symmetries are computed (and handled) if the solving process has not been interrupted
7857/** solving process deinitialization method of propagator (called before branch and bound process data is freed) */
7940 *naddconss += propdata->ngenorbconss + propdata->ngenlinconss + propdata->nsstconss - noldngenconns;
7946 SCIP_CALL( SCIPpresolCons(scip, propdata->genorbconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7947 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7948 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7953 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genorbconss[i]));
7960 SCIP_CALL( SCIPpresolCons(scip, propdata->genlinconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7961 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7962 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7967 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->genlinconss[i]));
7976 SCIP_CALL( SCIPpresolCons(scip, propdata->sstconss[i], nrounds, SCIP_PROPTIMING_ALWAYS, nnewfixedvars, nnewaggrvars, nnewchgvartypes,
7977 nnewchgbds, nnewholes, nnewdelconss, nnewaddconss, nnewupgdconss, nnewchgcoefs, nnewchgsides, nfixedvars, naggrvars,
7978 nchgvartypes, nchgbds, naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result) );
7983 SCIPdebugMsg(scip, "Presolving constraint <%s> detected cutoff or unboundedness.\n", SCIPconsGetName(propdata->sstconss[i]));
7987 SCIPdebugMsg(scip, "Presolved %d generated Schreier Sims constraints.\n", propdata->nsstconss);
8018 /* usesymmetry must be read and non-zero in order for propdata to have initialized symmetry handling propagators */
8076 * Note that this is relatively difficult to obtain: One needs to include all bounds of variables that are responsible
8077 * for creating the orbit in which the variables that was propagated lies. This includes all variables that are moved
8205 SCIP_CALL( SCIPsetPropPresol(scip, prop, propPresolSymmetry, PROP_PRESOL_PRIORITY, PROP_PRESOL_MAXROUNDS, PROP_PRESOLTIMING) );
8217 "limit on the number of generators that should be produced within symmetry detection (0 = no limit)",
8253 "Should we check whether the components of the symmetry group can be handled by double lex matrices?",
8273 "timing of adding constraints (0 = before presolving, 1 = during presolving, 2 = after presolving) [disabled parameter]",
8279 "timing of symmetry computation (0 = before presolving, 1 = during presolving, 2 = at first call) [disabled parameter]",
8319 "Should strong SBCs for enclosing orbit of symmetric subgroups be added if orbitopes are not used?",
8324 "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)",
8329 "rule to select the leader in an orbit (0: first var; 1: last var; 2: var having most conflicting vars in orbit)",
8334 "bitset encoding which variable types can be leaders (1: binary; 2: integer; 4: continuous);" \
8350 "Should Schreier Sims constraints be added if a symmetry component contains variables of different types?",
8355 "Whether all non-binary variables shall be not affected by symmetries if OF is active? (disabled)",
8385 "timing of symmetry computation and handling (0 = before presolving, 1 = during presolving, 2 = after presolving)",
8398 "terminate symmetry detection using Nauty when depth level of Nauty's search tree exceeds this number (-1: unlimited)",
8405 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, SYMsymmetryGetName(), SYMsymmetryGetDesc()) );
8408 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, SYMsymmetryGetAddName(), SYMsymmetryGetAddDesc()) );
8419 SCIP_CALL( SCIPincludeOrbitalReduction(scip, &propdata->orbitalreddata, propdata->shadowtreeeventhdlr) );
8422 SCIP_CALL( SCIPincludeLexicographicReduction(scip, &propdata->lexreddata, propdata->shadowtreeeventhdlr) );
8436 int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix (or NULL)*/
8437 int*** permstrans, /**< pointer to store permutation generators as (npermvars x nperms) matrix (or NULL)*/
8439 SCIP_Bool* binvaraffected, /**< pointer to store whether binary variables are affected (or NULL) */
8441 int** componentbegins, /**< pointer to store begin positions of components in components array (or NULL) */
8442 int** vartocomponent, /**< pointer to store assignment from variable to its component (or NULL) */
8454 assert( ncomponents != NULL || (components == NULL && componentbegins == NULL && vartocomponent == NULL) );
8504 if ( components != NULL || componentbegins != NULL || vartocomponent != NULL || ncomponents != NULL )
8568 SCIPinfoMessage(scip, NULL, "Cannot display symmetries. Symmetries have not been computed yet.\n");
8605 SCIPerrorMessage("Cannot create operator node type, symmetry propagator has not been included.\n");
8619 SCIP_CALL( SCIPhashmapInsertInt(propdata->customsymopnodetypes, (void*) opnodename, propdata->nopnodetypes) );
8643 SCIPerrorMessage("Cannot return operator node type, symmetry propagator has not been included.\n");
interface for symmetry computations
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
Definition: compute_symmetry_bliss.cpp:627
const char * SYMsymmetryGetAddName(void)
Definition: compute_symmetry_bliss.cpp:170
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *graph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
Definition: compute_symmetry_bliss.cpp:405
SCIP_Bool SYMcanComputeSymmetry(void)
Definition: compute_symmetry_bliss.cpp:148
const char * SYMsymmetryGetAddDesc(void)
Definition: compute_symmetry_bliss.cpp:176
Constraint handler for AND constraints, .
constraint handler for bound disjunction constraints
constraint handler for indicator constraints
Constraint handler for knapsack constraints of the form , x binary and .
Constraint handler for linear constraints in their most general form, .
constraint handler for linking binary variables to a linking (continuous or integer) variable
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
constraint handler for nonlinear constraints specified by algebraic expressions
Constraint handler for "or" constraints, .
SCIP_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nrows, int ncols, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool checkpporbitope, 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:131
interface for constraint handlers of type partitioning, packing, and full
Constraint handler for the set partitioning / packing / covering constraints .
constraint handler for SOS type 1 constraints
constraint handler for SOS type 2 constraints
constraint handler for symresack constraints
Constraint handler for variable bound constraints .
Constraint handler for XOR constraints, .
SCIP_Real SCIPgetShadowTreeEventHandlerExecutionTime(SCIP *scip, SCIP_EVENTHDLR *eventhdlr)
Definition: event_shadowtree.c:123
SCIP_RETCODE SCIPincludeEventHdlrShadowTree(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr)
Definition: event_shadowtree.c:663
power and signed power expression handlers
product expression handler
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:1731
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9619
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9642
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:17755
int SCIPdisjointsetGetComponentCount(SCIP_DISJOINTSET *djset)
Definition: misc.c:11344
void SCIPfreeDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset)
Definition: scip_datastructures.c:669
int SCIPdisjointsetFind(SCIP_DISJOINTSET *djset, int element)
Definition: misc.c:11247
void SCIPdisjointsetUnion(SCIP_DISJOINTSET *djset, int p, int q, SCIP_Bool forcerepofp)
Definition: misc.c:11274
SCIP_RETCODE SCIPcreateDisjointset(SCIP *scip, SCIP_DISJOINTSET **djset, int ncomponents)
Definition: scip_datastructures.c:654
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3304
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3061
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3466
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3179
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
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_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
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
SCIP_RETCODE SCIPgetIntParam(SCIP *scip, const char *name, int *value)
Definition: scip_param.c:269
SCIP_Bool SCIPconshdlrSupportsSignedPermsymDetection(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:5456
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:940
SCIP_Bool SCIPconshdlrSupportsPermsymDetection(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:5446
int SCIPconshdlrGetNActiveConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4812
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4735
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2621
SCIP_RETCODE SCIPgetConsSignedPermsymGraph(SCIP *scip, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
Definition: scip_cons.c:2687
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:2406
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2536
SCIP_RETCODE SCIPgetConsPermsymGraph(SCIP *scip, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
Definition: scip_cons.c:2654
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1173
SCIP_RETCODE SCIPcreateDatatreeInTree(SCIP *scip, SCIP_DATATREE *datatree, SCIP_DATATREE **newtree, const char *name, int capacity)
Definition: scip_datatree.c:61
SCIP_RETCODE SCIPinsertDatatreeInt(SCIP *scip, SCIP_DATATREE *datatree, const char *name, int value)
Definition: scip_datatree.c:102
SCIP_RETCODE SCIPinsertDatatreeReal(SCIP *scip, SCIP_DATATREE *datatree, const char *name, SCIP_Real value)
Definition: scip_datatree.c:136
SCIP_Bool SCIPexprhdlrHasGetSymData(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:685
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
Definition: scip_general.c:769
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPsetPropResprop(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPRESPROP((*propresprop)))
Definition: scip_prop.c:316
SCIP_RETCODE SCIPsetPropPresol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPPRESOL((*proppresol)), int presolpriority, int presolmaxrounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_prop.c:283
SCIP_RETCODE SCIPsetPropExitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITPRE((*propexitpre)))
Definition: scip_prop.c:267
SCIP_RETCODE SCIPsetPropExit(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXIT((*propexit)))
Definition: scip_prop.c:203
SCIP_RETCODE SCIPsetPropInitpre(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPINITPRE((*propinitpre)))
Definition: scip_prop.c:251
SCIP_RETCODE SCIPsetPropFree(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPFREE((*propfree)))
Definition: scip_prop.c:171
SCIP_RETCODE SCIPsetPropExitsol(SCIP *scip, SCIP_PROP *prop, SCIP_DECL_PROPEXITSOL((*propexitsol)))
Definition: scip_prop.c:235
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:118
SCIP_RETCODE SCIPdetermineNVarsAffectedSym(SCIP *scip, int **perms, int nperms, SCIP_VAR **permvars, int npermvars, int *nvarsaffected)
Definition: symmetry.c:608
SCIP_RETCODE SCIPcomputeComponentsSym(SCIP *scip, SYM_SYMTYPE symtype, 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:790
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:335
SCIP_RETCODE SCIPisInvolutionPerm(int *perm, SCIP_VAR **vars, int nvars, int *ntwocyclesperm, int *nbincyclesperm, SCIP_Bool earlytermination)
Definition: symmetry.c:557
SCIP_VARTYPE SCIPgetSymInferredVarType(SCIP_VAR *var)
Definition: symmetry.c:45
SCIP_RETCODE SCIPdetectSingleOrDoubleLexMatrices(SCIP *scip, SCIP_Bool detectsinglelex, int **perms, int nperms, int permlen, SCIP_Bool *success, SCIP_Bool *isorbitope, int ***lexmatrix, int *nrows, int *ncols, int **lexrowsbegin, int **lexcolsbegin, int *nrowmatrices, int *ncolmatrices)
Definition: symmetry.c:2118
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:1002
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
Definition: symmetry.c:1193
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:187
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:660
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_DECL_TABLECOLLECT((*tablecollect)), SCIP_TABLEDATA *tabledata, int position, SCIP_STAGE earlieststage)
Definition: scip_table.c:62
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:488
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:462
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:475
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:436
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:449
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5697
SCIP_RETCODE SCIPchgVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5875
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsort(int *perm, SCIP_DECL_SORTINDCOMP((*indcomp)), void *dataptr, int len)
Definition: misc.c:5581
SCIP_RETCODE SCIPfreeSymgraph(SCIP *scip, SYM_GRAPH **graph)
Definition: symmetry_graph.c:113
SCIP_RETCODE SCIPcreateSymgraph(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH **graph, SCIP_VAR **symvars, int nsymvars, int nopnodes, int nvalnodes, int nconsnodes, int nedges)
Definition: symmetry_graph.c:46
SCIP_RETCODE SCIPcomputeSymgraphColors(SCIP *scip, SYM_GRAPH *graph, SYM_SPEC fixedtype)
Definition: symmetry_graph.c:1346
SCIP_RETCODE SCIPcreateSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
Definition: symmetry_graph.c:1785
SCIP_RETCODE SCIPfreeSymgraphConsnodeperm(SCIP *scip, SYM_GRAPH *graph)
Definition: symmetry_graph.c:1805
SCIP_RETCODE SCIPcopySymgraph(SCIP *scip, SYM_GRAPH **graph, SYM_GRAPH *origgraph, int *perm, SYM_SPEC fixedtype)
Definition: symmetry_graph.c:203
int SCIPgetSymgraphNVarcolors(SYM_GRAPH *graph)
Definition: symmetry_graph.c:1759
internal miscellaneous methods
Definition: multiprecision.hpp:66
static SCIP_RETCODE handleOrbitope(SCIP *scip, SCIP_PROPDATA *propdata, int componentid, int **varidxmatrix, int nrows, int ncols, char *partialname, SCIP_Bool issigned, SCIP_Bool handlestatically, SCIP_Bool *success, SCIP_Bool allowchgbds, int *nchgbds)
Definition: prop_symmetry.c:6314
static SCIP_Bool conshdlrCanProvideSymInformation(SCIP_CONSHDLR *conshdlr, SYM_SYMTYPE symtype)
Definition: prop_symmetry.c:1504
static SCIP_RETCODE printSyminfoComponentHeader(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
Definition: prop_symmetry.c:616
static SCIP_RETCODE ensureSymmetryMovedPermvarsCountsComputed(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:679
static SCIP_Bool isInvolution(int *perm, int lenperm, SCIP_Bool *istransposition)
Definition: prop_symmetry.c:7280
static SCIP_RETCODE tryAddSymmetryHandlingMethodsComponent(SCIP *scip, SCIP_PROPDATA *propdata, int cidx, SCIP_Bool allowchgbds, int *nchgbds)
Definition: prop_symmetry.c:7566
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:2810
static SCIP_RETCODE propagateSymmetry(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
Definition: prop_symmetry.c:7740
static SCIP_RETCODE handleDoubleLexOrbitope(SCIP *scip, SCIP_PROPDATA *propdata, int **varidxmatrix, int nrows, int ncols, char *partialname, int nsignedrows, SCIP_Bool *success, SCIP_Bool allowchgbds, int *nchgbds)
Definition: prop_symmetry.c:6504
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:8430
static SCIP_RETCODE ensureSymmetryPermvarmapComputed(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:2168
static SCIP_RETCODE createConflictGraphSST(SCIP *scip, SCIP_CONFLICTDATA **varconflicts, SCIP_VAR **conflictvars, int nconflictvars, SCIP_HASHMAP *conflictvarmap)
Definition: prop_symmetry.c:4451
static SCIP_RETCODE ensureDynamicConsArrayAllocatedAndSufficientlyLarge(SCIP *scip, SCIP_CONS ***consarrptr, int *consarrsizeptr, int consarrsizereq)
Definition: prop_symmetry.c:1280
static SCIP_Bool isPermKnown(int *perm, int permlen, int **knownperms, int nknownperms, int *permmap)
Definition: prop_symmetry.c:7242
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:3636
static SCIP_RETCODE determineSymmetry(SCIP *scip, SCIP_PROPDATA *propdata, SYM_SPEC symspecrequire, SYM_SPEC symspecrequirefixed)
Definition: prop_symmetry.c:2357
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:3392
static SCIP_RETCODE hasOrbitopeColumnFlip(int **varidxmatrix, int startrow, int endrow, int startcol, int endcol, int *signedperm, int npermvars, SCIP_Bool transposed, int *flipablerows, int *nflipablerows)
Definition: prop_symmetry.c:6200
static int getNOrbitopesInComp(SCIP_VAR **permvars, int *graphcomponents, int *graphcompbegins, int *compcolorbegins, int ncompcolors, int symcompsize)
Definition: prop_symmetry.c:3718
SCIP_RETCODE SCIPcreateSymOpNodeType(SCIP *scip, const char *opnodename, int *nodetype)
Definition: prop_symmetry.c:8590
static SCIP_RETCODE displaySymmetriesWithComponents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:522
SCIP_RETCODE SCIPdisplaySymmetryGenerators(SCIP *scip, SCIP_PROP *prop)
Definition: prop_symmetry.c:8552
static SCIP_RETCODE tryHandleSingleOrDoubleLexMatricesComponent(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool detectsinglelex, int cidx, SCIP_Bool allowchgbds, int *nchgbds)
Definition: prop_symmetry.c:6991
static SCIP_RETCODE updateSymInfoConflictGraphSST(SCIP *scip, SCIP_CONFLICTDATA *varconflicts, SCIP_VAR **conflictvars, int nconflictvars, int *orbits, int *orbitbegins, int norbits)
Definition: prop_symmetry.c:4338
static SCIP_RETCODE estimateSymgraphSize(SCIP *scip, int *nopnodes, int *nvalnodes, int *nconsnodes, int *nedges)
Definition: prop_symmetry.c:1606
static SCIP_RETCODE addSymresackConss(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
Definition: prop_symmetry.c:4646
static SCIP_Bool isNonstandardPerm(SCIP *scip, int *symmetry, SCIP_VAR **vars, int nvars)
Definition: prop_symmetry.c:2039
static SCIP_RETCODE chooseOrderOfGenerators(SCIP *scip, SCIP_PROPDATA *propdata, int compidx, int **genorder, int *ntwocycleperms)
Definition: prop_symmetry.c:2732
static SCIP_RETCODE tryHandleSubgroups(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
Definition: prop_symmetry.c:7210
static SCIP_RETCODE tryAddSymmetryHandlingMethods(SCIP *scip, SCIP_PROP *prop, SCIP_Bool allowchgbds, int *nchgbds, SCIP_Bool *earlyterm)
Definition: prop_symmetry.c:7636
static SCIP_Bool testSymmetryComputationRequired(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:2307
static int compareSymgraphs(SCIP *scip, SYM_GRAPH *G1, SYM_GRAPH *G2)
Definition: prop_symmetry.c:928
static SCIP_RETCODE resetDynamicSymmetryHandling(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:1083
static SCIP_RETCODE selectOrbitLeaderSSTConss(SCIP *scip, SCIP_CONFLICTDATA *varconflicts, SCIP_VAR **conflictvars, int nconflictvars, int *orbits, int *orbitbegins, int norbits, int leaderrule, int tiebreakrule, SCIP_VARTYPE leadervartype, int *orbitidx, int *leaderidx, SCIP_Shortbool *orbitvarinconflict, int *norbitvarinconflict, SCIP_Bool *success)
Definition: prop_symmetry.c:4962
static SCIP_RETCODE freeSymmetryData(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:1111
static SCIP_RETCODE SCIPdisplaySymmetryStatistics(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:6152
static SCIP_RETCODE printSyminfoGroupAction(SCIP *scip, SCIP_Bool isorbitope, SCIP_Bool isdoublelex, int nrows, int ncols, int nrowmatrices, int ncolmatrices, int *rowsbegin, int *colsbegin)
Definition: prop_symmetry.c:635
static SCIP_DECL_PROPINITPRE(propInitpreSymmetry)
Definition: prop_symmetry.c:7790
static SCIP_RETCODE checkSymmetriesAreSymmetries(SCIP *scip, SYM_SYMTYPE symtype, int **perms, int nperms, int npermvars, SYM_SPEC fixedtype)
Definition: prop_symmetry.c:1708
static SCIP_Bool checkSymmetryDataFree(SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:1038
static SCIP_DECL_PROPRESPROP(propRespropSymmetry)
Definition: prop_symmetry.c:8081
static SCIP_DECL_SORTINDCOMP(SYMsortGraphCompVars)
Definition: prop_symmetry.c:897
static SCIP_RETCODE checkComponentsForNonstandardPerms(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:2076
static SCIP_DECL_SORTPTRCOMP(sortByPointerValue)
Definition: prop_symmetry.c:346
static SCIP_RETCODE tryAddOrbitalRedLexRed(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
Definition: prop_symmetry.c:5954
static SCIP_RETCODE freeConflictGraphSST(SCIP *scip, SCIP_CONFLICTDATA **varconflicts, int nvars)
Definition: prop_symmetry.c:4619
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:3304
static SCIP_RETCODE tryGenerateInvolutions(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
Definition: prop_symmetry.c:7322
static SCIP_RETCODE addSSTConss(SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool onlywithcontvars, int *nchgbds, int cidx)
Definition: prop_symmetry.c:5205
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 *success)
Definition: prop_symmetry.c:3077
static SCIP_RETCODE handleDoublelLexMatrix(SCIP *scip, SCIP_PROPDATA *propdata, int id, int **varidxmatrix, int nrows, int ncols, int *rowsbegin, int *colsbegin, int nrowblocks, int ncolblocks, int **signedperms, int nsignedperms, SCIP_Bool *success, SCIP_Bool allowchgbds, int *nchgbds)
Definition: prop_symmetry.c:6741
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:2547
static SCIP_RETCODE ensureSymmetryPermstransComputed(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:2200
static SCIP_RETCODE displaySymmetriesWithoutComponents(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:473
static SCIP_DECL_PROPEXITPRE(propExitpreSymmetry)
Definition: prop_symmetry.c:7828
static SCIP_RETCODE addSSTConssOrbitAndUpdateSST(SCIP *scip, SCIP_CONFLICTDATA *varconflicts, SCIP_PROPDATA *propdata, SCIP_VAR **permvars, int *orbits, int *orbitbegins, int orbitidx, int orbitleaderidx, SCIP_Shortbool *orbitvarinconflict, int norbitvarinconflict, int *nchgbds)
Definition: prop_symmetry.c:4785
SCIP_RETCODE SCIPincludePropSymmetry(SCIP *scip)
Definition: prop_symmetry.c:8129
static SCIP_DECL_PROPEXITSOL(propExitsolSymmetry)
Definition: prop_symmetry.c:7859
static SCIP_RETCODE displayCycleOfSymmetry(SCIP *scip, int *perm, SYM_SYMTYPE symtype, int baseidx, SCIP_Bool *covered, int nvars, SCIP_VAR **vars)
Definition: prop_symmetry.c:428
static SCIP_DECL_TABLECOLLECT(tableCollectSymmetry)
Definition: prop_symmetry.c:800
int SCIPgetSymmetryNGenerators(SCIP *scip)
Definition: prop_symmetry.c:8529
static SCIP_RETCODE ensureSymmetryComponentsComputed(SCIP *scip, SCIP_PROPDATA *propdata)
Definition: prop_symmetry.c:2121
static SCIP_RETCODE setSymmetryData(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR **vars, int nvars, int nbinvars, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, SCIP_Real **permvardomaincenter, SCIP_Bool **isproperperm, int **perms, int nperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool usecompression, SCIP_Real compressthreshold, SCIP_Bool *compressed)
Definition: prop_symmetry.c:1321
static SCIP_RETCODE detectAndHandleSubgroups(SCIP *scip, SCIP_PROPDATA *propdata, int cidx)
Definition: prop_symmetry.c:3801
static SCIP_RETCODE componentPackingPartitioningOrbisackUpgrade(SCIP *scip, SCIP_PROPDATA *propdata, int **componentperms, int componentsize, SCIP_Bool hassignedperm, SCIP_Bool *success, int *naddedconss)
Definition: prop_symmetry.c:5699
static SCIP_RETCODE computeSymmetryGroup(SCIP *scip, SYM_SYMTYPE symtype, SCIP_Bool compresssymmetries, SCIP_Real compressthreshold, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool checksymmetries, SCIP_VAR ***permvars, int *npermvars, int *nbinpermvars, SCIP_Real **permvardomaincenter, SCIP_Bool **isproperperm, int ***perms, int *nperms, int *nmaxperms, int *nmovedvars, SCIP_Bool *binvaraffected, SCIP_Bool *compressed, SCIP_Real *log10groupsize, SCIP_Real *symcodetime, SCIP_Bool *success)
Definition: prop_symmetry.c:1887
static SCIP_Bool isEquallyCenteredOrbitope(SCIP *scip, SCIP_Real *vardomaincenter, int **varidxmatrix, int startrow, int endrow, int startcol, int endcol, SCIP_Bool equalrowcenters)
Definition: prop_symmetry.c:6262
static SCIP_DECL_TABLEOUTPUT(tableOutputSymmetry)
Definition: prop_symmetry.c:748
static SCIP_RETCODE addOrbitopesDynamic(SCIP *scip, SCIP_PROPDATA *propdata, int componentid, char *partialname, int **varidxmatrix, int nrows, int ncols, SCIP_Bool *success)
Definition: prop_symmetry.c:5506
SCIP_RETCODE SCIPgetSymOpNodeType(SCIP *scip, const char *opnodename, int *nodetype)
Definition: prop_symmetry.c:8629
static SCIP_Bool conshdlrsCanProvideSymInformation(SCIP *scip, SYM_SYMTYPE symtype)
Definition: prop_symmetry.c:1523
static SCIP_Bool checkSortedArraysHaveOverlappingEntry(void **arr1, int narr1, void **arr2, int narr2, SCIP_DECL_SORTPTRCOMP((*compfunc)))
Definition: prop_symmetry.c:359
propagator for symmetry handling
public functions to work with algebraic expressions
public methods for data structures
Definition: struct_implics.h:76
Definition: struct_cons.h:47
Definition: struct_cons.h:128
Definition: struct_datatree.h:74
Definition: struct_misc.h:279
Definition: struct_event.h:218
Definition: struct_expr.h:44
Definition: struct_misc.h:139
Definition: struct_paramset.h:109
Definition: struct_prop.h:47
Definition: struct_var.h:262
Definition: struct_symmetry.h:46
Definition: prop_symmetry.c:881
Definition: struct_scip.h:72
methods for handling symmetries
methods for dealing with symmetry detection graphs
SCIP_RETCODE SCIPlexicographicReductionPropagate(SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
Definition: symmetry_lexred.c:1905
SCIP_RETCODE SCIPlexicographicReductionGetStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata, int *nred, int *ncutoff)
Definition: symmetry_lexred.c:1854
SCIP_RETCODE SCIPlexicographicReductionReset(SCIP *scip, SCIP_LEXREDDATA *masterdata)
Definition: symmetry_lexred.c:2081
SCIP_RETCODE SCIPlexicographicReductionPrintStatistics(SCIP *scip, SCIP_LEXREDDATA *masterdata)
Definition: symmetry_lexred.c:1872
SCIP_RETCODE SCIPlexicographicReductionFree(SCIP *scip, SCIP_LEXREDDATA **masterdata)
Definition: symmetry_lexred.c:2119
SCIP_RETCODE SCIPlexicographicReductionAddPermutation(SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_VAR **permvars, int npermvars, int *perm, SYM_SYMTYPE symtype, SCIP_Real *permvardomaincenter, SCIP_Bool usedynamicorder, SCIP_Bool *success)
Definition: symmetry_lexred.c:2017
SCIP_RETCODE SCIPincludeLexicographicReduction(SCIP *scip, SCIP_LEXREDDATA **masterdata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
Definition: symmetry_lexred.c:2142
methods for handling symmetries by dynamic lexicographic ordering reduction
SCIP_RETCODE SCIPorbitalReductionFree(SCIP *scip, SCIP_ORBITALREDDATA **orbireddata)
Definition: symmetry_orbital.c:1702
SCIP_RETCODE SCIPorbitalReductionGetStatistics(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, int *nred, int *ncutoff)
Definition: symmetry_orbital.c:1534
SCIP_RETCODE SCIPincludeOrbitalReduction(SCIP *scip, SCIP_ORBITALREDDATA **orbireddata, SCIP_EVENTHDLR *shadowtreeeventhdlr)
Definition: symmetry_orbital.c:1722
SCIP_RETCODE SCIPorbitalReductionPrintStatistics(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
Definition: symmetry_orbital.c:1551
SCIP_RETCODE SCIPorbitalReductionAddComponent(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
Definition: symmetry_orbital.c:1647
SCIP_RETCODE SCIPorbitalReductionReset(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
Definition: symmetry_orbital.c:1675
SCIP_RETCODE SCIPorbitalReductionPropagate(SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
Definition: symmetry_orbital.c:1582
struct SCIP_OrbitalReductionData SCIP_ORBITALREDDATA
Definition: symmetry_orbital.h:52
SCIP_RETCODE SCIPincludeOrbitopalReduction(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
Definition: symmetry_orbitopal.c:2291
SCIP_RETCODE SCIPorbitopalReductionFree(SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
Definition: symmetry_orbitopal.c:2271
SCIP_RETCODE SCIPorbitopalReductionReset(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
Definition: symmetry_orbitopal.c:2244
SCIP_RETCODE SCIPorbitopalReductionAddOrbitope(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_ROWORDERING rowordering, SCIP_COLUMNORDERING colordering, SCIP_VAR **vars, int nrows, int ncols, SCIP_Bool *success)
Definition: symmetry_orbitopal.c:2209
SCIP_RETCODE SCIPorbitopalReductionPropagate(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
Definition: symmetry_orbitopal.c:2139
SCIP_RETCODE SCIPorbitopalReductionGetStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, int *nred, int *ncutoff)
Definition: symmetry_orbitopal.c:2088
SCIP_RETCODE SCIPorbitopalReductionPrintStatistics(SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
Definition: symmetry_orbitopal.c:2107
SCIP_COLUMNORDERING SCIPorbitopalReductionGetDefaultColumnOrdering(SCIP_ORBITOPALREDDATA *orbireddata)
Definition: symmetry_orbitopal.c:2337
struct SCIP_OrbitopalReductionData SCIP_ORBITOPALREDDATA
Definition: symmetry_orbitopal.h:69
@ SCIP_LEADERRULE_MAXCONFLICTSINORBIT
Definition: type_symmetry.h:115
@ SCIP_LEADERTIEBREAKRULE_MAXCONFLICTSINORBIT
Definition: type_symmetry.h:124
#define SYM_HANDLETYPE_ORBITALREDUCTION
Definition: type_symmetry.h:104