symmetry_orbitopal.c File Reference

Detailed Description

methods for handling orbitopal symmetries

Author

Jasper van Doornmalen

This implements orbitopal reducion, which generalizes full orbitope propagation to work for non-binary variable domains, and is dynamified. See cons_orbitope.c for the variant for binary variables, both the static and partially dynamic variant. 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.

See Section 4.2, Example 12 and Section 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.

Orbitopal reduction can be used to handle symmetries of the following type. If the variables can be arranged in a matrix and the symmetries correspond to all column permutations of this matrix, then these symmetries are called orbitopal. Symmetry is completely handled by enforcing that the columns are lexicographically decreasing. If a reduction on a variable is applied, and if this variable is high up in the variable matrix, then this has a relatively large impact on the lexicographic ordering. Moreover, the ordering of the columns also matter. Dynamification allows for choosing a custom ordering of a subset of rows and a permutation of the columns. For every node, we maintain the ordered subset of rows and the column order. The root node assumes no rows and an arbitrary column order (we choose the identity). If towards a new node it is branched on a variable, that appears in a row which is not included in the subset of rows for the current node, then the row set of the new children is the ordered row set of the current node, appended by this new row. For the column order, if at the current node columns are symmetrically equivalent, then these can be permuted for the sake of symmetry handling. In the implementation, we only swap the column containing the branching variable with a symmetrically equivalent column elsewhere. We use one of the following heuristics:

• None: Keep the column-order as-is.
• First: Permute such that the column containing the branching variable is in the symmetrically equivalent column with minimal index.
• Last: The same, but to the symmetrically equivalent column with maximal index.
• Centre: The same, but to the symmetrically equivalent column closest to to the middlemost column among all columns.
• Median: The same, but to the median of all symmetrically equivalent columns. (This is the default)

Since the dynamic row and column ordering rule for a branch-and-bound tree node depends on the decisions made up to that branch-and-bound tree node, we compute and store the row and column order for the branch-and-bound tree children at the moment of branching. This is done by the eventhandler in this file. Instead of storing those, we could have chosen to reconstruct this row and column ordering to save memory. However, we cannot reliably reconstruct this order from the branch-and-bound tree itself, because the row and column ordering depends on symmetrical equivalence of columns in the orbitope matrix, and because SCIP can change the tree structure during solving that may re-write historic variable bound changes (for instance when global variable bound changes are found, or when the root node is moved down the tree to become the new effective root node). We are not concerned about storing the row and column ordering, since we only store the mutations with its parent. These are usually at most one column swap and usually at most one additional row.

Author

Jasper van Doornmalen

Definition in file symmetry_orbitopal.c.

#include "blockmemshell/memory.h"
#include "scip/symmetry_orbitopal.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/struct_scip.h"
#include "scip/struct_mem.h"
#include "scip/struct_tree.h"
#include "scip/symmetry.h"
#include "scip/debug.h"
#include "symmetry/type_symmetry.h"
#include <string.h>

Go to the source code of this file.

Data Structures
struct	OrbitopeData
struct	ColSwap
struct	BnbNodeInfo

Macros
#define	SYMHDLR_NAME   "orbitopalreduction"
#define	EVENTHDLR_NAME   "symmetry_orbitopal_eventhdlr"
#define	EVENTHDLR_DESC   "event handler for maintaining the branch-and-bound tree"
#define	DEFAULT_COLUMNORDERING   SCIP_COLUMNORDERING_MEDIAN

Typedefs
typedef struct OrbitopeData	ORBITOPEDATA
typedef struct ColSwap	COLSWAP
typedef struct BnbNodeInfo	BNBNODEINFO

