symmetry_lexred.c File Reference

Detailed Description

methods for handling symmetries by dynamic lexicographic ordering reduction

Author

Jasper van Doornmalen

This implements lexicographic reduction, which generalizes symresack propagation to work for non-binary variable domains, and is dynamified. Whereas static lexicographic reduction propagates that a vector \(x\) is lexicographically larger than its permuted counterpart (i.e., \(x \succeq \gamma(x)\) with \(\succeq\) being standard elementwise lexicographic comparison), the dynamic variant determines the variable vector ordering dynamically. Just as in orbital reduction (cf. symmetry_orbital.c), the variable order is chosen as the variables branched on from the root node to the focus node. Thus, in node \(\beta\), we propagate \(\sigma_\beta(x) \succeq \sigma_\beta(\gamma(x))\), where \(\sigma_\beta(\cdot)\) permutes and restricts the variable vector such that it corresponds to the branched variables in the order from the rooted path to \(\beta\).

See Section 4.1 and Example 11 in [vD,H]:
J. van Doornmalen, C. Hojny, "A Unified Framework for Symmetry Handling", preprint, 2023, https://doi.org/10.48550/arXiv.2211.01295.

For dynamic lexicographic reduction, 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 .

Definition in file symmetry_lexred.c.

#include "blockmemshell/memory.h"
#include "scip/symmetry_lexred.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 <string.h>

Go to the source code of this file.

Data Structures
struct	LexRedPermData
struct	NodeDepthBranchIndex
struct	VarArrayNodeDepthBranchIndex

Typedefs
typedef struct LexRedPermData	LEXDATA
typedef struct NodeDepthBranchIndex	NODEDEPTHBRANCHINDEX
typedef struct VarArrayNodeDepthBranchIndex	VARARRAYNODEDEPTHBRANCHINDEX

