symmetry_orbital.c File Reference

Detailed Description

methods for handling symmetries by orbital reduction

methods for handling symmetries based on orbits

Author

Jasper van Doornmalen

Orbital fixing is introduced by
F. Margot: Exploiting orbits in symmetric ILP. Math. Program., 98(1-3):3–21, 2003. The method computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the 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 variables in the orbit is fixed to 0 or 1, respectively. This method only works for binary variables. Margot considers the subgroup that stabilizes the set of one-fixings setwise. We determine a subgroup of this group, namely the group generated by the given symmetry group component generators, where the generators satisfy the stabilization condition.

A generalisation is given in the unified symmetry handling constraint paper, Section 4.3 and 5.1 in [vD,H]:
J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023, https://doi.org/10.48550/arXiv.2211.01295.

We assume that the provided symmetries (given by a generating permutation set) are symmetries for the problem at the root node. It is possible that dual (presolving) reductions break this symmetry. As an example, in cons_components.c, if the problem contains an independent component (i.e., variables are not connected logically by constraints), then these individual 'components' can be solved. If an optimal solution is easily retrieved, the variables of this component are fixed, even if symmetrically equivalent solutions exist. Another example is 'stuffing' for linear constraints.

To illustrate this, consider the example \(\max\{x_1 + x_2 : x_1 + x_2 \leq 1, Ay \leq b, (x,y) \in \{0,1\}^{2 + n}\} \). Since \(x_1\) and \(x_2\) are independent from the remaining problem, the setppc constraint handler may fix \((x_1,x_2) = (1,0)\). However, since both variables are symmetric, this setting is not strict (if it was strict, both variables would have been set to the same value) and orbital fixing would declare this subsolution as infeasible (there exists an orbit of non-branching variables that are fixed to different values).

We have observed, and assume, that such dual reductions only take place at presolving or in the root node. So, to avoid this situation, if we detect that a symmetry-breaking reduction is applied at the root node, we disable orbital fixing for certain generating permutations based on the bounds of the affected global variables, see identifyOrbitalSymmetriesBroken.

With the assumption that the symmetries are actual symmetries at the root node, symmetries are broken by the branching decisions. For a branch-and-bound tree node \(\beta\) and variable vector \(x\), let \(\sigma_\beta(x)\) be the permuted and restricted vector \(x\) that enumerates the branching variables, following the path of the root node to \(\beta\) (cf., Example 11 in [vD,H]). Consider a component of the symmetry group, given by a set of generating permutations. Of this set, we select these permutations (not disabled by identifyOrbitalSymmetriesBroken) for which te variable domains of the branched variables \(\sigma_\beta(x)\) are smaller or equal to the variable domains of the permuted variable. This defines a group (cf. [vD,H, Lemma 22]). This group is a subgroup of \(\delta^\beta\) of [vD,H, Section 4.3], meaning that the reductions are valid.

The reductions are:

• For each orbit of the group, every variable domains can be shrunk to the intersection of all variable domains in the orbit.
• The domains of the branching variables are upper bounds to the domains of the variables in its orbits.

For orbital fixing, it is crucial that the vectors \(\sigma_\beta(x)\) are the branching variables up to node \(\beta\) in the given order. Since SCIP can change the tree structure during solving (re-writing history), we store the original branching decisions at the moment they are made. See event_shadowtree.c .

Author

Jasper van Doornmalen

Definition in file symmetry_orbital.c.

#include "blockmemshell/memory.h"
#include "scip/symmetry_orbital.h"
#include "scip/pub_cons.h"
#include "scip/pub_message.h"
#include "scip/pub_var.h"
#include "scip/struct_var.h"
#include "scip/type_var.h"
#include "scip/scip.h"
#include "scip/scip_branch.h"
#include "scip/scip_conflict.h"
#include "scip/scip_cons.h"
#include "scip/scip_copy.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_prob.h"
#include "scip/scip_probing.h"
#include "scip/scip_sol.h"
#include "scip/scip_var.h"
#include "scip/debug.h"
#include "scip/struct_scip.h"
#include "scip/struct_mem.h"
#include "scip/struct_tree.h"
#include "scip/symmetry.h"
#include "scip/event_shadowtree.h"
#include <ctype.h>
#include <string.h>

Go to the source code of this file.