Functions
static SCIP_Bool	vartypeIsBranchRowType (SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_VARTYPE vartype)
static	SCIP_DECL_HASHGETKEY (hashGetKeyBnbnodeinfo)
static	SCIP_DECL_HASHKEYEQ (hashKeyEqBnbnodeinfo)
static	SCIP_DECL_HASHKEYVAL (hashKeyValBnbnodeinfo)
static SCIP_Bool	testColumnsAreSymmetricallyEquivalent (SCIP *scip, ORBITOPEDATA *orbidata, int col1, int col2)
static SCIP_RETCODE	updateColumnOrderWhenBranchingOnColumn (SCIP *scip, ORBITOPEDATA *orbidata, int *colorder, int *colorderinv, SCIP_VAR *var, COLSWAP *thiscolswap)
static int	getArrayEntryOrIndex (int *arr, int idx)
static void	freeRowOrder (SCIP *scip, ORBITOPEDATA *orbidata, int **roworder)
static SCIP_RETCODE	getRowOrder (SCIP *scip, ORBITOPEDATA *orbidata, SCIP_NODE *node, int **roworder, int *nselrows)
static SCIP_RETCODE	populateRootedPathColumnOrder (ORBITOPEDATA *orbidata, SCIP_NODE *node, SCIP_NODE **rootedpath, int *colorder, int *colorderinv)
static	SCIP_DECL_EVENTEXEC (eventExecNodeBranched)
static	SCIP_DECL_EVENTEXEC (eventExec)
static SCIP_Bool	rowIsBranchRow (SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, ORBITOPEDATA *orbidata, int rowid)
static SCIP_RETCODE	freeOrbitope (SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, ORBITOPEDATA **orbidata)
static SCIP_RETCODE	addOrbitope (SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_ROWORDERING rowordering, SCIP_COLUMNORDERING colordering, SCIP_VAR **vars, int nrows, int ncols, SCIP_Bool *success)
static void	freeColumnOrder (SCIP *scip, ORBITOPEDATA *orbidata, int **colorder, int **colorderinv)
static SCIP_RETCODE	getColumnOrder (SCIP *scip, ORBITOPEDATA *orbidata, SCIP_NODE *eventnode, int **colorder, int **colorderinv)
static void	assertIsOrbitopeMatrix (SCIP *scip, ORBITOPEDATA *orbidata, int *roworder, int *colorder, SCIP_Real *matrix, int nrows, int ncols, int *infinitesimal, SCIP_Bool addinfinitesimals)
static int	debugGetArrayHash (int *array, int len)
static SCIP_RETCODE	propagateStaticOrbitope (SCIP *scip, ORBITOPEDATA *orbidata, int *roworder, int nselrows, int *colorder, SCIP_Bool *infeasible, int *nfixedvars)
static SCIP_RETCODE	propagateOrbitope (SCIP *scip, ORBITOPEDATA *orbidata, SCIP_Bool *infeasible, int *nfixedvars)
SCIP_RETCODE	SCIPorbitopalReductionGetStatistics (SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, int *nred, int *ncutoff)
SCIP_RETCODE	SCIPorbitopalReductionPrintStatistics (SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
SCIP_RETCODE	SCIPorbitopalReductionPropagate (SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_Bool *infeasible, int *nred, SCIP_Bool *didrun)
SCIP_RETCODE	SCIPorbitopalReductionAddOrbitope (SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata, SCIP_ROWORDERING rowordering, SCIP_COLUMNORDERING colordering, SCIP_VAR **vars, int nrows, int ncols, SCIP_Bool *success)
SCIP_RETCODE	SCIPorbitopalReductionReset (SCIP *scip, SCIP_ORBITOPALREDDATA *orbireddata)
SCIP_RETCODE	SCIPorbitopalReductionFree (SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
SCIP_RETCODE	SCIPincludeOrbitopalReduction (SCIP *scip, SCIP_ORBITOPALREDDATA **orbireddata)
SCIP_COLUMNORDERING	SCIPorbitopalReductionGetDefaultColumnOrdering (SCIP_ORBITOPALREDDATA *orbireddata)

Macro Definition Documentation

SYMHDLR_NAME

#define SYMHDLR_NAME   "orbitopalreduction"

Definition at line 114 of file symmetry_orbitopal.c.

EVENTHDLR_NAME

#define EVENTHDLR_NAME   "symmetry_orbitopal_eventhdlr"

Definition at line 117 of file symmetry_orbitopal.c.

EVENTHDLR_DESC

#define EVENTHDLR_DESC   "event handler for maintaining the branch-and-bound tree"

Definition at line 118 of file symmetry_orbitopal.c.

DEFAULT_COLUMNORDERING

#define DEFAULT_COLUMNORDERING   SCIP_COLUMNORDERING_MEDIAN

the column ordering variant

Definition at line 119 of file symmetry_orbitopal.c.

Typedef Documentation

ORBITOPEDATA

typedef struct OrbitopeData ORBITOPEDATA

orbitopal symmetry handling data for a single orbitope

Definition at line 142 of file symmetry_orbitopal.c.

COLSWAP

typedef struct ColSwap COLSWAP

Definition at line 201 of file symmetry_orbitopal.c.

BNBNODEINFO

typedef struct BnbNodeInfo BNBNODEINFO

Definition at line 212 of file symmetry_orbitopal.c.

Function Documentation

vartypeIsBranchRowType()

static SCIP_Bool vartypeIsBranchRowType ( SCIP *  scip, SCIP_ORBITOPALREDDATA *  orbireddata, SCIP_VARTYPE  vartype  )

static

gets whether a variable type is a branchrow-type

Parameters

scip	SCIP data structure
orbireddata	pointer to the dynamic orbitopal reduction data
vartype	var type

Definition at line 165 of file symmetry_orbitopal.c.

References FALSE, NULL, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPABORT, SCIPconshdlrGetNActiveConss(), SCIPerrorMessage, and TRUE.

Referenced by rowIsBranchRow().

SCIP_DECL_HASHGETKEY()

static SCIP_DECL_HASHGETKEY ( hashGetKeyBnbnodeinfo  )

static

hash key for virtual branch and bound nodeinfo struct

Definition at line 216 of file symmetry_orbitopal.c.

SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashKeyEqBnbnodeinfo  )

static

returns TRUE iff the indices of both node numbers are equal

Definition at line 223 of file symmetry_orbitopal.c.

References BnbNodeInfo::nodenumber.

SCIP_DECL_HASHKEYVAL()

static SCIP_DECL_HASHKEYVAL ( hashKeyValBnbnodeinfo  )

static

returns the hash value of the key

Definition at line 232 of file symmetry_orbitopal.c.

References BnbNodeInfo::nodenumber.

testColumnsAreSymmetricallyEquivalent()

static SCIP_Bool testColumnsAreSymmetricallyEquivalent ( SCIP *  scip, ORBITOPEDATA *  orbidata, int  col1, int  col2  )

static

tests if two columns are symmetrically equivalent

We test if the columns with index col1 and col2 have elementwise the same bounds. If all symmetry-compatible reductions are applied, then it suffices to check only as many rows as are selected for orbitopal reduction. However, to be resilient to reductions that are not symmetry-compatible, we test all variables in the columns.

Parameters

scip	SCIP data structure
orbidata	orbitope information
col1	first column to compare
col2	second column to compare

Definition at line 247 of file symmetry_orbitopal.c.

References FALSE, OrbitopeData::ncols, OrbitopeData::nrows, NULL, SCIPsymEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), TRUE, and OrbitopeData::vars.

