Scippy

SCIP

Solving Constraint Integer Programs

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 <string.h>
#include <symmetry/type_symmetry.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
scipSCIP data structure
orbireddatapointer to the dynamic orbitopal reduction data
vartypevar 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
scipSCIP data structure
orbidataorbitope information
col1first column to compare
col2second 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
scipSCIP data structure
orbidataorbitope data
colorderarray to populate with column order, of size colorder
colorderinvinverse array of the column order, of size colorder
varvariable that we branch on
thiscolswapthe 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
arrarray
idxindex

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
scipSCIP data structure
orbidataorbitope data
roworderroworder 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
scipSCIP data structure
orbidataorbitope data
nodenode for which the row order should be detected
roworderarray to populate with row order
nselrowspointer 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
orbidataorbitope data
nodenode considered
rootedpatharray to populate with the rooted path, must be sufficiently long
colorderarray to populate with the column order, must be nvars long
colorderinvarray 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]

◆ 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
scipSCIP data structure
orbireddatapointer to the dynamic orbitopal reduction data
orbidatasymmetry handling data for orbitopal structure
rowidrow 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

◆ 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
scipSCIP data structure
orbireddatapointer to the dynamic orbitopal reduction data
roworderingspecifies how rows of orbitope are ordered
colorderingspecifies how columnss of orbitope are ordered
varsvariables array, must have size nrows * ncols
nrowsnumber of rows in orbitope
ncolsnumber of columns in orbitope
successto 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
scipSCIP data structure
orbidataorbitope data
colordercolorder array that is initialized with the colorder in the dynamic case, of size ncols, and NULL in the static case
colorderinvarray 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
scipSCIP data structure
orbidataorbitope data
eventnodenode where this should be determined at
colorderarray to populate with column order, of size ncols
colorderinvarray 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
scipSCIP data structure
orbidataorbitope data
roworderarray with the row order
colorderarray with the column order
matrixa matrix
nrowsnumber of rows of matrix
ncolsnumber of cols of matrix
infinitesimalarray specifying where the infinitesimals are at
addinfinitesimalswhether 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
arrayarray
lenarray 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
scipSCIP data structure
orbidataorbitope data
roworderarray with the row order (or NULL if identity function is used)
nselrowsnumber of selected rows
colorderarray with the column order (or NULL if identity function is used)
infeasiblepointer to store whether the problem is infeasible
nfixedvarspointer 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
scipSCIP data structure
orbidataorbitope data
infeasiblepointer to store whether the problem is infeasible
nfixedvarspointer 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
scipSCIP data structure
orbireddataorbitopal reduction data structure
nredtotal number of reductions applied
ncutofftotal 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
scipSCIP data structure
orbireddataorbitopal 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
scipSCIP data structure
orbireddataorbitopal reduction data structure
infeasiblepointer to store whether infeasibility is found
nredpointer to store the number of domain reductions
didruna 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
scipSCIP data structure
orbireddataorbitopal reduction data structure
roworderingspecifies how rows of orbitope are ordered
colorderingspecifies how columnss of orbitope are ordered
varsmatrix of variables on which the symmetry acts
nrowsnumber of rows
ncolsnumber of columns
successto 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
scipSCIP data structure
orbireddatapointer 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
scipSCIP data structure
orbireddatapointer 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
scipSCIP data structure
orbireddatapointer 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
orbireddatapointer to orbitopal reduction structure to populate

Definition at line 2360 of file symmetry_orbitopal.c.

References NULL.

Referenced by addOrbitopesDynamic().