Functions
static SCIP_RETCODE	lexdataFree (SCIP *scip, LEXDATA **lexdata)
static SCIP_RETCODE	lexdataCreate (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA **lexdata, SCIP_VAR *const *vars, int nvars, int *perm, SYM_SYMTYPE symtype, SCIP_Real *permvardomaincenter, SCIP_Bool usedynamicorder, SCIP_Bool *success)
static	SCIP_DECL_SORTINDCOMP (sortbynodedepthbranchindices)
static int	varOrderGetIndex (int *varorder, int pos)
static SCIP_RETCODE	getVarOrder (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, int nvarstotal, SCIP_VAR **branchvars, int nbranchvars, int *varorder, int *nselvars, int maxnselvars)
static SCIP_RETCODE	getVarBounds (SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset, SCIP_Real *lb1, SCIP_Real *ub1, SCIP_Real *lb2, SCIP_Real *ub2)
static SCIP_Bool	alwaysLTshiftedVars (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real shift1, SCIP_Real shift2, SCIP_Bool isnegated, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
static SCIP_Bool	canGTshiftedVars (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real shift1, SCIP_Real shift2, SCIP_Bool isnegated, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
static SCIP_RETCODE	propagateLowerBoundVar (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real center1, SCIP_Real center2, SCIP_Bool isnegated, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
static SCIP_RETCODE	propagateUpperBoundSymVar (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real center1, SCIP_Real center2, SCIP_Bool isnegated, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
static SCIP_RETCODE	propagateSelfReflectionVar (SCIP *scip, SCIP_VAR *var, SCIP_Real center, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
static SCIP_RETCODE	propagateVariablePair (SCIP *scip, SCIP_VAR *var1, SCIP_VAR *var2, SCIP_Real center1, SCIP_Real center2, SCIP_Bool isnegated, SCIP_Bool *infeasible, int *nreductions, SCIP_Bool peekmode, int varidx1, int varidx2, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
static SCIP_RETCODE	peekStaticLexredIsFeasible (SCIP *scip, LEXDATA *lexdata, int *varorder, int nselvars, int fixi, int fixj, int fixrow, SCIP_Real fixvaluei, SCIP_Real fixvaluej, SCIP_Bool *peekfeasible, SCIP_Real *peeklbs, SCIP_Real *peekubs, SCIP_Bool *peekbdset)
static SCIP_RETCODE	propagateStaticLexred (SCIP *scip, LEXDATA *lexdata, int *varorder, int nselvars, SCIP_Bool *infeasible, int *nreductions)
static SCIP_RETCODE	propagateLexredDynamic (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, int nvarstotal, SCIP_VAR **branchvars, int nbranchvars, SCIP_Bool *infeasible, int *nreductions)
static SCIP_RETCODE	propagateLexredStatic (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, SCIP_Bool *infeasible, int *nreductions)
static SCIP_RETCODE	propagateLexicographicReductionPerm (SCIP *scip, SCIP_LEXREDDATA *masterdata, LEXDATA *lexdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, int nvarstotal, SCIP_VAR **branchvars, int nbranchvars, SCIP_Bool *infeasible, int *nreductions)
static SCIP_RETCODE	shadowtreeFillNodeDepthBranchIndices (SCIP *scip, SCIP_LEXREDDATA *masterdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, SCIP_VAR **branchvars, int *nbranchvars, SCIP_SHADOWTREE *shadowtree, SCIP_NODE *focusnode, SCIP_Bool *inforesolved)
static SCIP_RETCODE	shadowtreeUndoNodeDepthBranchIndices (SCIP *scip, SCIP_LEXREDDATA *masterdata, NODEDEPTHBRANCHINDEX *nodedepthbranchindices, SCIP_VAR **branchvars, int *nbranchvars, SCIP_SHADOWTREE *shadowtree, SCIP_NODE *focusnode)
SCIP_RETCODE	SCIPlexicographicReductionGetStatistics (SCIP *scip, SCIP_LEXREDDATA *masterdata, int *nred, int *ncutoff)
SCIP_RETCODE	SCIPlexicographicReductionPrintStatistics (SCIP *scip, SCIP_LEXREDDATA *masterdata)
SCIP_RETCODE	SCIPlexicographicReductionPropagate (SCIP *scip, SCIP_LEXREDDATA *masterdata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
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)
SCIP_RETCODE	SCIPlexicographicReductionReset (SCIP *scip, SCIP_LEXREDDATA *masterdata)
SCIP_RETCODE	SCIPlexicographicReductionFree (SCIP *scip, SCIP_LEXREDDATA **masterdata)
SCIP_RETCODE	SCIPincludeLexicographicReduction (SCIP *scip, SCIP_LEXREDDATA **masterdata, SCIP_EVENTHDLR *shadowtreeeventhdlr)

Typedef Documentation

LEXDATA

typedef struct LexRedPermData LEXDATA

Definition at line 100 of file symmetry_lexred.c.

NODEDEPTHBRANCHINDEX

typedef struct NodeDepthBranchIndex NODEDEPTHBRANCHINDEX

Definition at line 125 of file symmetry_lexred.c.

VARARRAYNODEDEPTHBRANCHINDEX

typedef struct VarArrayNodeDepthBranchIndex VARARRAYNODEDEPTHBRANCHINDEX

Definition at line 135 of file symmetry_lexred.c.

Function Documentation

lexdataFree()

static SCIP_RETCODE lexdataFree ( SCIP *  scip, LEXDATA **  lexdata  )

static

frees dynamic lexicographic reduction propagator data

Parameters

scip	SCIP data structure
lexdata	pointer to individual lexicographic reduction propagator datas

Definition at line 144 of file symmetry_lexred.c.

References FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPhashmapFree(), SCIPreleaseVar(), SYM_SYMTYPE_SIGNPERM, and TRUE.

Referenced by SCIPlexicographicReductionReset().

lexdataCreate()

static SCIP_RETCODE lexdataCreate ( SCIP *  scip, SCIP_LEXREDDATA *  masterdata, LEXDATA **  lexdata, SCIP_VAR *const *  vars, int  nvars, int *  perm, SYM_SYMTYPE  symtype, SCIP_Real *  permvardomaincenter, SCIP_Bool  usedynamicorder, SCIP_Bool *  success  )

static

creates dynamic lexicographic reduction propagator data

Fixed points are removed.

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
lexdata	pointer to store data for permutation to be added
vars	input variables of the lexicographic reduction propagator
nvars	input number of variables of the lexicographic reduction propagator
perm	input permutation of the lexicographic reduction propagator
symtype	type of symmetries in perm
permvardomaincenter	array containing center point for each variable domain
usedynamicorder	whether a dynamic variable order shall be used
success	to store whether the component is successfully added

Definition at line 222 of file symmetry_lexred.c.

References FALSE, VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPactivateShadowTree(), SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPcaptureVar(), SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapInsertInt(), SCIPisTransformed(), SCIPmarkDoNotMultaggrVar(), SCIPvarIsTransformed(), SYM_SYMTYPE_PERM, TRUE, and VarArrayNodeDepthBranchIndex::vars.

Referenced by SCIPlexicographicReductionAddPermutation().

SCIP_DECL_SORTINDCOMP()

static SCIP_DECL_SORTINDCOMP ( sortbynodedepthbranchindices  )

static

comparator used in the getVarOrder() function, for sorting an array of NODEDEPTHBRANCHINDEX by depth, then by index

Warning

this function is only meant to be used in the getVarOrder() function

Precondition

datapointer is populated with a VARARRAYNODEDEPTHBRANCHINDEX pointer

the comparator is only called on entries with set (depth, index)-information

the (depth, index)-informations are all different

result: 0: the same index is compared, so the (depth, index)-informations are the same -1: the depth of ind1 is smaller than the depth of ind2, or it's equal and the index is smaller 1: the depth of ind2 is smaller than the depth of ind1, or it's equal and the index is smaller

Definition at line 422 of file symmetry_lexred.c.

References NodeDepthBranchIndex::index, VarArrayNodeDepthBranchIndex::masterdata, NodeDepthBranchIndex::nodedepth, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, SCIPhashmapGetImageInt(), and VarArrayNodeDepthBranchIndex::vars.

varOrderGetIndex()

static int varOrderGetIndex ( int *  varorder, int  pos  )

static

return the index of a variable at a specific position of a variable order

Parameters

varorder	variable order (or NULL)
pos	position for which index is returned

Definition at line 466 of file symmetry_lexred.c.

References NULL.

Referenced by peekStaticLexredIsFeasible(), and propagateStaticLexred().

getVarOrder()

static SCIP_RETCODE getVarOrder ( SCIP *  scip, SCIP_LEXREDDATA *  masterdata, LEXDATA *  lexdata, NODEDEPTHBRANCHINDEX *  nodedepthbranchindices, int  nvarstotal, SCIP_VAR **  branchvars, int  nbranchvars, int *  varorder, int *  nselvars, int  maxnselvars  )

static

gets the variable ordering based on the branching decisions at the node

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
lexdata	pointer to data for this permutation
nodedepthbranchindices	array with (depth, index)-information per variable in rooted path to focus node
nvarstotal	length of that array
branchvars	array populated with variables branched on in the symvarmap hashset
nbranchvars	number of elements in branchvars array
varorder	array to populate with variable order
nselvars	pointer to number of variables in the ordering
maxnselvars	maximal size of the number of selected variables

Definition at line 481 of file symmetry_lexred.c.

References VarArrayNodeDepthBranchIndex::masterdata, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, LexRedPermData::nvars, SCIP_OKAY, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPsortInd(), LexRedPermData::varmap, LexRedPermData::vars, and VarArrayNodeDepthBranchIndex::vars.

Referenced by propagateLexredDynamic().

getVarBounds()

static SCIP_RETCODE getVarBounds ( SCIP_VAR *  var1, SCIP_VAR *  var2, SCIP_Bool  peekmode, int  varidx1, int  varidx2, SCIP_Real *  peeklbs, SCIP_Real *  peekubs, SCIP_Bool *  peekbdset, SCIP_Real *  lb1, SCIP_Real *  ub1, SCIP_Real *  lb2, SCIP_Real *  ub2  )

static

gerts local variable bounds or reads bound from peek data

Parameters

var1	first variable in comparison
var2	second variable in comparison
peekmode	whether function is called in peek mode
varidx1	index of var1 (or NULL)
varidx2	index of var2 (or NULL)
peeklbs	lower bounds of variables in peek mode (or NULL)
peekubs	upper bounds of variables in peek mode (or NULL)
peekbdset	whether peek bounds have been set (or NULL)
lb1	pointer to store lower bound of var1
ub1	pointer to store upper bound of var1
lb2	pointer to store lower bound of var2
ub2	pointer to store upper bound of var2

Definition at line 590 of file symmetry_lexred.c.

References NULL, SCIP_OKAY, SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by alwaysLTshiftedVars(), canGTshiftedVars(), propagateLowerBoundVar(), propagateSelfReflectionVar(), propagateStaticLexred(), and propagateUpperBoundSymVar().

alwaysLTshiftedVars()

static SCIP_Bool alwaysLTshiftedVars ( SCIP *  scip, SCIP_VAR *  var1, SCIP_VAR *  var2, SCIP_Real  shift1, SCIP_Real  shift2, SCIP_Bool  isnegated, SCIP_Bool  peekmode, int  varidx1, int  varidx2, SCIP_Real *  peeklbs, SCIP_Real *  peekubs, SCIP_Bool *  peekbdset  )

static

returns whether a shifted variable is always smaller than another shifted variable

Shifts are always (var - shift).

Parameters

scip	SCIP data structure
var1	first variable in comparison
var2	second variable in comparison
shift1	shift of var1
shift2	shift of var2
isnegated	whether shift of var2 is negated
peekmode	whether function is called in peek mode
varidx1	index of var1 (or NULL)
varidx2	index of var2 (or NULL)
peeklbs	lower bounds of variables in peek mode (or NULL)
peekubs	upper bounds of variables in peek mode (or NULL)
peekbdset	whether peek bounds have been set (or NULL)

Definition at line 644 of file symmetry_lexred.c.

References FALSE, getVarBounds(), NULL, SCIP_CALL_ABORT, SCIP_Real, SCIPisLT(), and TRUE.

Referenced by peekStaticLexredIsFeasible(), and propagateVariablePair().

canGTshiftedVars()

static SCIP_Bool canGTshiftedVars ( SCIP *  scip, SCIP_VAR *  var1, SCIP_VAR *  var2, SCIP_Real  shift1, SCIP_Real  shift2, SCIP_Bool  isnegated, SCIP_Bool  peekmode, int  varidx1, int  varidx2, SCIP_Real *  peeklbs, SCIP_Real *  peekubs, SCIP_Bool *  peekbdset  )

static

returns whether a shifted variable can be greater than another shifted variable

Shifts are always (var - shift).

Parameters

scip	SCIP data structure
var1	first variable in comparison
var2	second variable in comparison
shift1	shift of var1
shift2	shift of var2
isnegated	whether shift of var2 is negated
peekmode	whether function is called in peek mode
varidx1	index of var1 (or NULL)
varidx2	index of var2 (or NULL)
peeklbs	lower bounds of variables in peek mode (or NULL)
peekubs	upper bounds of variables in peek mode (or NULL)
peekbdset	whether peek bounds have been set (or NULL)

Definition at line 691 of file symmetry_lexred.c.

References FALSE, getVarBounds(), NULL, SCIP_CALL_ABORT, SCIP_Real, SCIPisGT(), and TRUE.

Referenced by peekStaticLexredIsFeasible(), and propagateStaticLexred().

propagateLowerBoundVar()

static SCIP_RETCODE propagateLowerBoundVar ( SCIP *  scip, SCIP_VAR *  var1, SCIP_VAR *  var2, SCIP_Real  center1, SCIP_Real  center2, SCIP_Bool  isnegated, SCIP_Bool *  infeasible, int *  nreductions, SCIP_Bool  peekmode, int  varidx1, int  varidx2, SCIP_Real *  peeklbs, SCIP_Real *  peekubs, SCIP_Bool *  peekbdset  )

static

propagates lower bound of first variable in relation x >= y for shifted variables

Parameters

scip	SCIP data structure
var1	first variable in pair
var2	second variable in pair
center1	center of var1 (original var domain)
center2	center of var2 (original var domain)
isnegated	whether var2 is negated by symmetry
infeasible	pointer to store whether infeasibility is found
nreductions	pointer to store number of reductions
peekmode	whether function is called in peek mode
varidx1	index of var1 (or NULL)
varidx2	index of var2 (or NULL)
peeklbs	lower bounds of variables in peek mode (or NULL)
peekubs	upper bounds of variables in peek mode (or NULL)
peekbdset	whether peek bounds have been set (or NULL)

Definition at line 735 of file symmetry_lexred.c.

References FALSE, getVarBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), SCIPtightenVarLb(), SCIPvarGetName(), and TRUE.

Referenced by peekStaticLexredIsFeasible(), and propagateVariablePair().

propagateUpperBoundSymVar()

static SCIP_RETCODE propagateUpperBoundSymVar ( SCIP *  scip, SCIP_VAR *  var1, SCIP_VAR *  var2, SCIP_Real  center1, SCIP_Real  center2, SCIP_Bool  isnegated, SCIP_Bool *  infeasible, int *  nreductions, SCIP_Bool  peekmode, int  varidx1, int  varidx2, SCIP_Real *  peeklbs, SCIP_Real *  peekubs, SCIP_Bool *  peekbdset  )

static

propagates upper bound of second variable in relation x >= y for shifted variables

Parameters

scip	SCIP data structure
var1	first variable in pair
var2	second variable in pair
center1	center of var1 (original var domain)
center2	center of var2 (original var domain)
isnegated	whether var2 is negated by symmetry
infeasible	pointer to store whether infeasibility is found
nreductions	pointer to store number of reductions
peekmode	whether function is called in peek mode
varidx1	index of var1 (or NULL)
varidx2	index of var2 (or NULL)
peeklbs	lower bounds of variables in peek mode (or NULL)
peekubs	upper bounds of variables in peek mode (or NULL)
peekbdset	whether peek bounds have been set (or NULL)

Definition at line 822 of file symmetry_lexred.c.

References FALSE, getVarBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), and TRUE.

Referenced by peekStaticLexredIsFeasible(), and propagateVariablePair().

propagateSelfReflectionVar()

static SCIP_RETCODE propagateSelfReflectionVar ( SCIP *  scip, SCIP_VAR *  var, SCIP_Real  center, SCIP_Bool *  infeasible, int *  nreductions, SCIP_Bool  peekmode, int  varidx, SCIP_Real *  peeklbs, SCIP_Real *  peekubs, SCIP_Bool *  peekbdset  )

static

propagates x - c >= c - x

Parameters

scip	SCIP data structure
var	variable
center	center of var (original var domain)
infeasible	pointer to store whether infeasibility is found
nreductions	pointer to store number of reductions
peekmode	whether function is called in peek mode
varidx	index of var (or NULL)
peeklbs	lower bounds of variables in peek mode (or NULL)
peekubs	upper bounds of variables in peek mode (or NULL)
peekbdset	whether peek bounds have been set (or NULL)

Definition at line 932 of file symmetry_lexred.c.

References FALSE, getVarBounds(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisLT(), SCIPtightenVarLb(), SCIPvarGetName(), and TRUE.

Referenced by propagateVariablePair().

propagateVariablePair()

static SCIP_RETCODE propagateVariablePair ( SCIP *  scip, SCIP_VAR *  var1, SCIP_VAR *  var2, SCIP_Real  center1, SCIP_Real  center2, SCIP_Bool  isnegated, SCIP_Bool *  infeasible, int *  nreductions, SCIP_Bool  peekmode, int  varidx1, int  varidx2, SCIP_Real *  peeklbs, SCIP_Real *  peekubs, SCIP_Bool *  peekbdset  )

static

propagates lexicographic order for one pair of symmetric variables

Parameters

scip	SCIP data structure
var1	first variable in pair
var2	second variable in pair
center1	center of var1 (original var domain)
center2	center of var2 (original var domain)
isnegated	whether var2 is negated by symmetry
infeasible	pointer to store whether infeasibility is found
nreductions	pointer to store number of reductions
peekmode	whether function is called in peek mode
varidx1	index of var1 (or NULL)
varidx2	index of var2 (or NULL)
peeklbs	lower bounds of variables in peek mode (or NULL)
peekubs	upper bounds of variables in peek mode (or NULL)
peekbdset	whether peek bounds have been set (or NULL)

Definition at line 1003 of file symmetry_lexred.c.

References alwaysLTshiftedVars(), NULL, propagateLowerBoundVar(), propagateSelfReflectionVar(), propagateUpperBoundSymVar(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propagateStaticLexred().

peekStaticLexredIsFeasible()

static SCIP_RETCODE peekStaticLexredIsFeasible ( SCIP *  scip, LEXDATA *  lexdata, int *  varorder, int  nselvars, int  fixi, int  fixj, int  fixrow, SCIP_Real  fixvaluei, SCIP_Real  fixvaluej, SCIP_Bool *  peekfeasible, SCIP_Real *  peeklbs, SCIP_Real *  peekubs, SCIP_Bool *  peekbdset  )

static

checks if the static lexred with a certain variable ordering is feasible in the hypothetical scenario where variables with indices i and j are fixed to fixvalue (i.e., peeking)

Parameters

scip	SCIP data structure
lexdata	pointer to data for this permutation
varorder	array populated with variable order (or NULL for static propagation)
nselvars	number of variables in the ordering
fixi	variable index of left fixed column
fixj	variable index of right fixed column
fixrow	row index in var ordering, from which to start peeking
fixvaluei	value on which variables i is fixed
fixvaluej	value on which variables j is fixed
peekfeasible	pointer to store whether this is feasible or not
peeklbs	lower bounds of variables in peek mode (or NULL)
peekubs	upper bounds of variables in peek mode (or NULL)
peekbdset	whether peek bounds have been set (or NULL)

Definition at line 1076 of file symmetry_lexred.c.

References alwaysLTshiftedVars(), canGTshiftedVars(), FALSE, LexRedPermData::invperm, NULL, LexRedPermData::nvars, LexRedPermData::perm, propagateLowerBoundVar(), propagateUpperBoundSymVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SYM_SYMTYPE_SIGNPERM, LexRedPermData::symtype, TRUE, LexRedPermData::vardomaincenter, varOrderGetIndex(), and LexRedPermData::vars.

Referenced by propagateStaticLexred().

propagateStaticLexred()

static SCIP_RETCODE propagateStaticLexred ( SCIP *  scip, LEXDATA *  lexdata, int *  varorder, int  nselvars, SCIP_Bool *  infeasible, int *  nreductions  )

static

propagates static lexicographic reduction with specified variable ordering

Parameters

scip	SCIP data structure
lexdata	pointer to data for this permutation
varorder	array populated with variable order (or NULL if static propagation)
nselvars	number of variables in the ordering
infeasible	pointer to store whether the problem is infeasible
nreductions	pointer to store the number of found domain reductions

Definition at line 1204 of file symmetry_lexred.c.

References canGTshiftedVars(), FALSE, getVarBounds(), LexRedPermData::invperm, NULL, LexRedPermData::nvars, peekStaticLexredIsFeasible(), LexRedPermData::perm, propagateVariablePair(), SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBufferArray, SCIPisIntegral(), SCIPsymEQ(), SCIPsymGE(), SCIPsymGT(), SCIPsymLE(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetType(), SYM_SYMTYPE_SIGNPERM, LexRedPermData::symtype, TRUE, LexRedPermData::vardomaincenter, varOrderGetIndex(), and LexRedPermData::vars.

Referenced by propagateLexredDynamic(), and propagateLexredStatic().

propagateLexredDynamic()

static SCIP_RETCODE propagateLexredDynamic ( SCIP *  scip, SCIP_LEXREDDATA *  masterdata, LEXDATA *  lexdata, NODEDEPTHBRANCHINDEX *  nodedepthbranchindices, int  nvarstotal, SCIP_VAR **  branchvars, int  nbranchvars, SCIP_Bool *  infeasible, int *  nreductions  )

static

propagation method for a dynamic lexicographic reduction

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
lexdata	pointer to data for this permutation
nodedepthbranchindices	array with (depth, index)-information per variable in rooted path to focus node
nvarstotal	length of nodedepthbranchindices array
branchvars	array populated with variables branched on
nbranchvars	number of elements in branchvars array
infeasible	pointer to store whether the problem is infeasible
nreductions	pointer to store the number of found domain reductions

Definition at line 1536 of file symmetry_lexred.c.

References getVarOrder(), LexRedPermData::isdynamic, VarArrayNodeDepthBranchIndex::masterdata, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, LexRedPermData::nvars, propagateStaticLexred(), SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, and SCIPfreeBufferArray.

Referenced by propagateLexicographicReductionPerm().

propagateLexredStatic()

static SCIP_RETCODE propagateLexredStatic ( SCIP *  scip, SCIP_LEXREDDATA *  masterdata, LEXDATA *  lexdata, SCIP_Bool *  infeasible, int *  nreductions  )

static

propagation method for a dynamic lexicographic reduction

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
lexdata	pointer to data for this permutation
infeasible	pointer to store whether the problem is infeasible
nreductions	pointer to store the number of found domain reductions

Definition at line 1586 of file symmetry_lexred.c.

References LexRedPermData::isdynamic, VarArrayNodeDepthBranchIndex::masterdata, NULL, LexRedPermData::nvars, propagateStaticLexred(), SCIP_CALL, and SCIP_OKAY.

Referenced by propagateLexicographicReductionPerm().

propagateLexicographicReductionPerm()

static SCIP_RETCODE propagateLexicographicReductionPerm ( SCIP *  scip, SCIP_LEXREDDATA *  masterdata, LEXDATA *  lexdata, NODEDEPTHBRANCHINDEX *  nodedepthbranchindices, int  nvarstotal, SCIP_VAR **  branchvars, int  nbranchvars, SCIP_Bool *  infeasible, int *  nreductions  )

static

propagation method for applying dynamic lexicographic reduction for a single permutation

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
lexdata	pointer to data for this permutation
nodedepthbranchindices	array with (depth, index)-information per variable in rooted path to focus node
nvarstotal	length of that array
branchvars	array populated with variables branched on
nbranchvars	number of elements in branchvars array
infeasible	pointer to store whether the problem is infeasible
nreductions	pointer to store the number of found domain reductions

Definition at line 1614 of file symmetry_lexred.c.

References FALSE, LexRedPermData::isdynamic, VarArrayNodeDepthBranchIndex::masterdata, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, propagateLexredDynamic(), propagateLexredStatic(), SCIP_CALL, and SCIP_OKAY.

Referenced by SCIPlexicographicReductionPropagate().

shadowtreeFillNodeDepthBranchIndices()

static SCIP_RETCODE shadowtreeFillNodeDepthBranchIndices ( SCIP *  scip, SCIP_LEXREDDATA *  masterdata, NODEDEPTHBRANCHINDEX *  nodedepthbranchindices, SCIP_VAR **  branchvars, int *  nbranchvars, SCIP_SHADOWTREE *  shadowtree, SCIP_NODE *  focusnode, SCIP_Bool *  inforesolved  )

static

populates array with information of first variable change

Precondition

assuming nodedepthbranchindices is initially clean

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
nodedepthbranchindices	array to populate
branchvars	array to populate with variables branched on
nbranchvars	number of elements in branchvars array
shadowtree	pointer to shadow tree structure
focusnode	focusnode to which the rooted path is evaluated
inforesolved	pointer to store whether information is successfully resolved

Definition at line 1657 of file symmetry_lexred.c.

References SCIP_ShadowNode::branchingdecisions, SCIP_ShadowNode::children, FALSE, NodeDepthBranchIndex::index, VarArrayNodeDepthBranchIndex::masterdata, SCIP_ShadowNode::nbranchingdecisions, SCIP_ShadowNode::nchildren, NodeDepthBranchIndex::nodedepth, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, SCIP_ShadowNode::parent, SCIP_OKAY, SCIPhashmapGetImageInt(), SCIPnodeGetDepth(), SCIPshadowTreeGetShadowNode(), SCIPvarIsTransformed(), SCIPwarningMessage(), TRUE, and SCIP_ShadowBoundUpdate::var.

Referenced by SCIPlexicographicReductionPropagate().

shadowtreeUndoNodeDepthBranchIndices()

static SCIP_RETCODE shadowtreeUndoNodeDepthBranchIndices ( SCIP *  scip, SCIP_LEXREDDATA *  masterdata, NODEDEPTHBRANCHINDEX *  nodedepthbranchindices, SCIP_VAR **  branchvars, int *  nbranchvars, SCIP_SHADOWTREE *  shadowtree, SCIP_NODE *  focusnode  )

static

cleans nodedepthbranchindices array

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
nodedepthbranchindices	array populated by nodedepthbranchindices to clean
branchvars	array populated with variables branched on
nbranchvars	number of elements in branchvars array
shadowtree	pointer to shadow tree structure
focusnode	focusnode to which the rooted path is evaluated

Definition at line 1773 of file symmetry_lexred.c.

References SCIP_ShadowNode::branchingdecisions, SCIP_ShadowNode::children, NodeDepthBranchIndex::index, VarArrayNodeDepthBranchIndex::masterdata, SCIP_ShadowNode::nbranchingdecisions, SCIP_ShadowNode::nchildren, NodeDepthBranchIndex::nodedepth, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, SCIP_ShadowNode::parent, SCIP_OKAY, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPnodeGetDepth(), SCIPshadowTreeGetShadowNode(), and SCIP_ShadowBoundUpdate::var.

Referenced by SCIPlexicographicReductionPropagate().

SCIPlexicographicReductionGetStatistics()

SCIP_RETCODE SCIPlexicographicReductionGetStatistics	(	SCIP *	scip,
		SCIP_LEXREDDATA *	masterdata,
		int *	nred,
		int *	ncutoff
	)

prints lexicographic reduction propagation data

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
nred	total number of reductions applied
ncutoff	total number of cutoffs applied

Definition at line 1871 of file symmetry_lexred.c.

References VarArrayNodeDepthBranchIndex::masterdata, NULL, and SCIP_OKAY.

Referenced by SCIP_DECL_TABLEOUTPUT().

SCIPlexicographicReductionPrintStatistics()

SCIP_RETCODE SCIPlexicographicReductionPrintStatistics	(	SCIP *	scip,
		SCIP_LEXREDDATA *	masterdata
	)

prints lexicographic reduction propagation data

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator

Definition at line 1889 of file symmetry_lexred.c.

References VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, and SCIPverbMessage().

Referenced by SCIPdisplaySymmetryStatistics().

SCIPlexicographicReductionPropagate()

SCIP_RETCODE SCIPlexicographicReductionPropagate	(	SCIP *	scip,
		SCIP_LEXREDDATA *	masterdata,
		SCIP_Bool *	infeasible,
		int *	nred,
		SCIP_Bool *	didrun
	)

applies lexicographic reduction propagation

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
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 1922 of file symmetry_lexred.c.

References FALSE, VarArrayNodeDepthBranchIndex::masterdata, VarArrayNodeDepthBranchIndex::nodedepthbranchindices, NULL, propagateLexicographicReductionPerm(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPgetFocusNode(), SCIPgetShadowTree(), shadowtreeFillNodeDepthBranchIndices(), shadowtreeUndoNodeDepthBranchIndices(), and TRUE.

Referenced by propagateSymmetry().

SCIPlexicographicReductionAddPermutation()

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
	)

adds permutation for lexicographic reduction propagation

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
permvars	variable array of the permutation
npermvars	number of variables in that array
perm	permutation
symtype	type of symmetries in perm
permvardomaincenter	array containing center point for each variable domain
usedynamicorder	whether a dynamic variable order shall be used
success	to store whether the component is successfully added

Definition at line 2033 of file symmetry_lexred.c.

References FALSE, lexdataCreate(), VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPisTransformed(), SCIPreallocBlockMemoryArray, SYM_SYMTYPE_PERM, and SYM_SYMTYPE_SIGNPERM.

Referenced by addOrbitopesDynamic(), and tryAddOrbitalRedLexRed().

SCIPlexicographicReductionReset()

SCIP_RETCODE SCIPlexicographicReductionReset	(	SCIP *	scip,
		SCIP_LEXREDDATA *	masterdata
	)

resets lexicographic reduction propagation (removes all permutations)

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator

Definition at line 2097 of file symmetry_lexred.c.

References FALSE, lexdataFree(), VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPhashmapFree().

Referenced by resetDynamicSymmetryHandling(), and SCIPlexicographicReductionFree().

SCIPlexicographicReductionFree()

SCIP_RETCODE SCIPlexicographicReductionFree	(	SCIP *	scip,
		SCIP_LEXREDDATA **	masterdata
	)

frees lexicographic reduction data

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator

Definition at line 2135 of file symmetry_lexred.c.

References VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPlexicographicReductionReset().

Referenced by SCIP_DECL_PROPFREE().

SCIPincludeLexicographicReduction()

SCIP_RETCODE SCIPincludeLexicographicReduction	(	SCIP *	scip,
		SCIP_LEXREDDATA **	masterdata,
		SCIP_EVENTHDLR *	shadowtreeeventhdlr
	)

initializes structures needed for lexicographic reduction propagation

This is only done exactly once.

Parameters

scip	SCIP data structure
masterdata	pointer to global data for lexicographic reduction propagator
shadowtreeeventhdlr	pointer to the shadow tree eventhdlr

Definition at line 2158 of file symmetry_lexred.c.

References FALSE, VarArrayNodeDepthBranchIndex::masterdata, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPcheckStage(), and TRUE.

Referenced by SCIPincludePropSymmetry().