Referenced by updateColumnOrderWhenBranchingOnColumn().

updateColumnOrderWhenBranchingOnColumn()

static SCIP_RETCODE updateColumnOrderWhenBranchingOnColumn ( SCIP *  scip, ORBITOPEDATA *  orbidata, int *  colorder, int *  colorderinv, SCIP_VAR *  var, COLSWAP *  thiscolswap  )

static

updates the column order with a bound change

When it is branched on a variable in a column, update the column order for the children of the focusnode. Symmetrically equivalent columns, that is the columns where the variables have elementwise the same domain, at the focusnode at the moment of branching can be permuted. In this function, we select such a permutation, based on the column containing the branching variable(s). In all cases, we swap the column containing the branching variable with a symmetrically equivalent column, and the columnordering specifies if we prefer it to be the leftmost, rightmost, centermost symmetrically equivalent column, or the median column among the symmetrically equivalent columns.

The column ordering is determined and stored at the moment of branching.

Parameters

scip	SCIP data structure
orbidata	orbitope data
colorder	array to populate with column order, of size colorder
colorderinv	inverse array of the column order, of size colorder
var	variable that we branch on
thiscolswap	the colswap to populate

Definition at line 297 of file symmetry_orbitopal.c.

References ABS, OrbitopeData::colindexmap, OrbitopeData::columnordering, ColSwap::from, OrbitopeData::ncols, OrbitopeData::nrows, BnbNodeInfo::nrows, NULL, SCIP_CALL, SCIP_COLUMNORDERING_CENTRE, SCIP_COLUMNORDERING_FIRST, SCIP_COLUMNORDERING_LAST, SCIP_COLUMNORDERING_MEDIAN, SCIP_COLUMNORDERING_NONE, SCIP_ERROR, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPdebugPrintf, SCIPfreeBufferArray, SCIPhashmapGetImageInt(), SCIPsortInd(), SCIPsymEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), testColumnsAreSymmetricallyEquivalent(), ColSwap::to, and OrbitopeData::vars.