Data Structures
struct	OrbitalReductionComponentData

Macros
#define	EVENTHDLR_SYMMETRY_NAME   "symmetry_orbital"
#define	EVENTHDLR_SYMMETRY_DESC   "filter global variable bound reduction event handler for orbital reduction"

Typedefs
typedef struct OrbitalReductionComponentData	ORCDATA

Functions
static SCIP_RETCODE	identifyOrbitalSymmetriesBroken (SCIP *scip, ORCDATA *orcdata)
static SCIP_RETCODE	orbitalReductionGetSymmetryStabilizerSubgroup (SCIP *scip, ORCDATA *orcdata, int **chosenperms, int *nchosenperms, SCIP_Real *varlbs, SCIP_Real *varubs, int *branchedvarindices, SCIP_Bool *inbranchedvarindices, int nbranchedvarindices)
static int	bisectSortedArrayFindFirstGEQ (int *ids, int *idssort, int frameleft, int frameright, int findid)
static SCIP_RETCODE	applyOrbitalReductionPart (SCIP *scip, ORCDATA *orcdata, SCIP_Bool *infeasible, int *nred, int *varorbitids, int *varorbitidssort, SCIP_Real *varlbs, SCIP_Real *varubs)
static SCIP_RETCODE	applyOrbitalBranchingPropagations (SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
static SCIP_RETCODE	applyOrbitalReductionPropagations (SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
static SCIP_RETCODE	orbitalReductionPropagateComponent (SCIP *scip, ORCDATA *orcdata, SCIP_SHADOWTREE *shadowtree, SCIP_Bool *infeasible, int *nred)
static SCIP_RETCODE	addComponent (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
static SCIP_RETCODE	freeComponent (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, ORCDATA **orcdata)
static	SCIP_DECL_EVENTEXEC (eventExecGlobalBoundChange)
SCIP_RETCODE	SCIPorbitalReductionGetStatistics (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, int *nred, int *ncutoff)
SCIP_RETCODE	SCIPorbitalReductionPrintStatistics (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
SCIP_RETCODE	SCIPorbitalReductionPropagate (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
SCIP_RETCODE	SCIPorbitalReductionAddComponent (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata, SCIP_VAR **permvars, int npermvars, int **perms, int nperms, SCIP_Bool *success)
SCIP_RETCODE	SCIPorbitalReductionReset (SCIP *scip, SCIP_ORBITALREDDATA *orbireddata)
SCIP_RETCODE	SCIPorbitalReductionFree (SCIP *scip, SCIP_ORBITALREDDATA **orbireddata)
SCIP_RETCODE	SCIPincludeOrbitalReduction (SCIP *scip, SCIP_ORBITALREDDATA **orbireddata, SCIP_EVENTHDLR *shadowtreeeventhdlr)

Macro Definition Documentation

EVENTHDLR_SYMMETRY_NAME

#define EVENTHDLR_SYMMETRY_NAME   "symmetry_orbital"

Definition at line 121 of file symmetry_orbital.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeOrbitalReduction().

EVENTHDLR_SYMMETRY_DESC

#define EVENTHDLR_SYMMETRY_DESC   "filter global variable bound reduction event handler for orbital reduction"

Definition at line 122 of file symmetry_orbital.c.

Referenced by SCIPincludeOrbitalReduction().

Typedef Documentation

ORCDATA

typedef struct OrbitalReductionComponentData ORCDATA

Definition at line 148 of file symmetry_orbital.c.

Function Documentation

identifyOrbitalSymmetriesBroken()

static SCIP_RETCODE identifyOrbitalSymmetriesBroken ( SCIP *  scip, ORCDATA *  orcdata  )

static

identifies the orbits at which symmetry is broken according to the global bounds

An example of a symmetry-breaking constraint is cons_components.

Parameters

scip	pointer to SCIP data structure
orcdata	pointer to data for orbital reduction data

Definition at line 175 of file symmetry_orbital.c.

References FALSE, OrbitalReductionComponentData::globalvarlbs, OrbitalReductionComponentData::globalvarubs, OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::npermvars, OrbitalReductionComponentData::nsymbrokenvarids, NULL, OrbitalReductionComponentData::perms, OrbitalReductionComponentData::permvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPfreeDisjointset(), SCIPreallocBlockMemoryArray, SCIPsort(), SCIPsymEQ(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPwarningMessage(), OrbitalReductionComponentData::symbrokenvarids, OrbitalReductionComponentData::symmetrybrokencomputed, and TRUE.

Referenced by orbitalReductionPropagateComponent().

orbitalReductionGetSymmetryStabilizerSubgroup()

static SCIP_RETCODE orbitalReductionGetSymmetryStabilizerSubgroup ( SCIP *  scip, ORCDATA *  orcdata, int **  chosenperms, int *  nchosenperms, SCIP_Real *  varlbs, SCIP_Real *  varubs, int *  branchedvarindices, SCIP_Bool *  inbranchedvarindices, int  nbranchedvarindices  )

static

populates chosenperms with a generating set of the symmetry group stabilizing the branching decisions

The symmetry subgroup considered is generated by all permutations where for all branching variables \(x\) with permuted variable \(y\) for all possible variable assignments we have \(x \leq y\). We restrict ourselves to testing this only for the group generators.

Parameters

scip	pointer to SCIP data structure
orcdata	pointer to data for orbital reduction data
chosenperms	pointer to permutations that are chosen
nchosenperms	pointer to store the number of chosen permutations
varlbs	array of orcdata->permvars variable LBs. If NULL, use local bounds
varubs	array of orcdata->permvars variable UBs. If NULL, use local bounds
branchedvarindices	array of given branching decisions, in branching order
inbranchedvarindices	array stating whether variable with index in orcdata->permvars is contained in the branching decisions.
nbranchedvarindices	number of branching decisions

Definition at line 343 of file symmetry_orbital.c.

References OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::npermvars, OrbitalReductionComponentData::nsymbrokenvarids, NULL, OrbitalReductionComponentData::perms, OrbitalReductionComponentData::permvars, SCIP_OKAY, SCIPsymEQ(), SCIPsymGT(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), OrbitalReductionComponentData::symbrokenvarids, and OrbitalReductionComponentData::symmetrybrokencomputed.

Referenced by applyOrbitalBranchingPropagations(), and applyOrbitalReductionPropagations().

bisectSortedArrayFindFirstGEQ()

static int bisectSortedArrayFindFirstGEQ ( int *  ids, int *  idssort, int  frameleft, int  frameright, int  findid  )

static

using bisection, finds the minimal index k (frameleft <= k < frameright) such that ids[idssort[k]] >= findid

If for all k (frameleft <= k < frameright) holds ids[idssort[k]] < findid, returns frameright.

Parameters

ids	int array with entries
idssort	array of indices of ids that sort ids
frameleft	search in idssort for index range [frameleft, frameright)
frameright	search in idssort for index range [frameleft, frameright)
findid	entry value to find

Definition at line 450 of file symmetry_orbital.c.

References NULL.

Referenced by applyOrbitalBranchingPropagations().

applyOrbitalReductionPart()

static SCIP_RETCODE applyOrbitalReductionPart ( SCIP *  scip, ORCDATA *  orcdata, SCIP_Bool *  infeasible, int *  nred, int *  varorbitids, int *  varorbitidssort, SCIP_Real *  varlbs, SCIP_Real *  varubs  )

static

applies the orbital reduction steps for precomputed orbits

Either use the local variable bounds, or variable bounds determined by the varlbs and varubs arrays.

Precondition

varubs is NULL if and only if varlbs is NULL.

Parameters

scip	pointer to SCIP data structure
orcdata	pointer to data for orbital reduction data
infeasible	pointer to store whether infeasibility is detected
nred	pointer to store the number of determined domain reductions
varorbitids	array specifying the orbit IDs for variables in array orcdata->vars
varorbitidssort	an index array that sorts the varorbitids array
varlbs	array of lower bounds for variable array orcdata->vars to compute with or NULL, if local bounds are used
varubs	array of upper bounds for variable array orcdata->vars to compute with or NULL, if local bounds are used.

Definition at line 515 of file symmetry_orbital.c.

References OrbitalReductionComponentData::npermvars, NULL, OrbitalReductionComponentData::permvars, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisInfinity(), SCIPsymGE(), SCIPsymGT(), SCIPsymLE(), SCIPsymLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by applyOrbitalBranchingPropagations(), and applyOrbitalReductionPropagations().

applyOrbitalBranchingPropagations()

static SCIP_RETCODE applyOrbitalBranchingPropagations ( SCIP *  scip, ORCDATA *  orcdata, SCIP_SHADOWTREE *  shadowtree, SCIP_Bool *  infeasible, int *  nred  )

static

orbital reduction, the orbital branching part

Parameters

scip	pointer to SCIP data structure
orcdata	pointer to data for orbital reduction data
shadowtree	pointer to shadow tree
infeasible	pointer to store whether infeasibility is detected
nred	pointer to store the number of determined domain reductions

Definition at line 643 of file symmetry_orbital.c.

References applyOrbitalReductionPart(), bisectSortedArrayFindFirstGEQ(), SCIP_ShadowBoundUpdate::boundchgtype, SCIP_ShadowNode::branchingdecisions, FALSE, OrbitalReductionComponentData::globalvarlbs, OrbitalReductionComponentData::globalvarubs, OrbitalReductionComponentData::lastnode, SCIP_ShadowNode::nbranchingdecisions, SCIP_ShadowBoundUpdate::newbound, OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::npermvars, SCIP_ShadowNode::npropagations, NULL, orbitalReductionGetSymmetryStabilizerSubgroup(), SCIP_ShadowNode::parent, OrbitalReductionComponentData::permvarmap, OrbitalReductionComponentData::permvars, SCIP_ShadowNode::propagations, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPfreeDisjointset(), SCIPgetCurrentNode(), SCIPgetFocusNode(), SCIPhashmapGetImageInt(), SCIPisInfinity(), SCIPnodeGetParent(), SCIPshadowTreeGetShadowNode(), SCIPsort(), SCIPsymGE(), SCIPsymGT(), SCIPsymLE(), SCIPsymLT(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPwarningMessage(), OrbitalReductionComponentData::treewarninggiven, TRUE, and SCIP_ShadowBoundUpdate::var.

Referenced by orbitalReductionPropagateComponent().

applyOrbitalReductionPropagations()

static SCIP_RETCODE applyOrbitalReductionPropagations ( SCIP *  scip, ORCDATA *  orcdata, SCIP_SHADOWTREE *  shadowtree, SCIP_Bool *  infeasible, int *  nred  )

static

orbital reduction, the orbital reduction part

Parameters

scip	pointer to SCIP data structure
orcdata	pointer to data for orbital reduction data
shadowtree	pointer to shadow tree
infeasible	pointer to store whether infeasibility is detected
nred	pointer to store the number of determined domain reductions

Definition at line 1021 of file symmetry_orbital.c.

References applyOrbitalReductionPart(), SCIP_ShadowNode::branchingdecisions, FALSE, SCIP_ShadowNode::nbranchingdecisions, OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::npermvars, NULL, orbitalReductionGetSymmetryStabilizerSubgroup(), SCIP_ShadowNode::parent, OrbitalReductionComponentData::permvarmap, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPcreateDisjointset(), SCIPdisjointsetFind(), SCIPdisjointsetUnion(), SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPfreeDisjointset(), SCIPgetCurrentNode(), SCIPgetFocusNode(), SCIPhashmapGetImageInt(), SCIPshadowTreeGetShadowNode(), SCIPsort(), TRUE, and SCIP_ShadowBoundUpdate::var.

Referenced by orbitalReductionPropagateComponent().

orbitalReductionPropagateComponent()

static SCIP_RETCODE orbitalReductionPropagateComponent ( SCIP *  scip, ORCDATA *  orcdata, SCIP_SHADOWTREE *  shadowtree, SCIP_Bool *  infeasible, int *  nred  )

static

applies orbital reduction on a symmetry group component using a two step mechanism

1. At the parent of our focus node (which is the current node, because we're not probing), compute the symmetry group just before branching. Then, for our branching variable x with variable y in its orbit, we mimic adding the constraint x >= y by variable bound propagations in this node.

   In principle, this generalizes orbital branching in the binary case: propagation of x >= y yields

   1. In the 1-branch: 1 = x >= y is a tautology (since y is in {0, 1}). Nothing happens. 0. In the 0-branch: 0 = x >= y implies y = 0. This is an exact description of orbital branching. REF: Ostrowski, James, et al. "Orbital branching." Mathematical Programming 126.1 (2011): 147-178.

   (This only needs to be done once per node.)

2. At the focus node itself, compute the symmetry group. The symmetry group in this branch-and-bound tree node is a subgroup of the problem symmetry group as described in the function orbitalReductionGetSymmetryStabilizerSubgroup. For this symmetry subgroup, in each orbit, update the variable domains with the intersection of all variable domains in the orbit.

   This generalizes orbital fixing in the binary case. REF: Margot 2002, Margot 2003, Orbital Branching, Ostrowski's PhD thesis.

Parameters

scip	SCIP data structure
orcdata	orbital reduction component data
shadowtree	pointer to shadow tree
infeasible	pointer to store whether infeasibility is found
nred	pointer to store the number of domain reductions

Definition at line 1182 of file symmetry_orbital.c.

References applyOrbitalBranchingPropagations(), applyOrbitalReductionPropagations(), identifyOrbitalSymmetriesBroken(), OrbitalReductionComponentData::npermvars, OrbitalReductionComponentData::nsymbrokenvarids, NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPgetNNodes(), SCIPgetStage(), and OrbitalReductionComponentData::symmetrybrokencomputed.

Referenced by SCIPorbitalReductionPropagate().

addComponent()

static SCIP_RETCODE addComponent ( SCIP *  scip, SCIP_ORBITALREDDATA *  orbireddata, SCIP_VAR **  permvars, int  npermvars, int **  perms, int  nperms, SCIP_Bool *  success  )

static

adds component

Parameters

scip	SCIP data structure
orbireddata	pointer to the orbital reduction data
permvars	variable array of the permutation
npermvars	number of variables in that array
perms	permutations in the component
nperms	number of permutations in the component
success	to store whether the component is successfully added

Definition at line 1233 of file symmetry_orbital.c.

References FALSE, OrbitalReductionComponentData::globalvarlbs, OrbitalReductionComponentData::globalvarubs, OrbitalReductionComponentData::lastnode, OrbitalReductionComponentData::nperms, OrbitalReductionComponentData::npermvars, OrbitalReductionComponentData::nsymbrokenvarids, NULL, OrbitalReductionComponentData::perms, OrbitalReductionComponentData::permvarmap, OrbitalReductionComponentData::permvars, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIPactivateShadowTree(), SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPcaptureVar(), SCIPcatchVarEvent(), SCIPfreeBlockMemory, SCIPhashmapCreate(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPmarkDoNotMultaggrVar(), SCIPreallocBlockMemoryArray, SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), OrbitalReductionComponentData::symbrokenvarids, OrbitalReductionComponentData::symmetrybrokencomputed, OrbitalReductionComponentData::treewarninggiven, and TRUE.

Referenced by SCIPorbitalReductionAddComponent().

freeComponent()

static SCIP_RETCODE freeComponent ( SCIP *  scip, SCIP_ORBITALREDDATA *  orbireddata, ORCDATA **  orcdata  )

static

frees component

Parameters

scip	SCIP data structure
orbireddata	pointer to the orbital reduction data
orcdata	pointer to component data

Definition at line 1405 of file symmetry_orbital.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_STAGE_FREE, SCIPdropVarEvent(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetStage(), SCIPhashmapFree(), SCIPisTransformed(), and SCIPreleaseVar().

Referenced by SCIPorbitalReductionReset().

SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecGlobalBoundChange  )

static

maintains global variable bound reductions found during presolving or at the root node

Definition at line 1479 of file symmetry_orbital.c.

References EVENTHDLR_SYMMETRY_NAME, OrbitalReductionComponentData::globalvarlbs, OrbitalReductionComponentData::globalvarubs, NULL, OrbitalReductionComponentData::permvarmap, SCIP_ERROR, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPABORT, SCIPeventGetNewbound(), SCIPeventGetOldbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetName(), SCIPgetNNodes(), SCIPgetStage(), SCIPhashmapGetImageInt(), SCIPvarIsTransformed(), and OrbitalReductionComponentData::symmetrybrokencomputed.

SCIPorbitalReductionGetStatistics()

SCIP_RETCODE SCIPorbitalReductionGetStatistics	(	SCIP *	scip,
		SCIP_ORBITALREDDATA *	orbireddata,
		int *	nred,
		int *	ncutoff
	)

prints orbital reduction data

Parameters

scip	SCIP data structure
orbireddata	orbital reduction data structure
nred	pointer to store the total number of reductions applied
ncutoff	pointer to store the total number of cutoffs applied

Definition at line 1534 of file symmetry_orbital.c.

References NULL, and SCIP_OKAY.

Referenced by SCIP_DECL_TABLEOUTPUT().

SCIPorbitalReductionPrintStatistics()

SCIP_RETCODE SCIPorbitalReductionPrintStatistics	(	SCIP *	scip,
		SCIP_ORBITALREDDATA *	orbireddata
	)

prints orbital reduction data

Parameters

scip	SCIP data structure
orbireddata	orbital reduction data structure

Definition at line 1551 of file symmetry_orbital.c.

References NULL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, and SCIPverbMessage().

Referenced by SCIPdisplaySymmetryStatistics().

SCIPorbitalReductionPropagate()

SCIP_RETCODE SCIPorbitalReductionPropagate	(	SCIP *	scip,
		SCIP_ORBITALREDDATA *	orbireddata,
		SCIP_Bool *	infeasible,
		int *	nred,
		SCIP_Bool *	didrun
	)

propagates orbital reduction

Parameters

scip	SCIP data structure
orbireddata	orbital reduction data structure
infeasible	pointer to store whether infeasibility is found
nred	pointer to store the number of domain reductions
didrun	a global pointer maintaining if any symmetry propagator has run only set this to TRUE when a reduction is found, never set to FALSE

Definition at line 1582 of file symmetry_orbital.c.

References FALSE, OrbitalReductionComponentData::nperms, NULL, orbitalReductionPropagateComponent(), SCIP_CALL, SCIP_OKAY, SCIPgetShadowTree(), SCIPinProbing(), SCIPinRepropagation(), and TRUE.

Referenced by propagateSymmetry().

SCIPorbitalReductionAddComponent()

SCIP_RETCODE SCIPorbitalReductionAddComponent	(	SCIP *	scip,
		SCIP_ORBITALREDDATA *	orbireddata,
		SCIP_VAR **	permvars,
		int	npermvars,
		int **	perms,
		int	nperms,
		SCIP_Bool *	success
	)

adds component for orbital reduction

Parameters

scip	SCIP data structure
orbireddata	orbital reduction data structure
permvars	variable array of the permutation
npermvars	number of variables in that array
perms	permutations in the component
nperms	number of permutations in the component
success	to store whether the component is successfully added

Definition at line 1644 of file symmetry_orbital.c.

References addComponent(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPisTransformed().

Referenced by tryAddOrbitalRedLexRed().

SCIPorbitalReductionReset()

SCIP_RETCODE SCIPorbitalReductionReset	(	SCIP *	scip,
		SCIP_ORBITALREDDATA *	orbireddata
	)

resets orbital reduction data structure (clears all components)

Parameters

scip	SCIP data structure
orbireddata	orbital reduction data structure

Definition at line 1672 of file symmetry_orbital.c.

References freeComponent(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPfreeBlockMemoryArrayNull.

Referenced by resetDynamicSymmetryHandling(), and SCIPorbitalReductionFree().

SCIPorbitalReductionFree()

SCIP_RETCODE SCIPorbitalReductionFree	(	SCIP *	scip,
		SCIP_ORBITALREDDATA **	orbireddata
	)

frees orbital reduction data

Parameters

scip	SCIP data structure
orbireddata	orbital reduction data structure

Definition at line 1699 of file symmetry_orbital.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPorbitalReductionReset().

Referenced by SCIP_DECL_PROPFREE().

SCIPincludeOrbitalReduction()

SCIP_RETCODE SCIPincludeOrbitalReduction	(	SCIP *	scip,
		SCIP_ORBITALREDDATA **	orbireddata,
		SCIP_EVENTHDLR *	shadowtreeeventhdlr
	)

initializes structures needed for orbital reduction

This is only done exactly once.

Parameters

scip	SCIP data structure
orbireddata	pointer to orbital reduction data structure to populate
shadowtreeeventhdlr	pointer to the shadow tree eventhdlr

Definition at line 1719 of file symmetry_orbital.c.

References EVENTHDLR_SYMMETRY_DESC, EVENTHDLR_SYMMETRY_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPcheckStage(), SCIPincludeEventhdlrBasic(), and TRUE.

Referenced by SCIPincludePropSymmetry().