Referenced by SCIP_DECL_EVENTEXEC().

getArrayEntryOrIndex()

static int getArrayEntryOrIndex ( int *  arr, int  idx  )

static

yields entry at index in array, or returns entry if array is NULL

Parameters

arr	array
idx	index

Definition at line 521 of file symmetry_orbitopal.c.

References NULL.

Referenced by assertIsOrbitopeMatrix(), and propagateStaticOrbitope().

freeRowOrder()

static void freeRowOrder ( SCIP *  scip, ORBITOPEDATA *  orbidata, int **  roworder  )

static

frees the row order

Parameters

scip	SCIP data structure
orbidata	orbitope data
roworder	roworder array that is initialized with the roworder in the dynamic case, and NULL in the static case

Definition at line 534 of file symmetry_orbitopal.c.

References OrbitopeData::nrows, NULL, OrbitopeData::rowordering, SCIP_ROWORDERING_BRANCHING, SCIP_ROWORDERING_NONE, and SCIPfreeBlockMemoryArray.

Referenced by propagateOrbitope(), and SCIP_DECL_EVENTEXEC().

getRowOrder()

static SCIP_RETCODE getRowOrder ( SCIP *  scip, ORBITOPEDATA *  orbidata, SCIP_NODE *  node, int **  roworder, int *  nselrows  )

static

gets the row order at the node

this is NULL (i.e., the identity map) in the static (none) setting. this is an array of size orbidata->nrows in the dynamic (branching) setting.

The row order is given in the order of the variables that is branched on.

Parameters

scip	SCIP data structure
orbidata	orbitope data
node	node for which the row order should be detected
roworder	array to populate with row order
nselrows	pointer to populate with the number of rows part of the row order

Definition at line 567 of file symmetry_orbitopal.c.

References OrbitopeData::ncols, OrbitopeData::nodeinfos, BnbNodeInfo::nodenumber, OrbitopeData::nrows, BnbNodeInfo::nrows, NULL, OrbitopeData::rowordering, BnbNodeInfo::rows, SCIP_CALL, SCIP_OKAY, SCIP_ROWORDERING_BRANCHING, SCIP_ROWORDERING_NONE, SCIPallocBlockMemoryArray, SCIPhashtableRetrieve(), SCIPnodeGetNumber(), and SCIPnodeGetParent().

Referenced by propagateOrbitope(), and SCIP_DECL_EVENTEXEC().

populateRootedPathColumnOrder()

static SCIP_RETCODE populateRootedPathColumnOrder ( ORBITOPEDATA *  orbidata, SCIP_NODE *  node, SCIP_NODE **  rootedpath, int *  colorder, int *  colorderinv  )

static

gets rooted path up to node and populates column ordering array

Parameters

orbidata	orbitope data
node	node considered
rootedpath	array to populate with the rooted path, must be sufficiently long
colorder	array to populate with the column order, must be nvars long
colorderinv	array to populate with the inverse column order, must be nvars long

Definition at line 644 of file symmetry_orbitopal.c.

References BnbNodeInfo::colswaps, ColSwap::from, OrbitopeData::ncols, BnbNodeInfo::ncolswaps, OrbitopeData::nodeinfos, BnbNodeInfo::nodenumber, NULL, SCIP_OKAY, SCIPhashtableRetrieve(), SCIPnodeGetDepth(), SCIPnodeGetNumber(), SCIPnodeGetParent(), and ColSwap::to.

Referenced by getColumnOrder(), and SCIP_DECL_EVENTEXEC().

SCIP_DECL_EVENTEXEC() [1/2]

static SCIP_DECL_EVENTEXEC ( eventExecNodeBranched  )

static

at branching decisions, maintains the column swap and potential new rows in the orbitope

Definition at line 727 of file symmetry_orbitopal.c.

References OrbitopeData::colindexmap, BnbNodeInfo::colswaps, OrbitopeData::columnordering, freeRowOrder(), ColSwap::from, getRowOrder(), OrbitopeData::ncols, BnbNodeInfo::ncolswaps, OrbitopeData::nodeinfos, BnbNodeInfo::nodenumber, OrbitopeData::nrows, BnbNodeInfo::nrows, NULL, populateRootedPathColumnOrder(), OrbitopeData::rowindexmap, OrbitopeData::rowordering, BnbNodeInfo::rows, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_CALL, SCIP_COLUMNORDERING_NONE, SCIP_OKAY, SCIP_ROWORDERING_BRANCHING, SCIP_ROWORDERING_NONE, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPboundchgGetBoundchgtype(), SCIPboundchgGetVar(), SCIPcalcMemGrowSize(), SCIPdomchgGetBoundchg(), SCIPdomchgGetNBoundchgs(), SCIPeventGetNode(), SCIPfreeBlockMemory, SCIPfreeBufferArray, SCIPgetChildren(), SCIPgetFocusNode(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashtableSafeInsert(), SCIPinProbing(), SCIPnodeGetDepth(), SCIPnodeGetDomchg(), SCIPnodeGetNumber(), SCIPnodeGetParent(), SCIPreallocBlockMemoryArray, SCIPreallocBufferArray, ColSwap::to, updateColumnOrderWhenBranchingOnColumn(), and OrbitopeData::vars.

SCIP_DECL_EVENTEXEC() [2/2]

static SCIP_DECL_EVENTEXEC ( eventExec  )

static

at branching decisions, maintains the column swap and potential new rows in the orbitope

Definition at line 974 of file symmetry_orbitopal.c.

References EVENTHDLR_NAME, SCIP_ERROR, SCIP_EVENTTYPE_NODEBRANCHED, SCIPerrorMessage, and SCIPeventGetType().

rowIsBranchRow()

static SCIP_Bool rowIsBranchRow ( SCIP *  scip, SCIP_ORBITOPALREDDATA *  orbireddata, ORBITOPEDATA *  orbidata, int  rowid  )

static

returns whether a row contains potential branching variables

Parameters

scip	SCIP data structure
orbireddata	pointer to the dynamic orbitopal reduction data
orbidata	symmetry handling data for orbitopal structure
rowid	row id for which to check

Definition at line 989 of file symmetry_orbitopal.c.

References OrbitopeData::ncols, OrbitopeData::nrows, BnbNodeInfo::nrows, NULL, SCIPvarGetType(), OrbitopeData::vars, and vartypeIsBranchRowType().

Referenced by addOrbitope().

freeOrbitope()

static SCIP_RETCODE freeOrbitope ( SCIP *  scip, SCIP_ORBITOPALREDDATA *  orbireddata, ORBITOPEDATA **  orbidata  )

static

frees orbitope data

Parameters

scip	SCIP data structure
orbireddata	pointer to the dynamic orbitopal reduction data
orbidata	pointer to orbitope data

Definition at line 1032 of file symmetry_orbitopal.c.

References BnbNodeInfo::colswaps, BnbNodeInfo::ncolswaps, BnbNodeInfo::nrows, NULL, BnbNodeInfo::rows, SCIP_CALL, SCIP_COLUMNORDERING_NONE, SCIP_EVENTTYPE_NODEBRANCHED, SCIP_OKAY, SCIP_ROWORDERING_NONE, SCIPdropEvent(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPhashmapFree(), SCIPhashtableFree(), SCIPhashtableGetEntry(), SCIPhashtableGetNEntries(), SCIPisTransformed(), and SCIPreleaseVar().

Referenced by SCIPorbitopalReductionReset().

addOrbitope()

static SCIP_RETCODE addOrbitope ( SCIP *  scip, SCIP_ORBITOPALREDDATA *  orbireddata, SCIP_ROWORDERING  rowordering, SCIP_COLUMNORDERING  colordering, SCIP_VAR **  vars, int  nrows, int  ncols, SCIP_Bool *  success  )

static

adds an orbitope to the orbitopal reduction data

Parameters

scip	SCIP data structure
orbireddata	pointer to the dynamic orbitopal reduction data
rowordering	specifies how rows of orbitope are ordered
colordering	specifies how columnss of orbitope are ordered
vars	variables array, must have size nrows * ncols
nrows	number of rows in orbitope
ncols	number of columns in orbitope
success	to store whether the component is successfully added

Definition at line 1106 of file symmetry_orbitopal.c.

References OrbitopeData::colindexmap, OrbitopeData::columnordering, OrbitopeData::dbghash, FALSE, OrbitopeData::lastnodenumber, MIN, SCIP_Var::name, OrbitopeData::nbranchrows, OrbitopeData::ncols, OrbitopeData::nrows, BnbNodeInfo::nrows, NULL, OrbitopeData::rowindexmap, rowIsBranchRow(), OrbitopeData::rowordering, SCIP_CALL, SCIP_COLUMNORDERING_NONE, SCIP_EVENTTYPE_NODEBRANCHED, SCIP_OKAY, SCIP_ROWORDERING_NONE, SCIP_STAGE_SOLVING, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPcaptureVar(), SCIPcatchEvent(), SCIPdebugMessage, SCIPdebugMsg, SCIPgetNNodes(), SCIPgetStage(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapInsertInt(), SCIPhashtableCreate(), SCIPmarkDoNotMultaggrVar(), SCIPreallocBlockMemoryArray, SCIPvarIsTransformed(), TRUE, and OrbitopeData::vars.

Referenced by SCIPorbitopalReductionAddOrbitope().

freeColumnOrder()

static void freeColumnOrder ( SCIP *  scip, ORBITOPEDATA *  orbidata, int **  colorder, int **  colorderinv  )

static

frees the column order

Parameters

scip	SCIP data structure
orbidata	orbitope data
colorder	colorder array that is initialized with the colorder in the dynamic case, of size ncols, and NULL in the static case
colorderinv	array with the inverse column order, of size ncols

Definition at line 1261 of file symmetry_orbitopal.c.

References OrbitopeData::columnordering, OrbitopeData::ncols, NULL, SCIP_COLUMNORDERING_NONE, and SCIPfreeBlockMemoryArray.

Referenced by propagateOrbitope().

getColumnOrder()

static SCIP_RETCODE getColumnOrder ( SCIP *  scip, ORBITOPEDATA *  orbidata, SCIP_NODE *  eventnode, int **  colorder, int **  colorderinv  )

static

gets the column order at the node

The column order is (deterministically) dynamically decided based on the policy for column ordering.

Parameters

scip	SCIP data structure
orbidata	orbitope data
eventnode	node where this should be determined at
colorder	array to populate with column order, of size ncols
colorderinv	array to populate with inverse column order, of size ncols

Definition at line 1293 of file symmetry_orbitopal.c.

References OrbitopeData::columnordering, OrbitopeData::ncols, NULL, populateRootedPathColumnOrder(), SCIP_CALL, SCIP_COLUMNORDERING_NONE, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPnodeGetDepth(), and SCIPnodeGetParent().

Referenced by propagateOrbitope().

assertIsOrbitopeMatrix()

static void assertIsOrbitopeMatrix ( SCIP *  scip, ORBITOPEDATA *  orbidata, int *  roworder, int *  colorder, SCIP_Real *  matrix, int  nrows, int  ncols, int *  infinitesimal, SCIP_Bool  addinfinitesimals  )

static

checks if the columns of the matrix are lexicographically decreasing, using the specified row and column ordering

Parameters

scip	SCIP data structure
orbidata	orbitope data
roworder	array with the row order
colorder	array with the column order
matrix	a matrix
nrows	number of rows of matrix
ncols	number of cols of matrix
infinitesimal	array specifying where the infinitesimals are at
addinfinitesimals	whether infinitesimals are added (TRUE) or subtracted (FALSE)

Definition at line 1353 of file symmetry_orbitopal.c.

References getArrayEntryOrIndex(), BnbNodeInfo::nrows, NULL, SCIPsymEQ(), SCIPsymGE(), SCIPsymGT(), SCIPsymLE(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and OrbitopeData::vars.

Referenced by propagateStaticOrbitope().

debugGetArrayHash()

static int debugGetArrayHash ( int *  array, int  len  )

static

to test if arrays are the same, generates some hash for an array of integers

Parameters

array	array
len	array length

Definition at line 1438 of file symmetry_orbitopal.c.

References NULL.

Referenced by propagateOrbitope().

propagateStaticOrbitope()

static SCIP_RETCODE propagateStaticOrbitope ( SCIP *  scip, ORBITOPEDATA *  orbidata, int *  roworder, int  nselrows, int *  colorder, SCIP_Bool *  infeasible, int *  nfixedvars  )

static

gets the column order at the node

Parameters

scip	SCIP data structure
orbidata	orbitope data
roworder	array with the row order (or NULL if identity function is used)
nselrows	number of selected rows
colorder	array with the column order (or NULL if identity function is used)
infeasible	pointer to store whether the problem is infeasible
nfixedvars	pointer to counter of number of variable domain reductions

Definition at line 1490 of file symmetry_orbitopal.c.

References assertIsOrbitopeMatrix(), FALSE, getArrayEntryOrIndex(), MAX, MIN, SCIP_Var::name, OrbitopeData::ncols, OrbitopeData::nrows, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPdebugMessage, SCIPdebugPrintf, SCIPfreeBufferArrayNull, SCIPisIntegral(), SCIPsymEQ(), SCIPsymGE(), SCIPsymGT(), SCIPsymLE(), SCIPsymLT(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), TRUE, and OrbitopeData::vars.

Referenced by propagateOrbitope().

propagateOrbitope()

static SCIP_RETCODE propagateOrbitope ( SCIP *  scip, ORBITOPEDATA *  orbidata, SCIP_Bool *  infeasible, int *  nfixedvars  )

static

propagation method for a single orbitope matrix

Parameters

scip	SCIP data structure
orbidata	orbitope data
infeasible	pointer to store whether the problem is infeasible
nfixedvars	pointer to store the number of found domain reductions

Definition at line 2028 of file symmetry_orbitopal.c.

References OrbitopeData::dbghash, debugGetArrayHash(), FALSE, freeColumnOrder(), freeRowOrder(), getColumnOrder(), getRowOrder(), OrbitopeData::lastnodenumber, OrbitopeData::ncols, OrbitopeData::nrows, BnbNodeInfo::nrows, NULL, SCIP_Node::number, propagateStaticOrbitope(), SCIP_CALL, SCIP_OKAY, SCIPdebugPrintf, SCIPgetCurrentNode(), SCIPgetFocusNode(), SCIPnodeGetDomchg(), SCIPnodeGetNDomchg(), SCIPnodeGetNumber(), and SCIPnodeGetParent().

Referenced by SCIPorbitopalReductionPropagate().

SCIPorbitopalReductionGetStatistics()

SCIP_RETCODE SCIPorbitopalReductionGetStatistics	(	SCIP *	scip,
		SCIP_ORBITOPALREDDATA *	orbireddata,
		int *	nred,
		int *	ncutoff
	)

gets the number of reductions

Parameters

scip	SCIP data structure
orbireddata	orbitopal reduction data structure
nred	total number of reductions applied
ncutoff	total number of cutoffs applied

Definition at line 2119 of file symmetry_orbitopal.c.

References NULL, and SCIP_OKAY.

Referenced by SCIP_DECL_TABLEOUTPUT().

SCIPorbitopalReductionPrintStatistics()

SCIP_RETCODE SCIPorbitopalReductionPrintStatistics	(	SCIP *	scip,
		SCIP_ORBITOPALREDDATA *	orbireddata
	)

prints orbitopal reduction data

Parameters

scip	SCIP data structure
orbireddata	orbitopal reduction data structure

Definition at line 2138 of file symmetry_orbitopal.c.

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

Referenced by SCIPdisplaySymmetryStatistics().

SCIPorbitopalReductionPropagate()

SCIP_RETCODE SCIPorbitopalReductionPropagate	(	SCIP *	scip,
		SCIP_ORBITOPALREDDATA *	orbireddata,
		SCIP_Bool *	infeasible,
		int *	nred,
		SCIP_Bool *	didrun
	)

propagates orbitopal reduction

Parameters

scip	SCIP data structure
orbireddata	orbitopal 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 2170 of file symmetry_orbitopal.c.

References FALSE, NULL, propagateOrbitope(), SCIP_CALL, SCIP_OKAY, SCIPallowStrongDualReds(), SCIPdebugMessage, SCIPinProbing(), and TRUE.

Referenced by propagateSymmetry().

SCIPorbitopalReductionAddOrbitope()

SCIP_RETCODE SCIPorbitopalReductionAddOrbitope	(	SCIP *	scip,
		SCIP_ORBITOPALREDDATA *	orbireddata,
		SCIP_ROWORDERING	rowordering,
		SCIP_COLUMNORDERING	colordering,
		SCIP_VAR **	vars,
		int	nrows,
		int	ncols,
		SCIP_Bool *	success
	)

adds orbitopal component to orbitopal symmetry handler

Parameters

scip	SCIP data structure
orbireddata	orbitopal reduction data structure
rowordering	specifies how rows of orbitope are ordered
colordering	specifies how columnss of orbitope are ordered
vars	matrix of variables on which the symmetry acts
nrows	number of rows
ncols	number of columns
success	to store whether the component is successfully added

Definition at line 2232 of file symmetry_orbitopal.c.

References addOrbitope(), BnbNodeInfo::nrows, NULL, SCIP_CALL, SCIP_OKAY, SCIPfindConshdlr(), SCIPisTransformed(), and TRUE.

Referenced by addOrbitopesDynamic().

SCIPorbitopalReductionReset()

SCIP_RETCODE SCIPorbitopalReductionReset	(	SCIP *	scip,
		SCIP_ORBITOPALREDDATA *	orbireddata
	)

resets orbitopal reduction data structure (clears all orbitopes)

Parameters

scip	SCIP data structure
orbireddata	pointer to orbitopal reduction structure to populate

Definition at line 2267 of file symmetry_orbitopal.c.

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

Referenced by resetDynamicSymmetryHandling(), and SCIPorbitopalReductionFree().

SCIPorbitopalReductionFree()

SCIP_RETCODE SCIPorbitopalReductionFree	(	SCIP *	scip,
		SCIP_ORBITOPALREDDATA **	orbireddata
	)

frees orbitopal reduction data

Parameters

scip	SCIP data structure
orbireddata	pointer to orbitopal reduction structure to populate

Definition at line 2294 of file symmetry_orbitopal.c.

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

Referenced by SCIP_DECL_PROPFREE().

SCIPincludeOrbitopalReduction()

SCIP_RETCODE SCIPincludeOrbitopalReduction	(	SCIP *	scip,
		SCIP_ORBITOPALREDDATA **	orbireddata
	)

initializes structures needed for orbitopal reduction

This is only done exactly once.

Parameters

scip	SCIP data structure
orbireddata	pointer to orbitopal reduction structure to populate

Definition at line 2314 of file symmetry_orbitopal.c.

References DEFAULT_COLUMNORDERING, EVENTHDLR_DESC, EVENTHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPaddIntParam(), SCIPallocBlockMemory, SCIPcheckStage(), SCIPfindEventhdlr(), SCIPincludeEventhdlrBasic(), SYMHDLR_NAME, and TRUE.

Referenced by SCIPincludePropSymmetry().

SCIPorbitopalReductionGetDefaultColumnOrdering()

SCIP_COLUMNORDERING SCIPorbitopalReductionGetDefaultColumnOrdering

(

SCIP_ORBITOPALREDDATA *

orbireddata

)

returns the default column ordering

Parameters

orbireddata

pointer to orbitopal reduction structure to populate

Definition at line 2360 of file symmetry_orbitopal.c.

References NULL.

Referenced by addOrbitopesDynamic().