Detailed Description

interface for symmetry computations to bliss

Author: Marc Pfetsch; Thomas Rehn; Fabian Wegscheider

Definition in file compute_symmetry_bliss.cpp.

#include "compute_symmetry.h"
#include <bliss/defs.hh>
#include <bliss/graph.hh>
#include <string.h>
#include <vector>
#include <list>
#include <math.h>
#include "scip/expr_var.h"
#include "scip/expr_sum.h"
#include "scip/expr_pow.h"
#include "scip/expr.h"
#include "scip/cons_nonlinear.h"
#include "scip/cons_linear.h"

Go to the source code of this file.

Data Structures
struct	BLISS_Data

Functions
static	SCIP_DECL_HASHGETKEY (SYMhashGetKeyOptype)

static	SCIP_DECL_HASHKEYEQ (SYMhashKeyEQOptype)

static	SCIP_DECL_HASHKEYVAL (SYMhashKeyValOptype)

static	SCIP_DECL_HASHGETKEY (SYMhashGetKeyConsttype)

static	SCIP_DECL_HASHKEYEQ (SYMhashKeyEQConsttype)

static	SCIP_DECL_HASHKEYVAL (SYMhashKeyValConsttype)

static	SCIP_DECL_HASHGETKEY (SYMhashGetKeyRhstype)

static	SCIP_DECL_HASHKEYEQ (SYMhashKeyEQRhstype)

static	SCIP_DECL_HASHKEYVAL (SYMhashKeyValRhstype)

static void	blisshook (void user_param, unsigned int n, const unsigned int aut)

static SCIP_RETCODE	createVariableNodes (SCIP scip, bliss::Graph G, SYM_MATRIXDATA *matrixdata, int &nnodes, const int &nedges, int &nusedcolors)

static SCIP_RETCODE	fillGraphByLinearConss (SCIP scip, bliss::Graph G, SYM_MATRIXDATA *matrixdata, int &nnodes, int &nedges, int &nusedcolors, SCIP_Bool &success)

static SCIP_RETCODE	fillGraphByNonlinearConss (SCIP scip, bliss::Graph G, SYM_EXPRDATA *exprdata, int &nnodes, int &nedges, int &nusedcolors, SCIP_Bool &success)

SCIP_Bool	SYMcanComputeSymmetry (void)

const char *	SYMsymmetryGetName (void)

const char *	SYMsymmetryGetDesc (void)

SCIP_RETCODE	SYMcomputeSymmetryGenerators (SCIP scip, int maxgenerators, SYM_MATRIXDATA matrixdata, SYM_EXPRDATA exprdata, int nperms, int nmaxperms, int *perms, SCIP_Real log10groupsize)

Variables
static char	blissname [100]

Function Documentation

◆ SCIP_DECL_HASHGETKEY() [1/3]

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyOptype )

static

gets the key of the given element

Definition at line 60 of file compute_symmetry_bliss.cpp.

◆ SCIP_DECL_HASHKEYEQ() [1/3]

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQOptype )

static

returns TRUE iff both keys are equal

Compare the types of two operators according to their name, level and, in case of power, exponent.

Definition at line 70 of file compute_symmetry_bliss.cpp.

References SYM_Optype::expr, FALSE, SYM_Optype::level, SCIPexprGetHdlr(), SCIPgetExponentExprPow(), SCIPisExprPower(), and TRUE.

◆ SCIP_DECL_HASHKEYVAL() [1/3]

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValOptype )

static

returns the hash value of the key

Definition at line 96 of file compute_symmetry_bliss.cpp.

References SYM_Optype::expr, SYM_Optype::level, SCIP_Real, SCIPexprGetHdlr(), SCIPexprhdlrGetName(), SCIPgetExponentExprPow(), SCIPhashTwo, SCIPisExprPower(), and SCIPrealHashCode().

◆ SCIP_DECL_HASHGETKEY() [2/3]

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyConsttype )

static

gets the key of the given element

Definition at line 116 of file compute_symmetry_bliss.cpp.

◆ SCIP_DECL_HASHKEYEQ() [2/3]

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQConsttype )

static

returns TRUE iff both keys are equal

Compare two constants according to their values.

Definition at line 126 of file compute_symmetry_bliss.cpp.

References SCIP_Bool, and SYM_Consttype::value.

◆ SCIP_DECL_HASHKEYVAL() [2/3]

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValConsttype )

static

returns the hash value of the key

Definition at line 139 of file compute_symmetry_bliss.cpp.

References SCIPrealHashCode(), and SYM_Consttype::value.

◆ SCIP_DECL_HASHGETKEY() [3/3]

static SCIP_DECL_HASHGETKEY ( SYMhashGetKeyRhstype )

static

gets the key of the given element

Definition at line 152 of file compute_symmetry_bliss.cpp.

◆ SCIP_DECL_HASHKEYEQ() [3/3]

static SCIP_DECL_HASHKEYEQ ( SYMhashKeyEQRhstype )

static

returns TRUE iff both keys are equal

Compare two constraint sides according to lhs and rhs.

Definition at line 162 of file compute_symmetry_bliss.cpp.

References FALSE, SYM_Rhstype::lhs, SYM_Rhstype::rhs, and SCIP_Bool.

◆ SCIP_DECL_HASHKEYVAL() [3/3]

static SCIP_DECL_HASHKEYVAL ( SYMhashKeyValRhstype )

static

returns the hash value of the key

Definition at line 178 of file compute_symmetry_bliss.cpp.

References SYM_Rhstype::lhs, SYM_Rhstype::rhs, SCIPhashTwo, and SCIPrealHashCode().

◆ blisshook()

static void blisshook	(	void *	user_param,
		unsigned int	n,
		const unsigned int *	aut
	)

static

callback function for bliss

Parameters

user_param	parameter supplied at call to bliss
n	size of aut vector
aut	automorphism

Definition at line 189 of file compute_symmetry_bliss.cpp.

References BLISS_Data::maxgenerators, BLISS_Data::nmaxperms, BLISS_Data::nperms, BLISS_Data::npermvars, NULL, BLISS_Data::perms, BLISS_Data::scip, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPcalcMemGrowSize(), SCIPfreeBlockMemoryArray, and SCIPreallocBlockMemoryArray.

Referenced by SYMcomputeSymmetryGenerators().

◆ createVariableNodes()

static SCIP_RETCODE createVariableNodes	(	SCIP *	scip,
		bliss::Graph *	G,
		SYM_MATRIXDATA *	matrixdata,
		int &	nnodes,
		const int &	nedges,
		int &	nusedcolors
	)

static

Creates the nodes in the graph that correspond to variables. Each variable type gets a unique color

Precondition: graph should be empty when this is called

Parameters

scip	SCIP instance
G	Graph to be constructed
matrixdata	data for MIP matrix (also contains the relevant variables)
nnodes	buffer to store number of nodes in graph
nedges	buffer to store number of edges in graph
nusedcolors	buffer to store number of used colors

Definition at line 259 of file compute_symmetry_bliss.cpp.

References nnodes, SYM_Matrixdata::npermvars, NULL, SYM_Matrixdata::nuniquevars, SYM_Matrixdata::permvarcolors, SCIP_OKAY, and SCIPdebugMsg.

Referenced by SYMcomputeSymmetryGenerators().

◆ fillGraphByLinearConss()

static SCIP_RETCODE fillGraphByLinearConss	(	SCIP *	scip,
		bliss::Graph *	G,
		SYM_MATRIXDATA *	matrixdata,
		int &	nnodes,
		int &	nedges,
		int &	nusedcolors,
		SCIP_Bool &	success
	)

static

Construct linear part of colored graph for symmetry computations

Construct graph:

Each variable gets a different node.
Each constraint gets a different node.
Each matrix coefficient gets a different node that is connected to the two nodes corresponding to the respective constraint and variable.

Each different variable, rhs, matrix coefficient gets a different color that is attached to the corresponding entries.

Precondition: This method assumes that the nodes corresponding to permutation variables are already in the graph and that their node number is equal to their index.

Parameters

scip	SCIP instance
G	Graph to be constructed
matrixdata	data for MIP matrix
nnodes	buffer to store number of nodes in graph
nedges	buffer to store number of edges in graph
nusedcolors	buffer to store number of used colors
success	whether the construction was successful

Definition at line 311 of file compute_symmetry_bliss.cpp.

References FALSE, SYM_Matrixdata::matcoef, SYM_Matrixdata::matcoefcolors, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, nnodes, BLISS_Data::npermvars, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, NULL, SYM_Matrixdata::nuniquemat, SYM_Matrixdata::nuniquerhs, SYM_Matrixdata::nuniquevars, SYM_Matrixdata::rhscoefcolors, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisEQ(), and TRUE.

Referenced by SYMcomputeSymmetryGenerators().

◆ fillGraphByNonlinearConss()

static SCIP_RETCODE fillGraphByNonlinearConss	(	SCIP *	scip,
		bliss::Graph *	G,
		SYM_EXPRDATA *	exprdata,
		int &	nnodes,
		int &	nedges,
		int &	nusedcolors,
		SCIP_Bool &	success
	)

static

Construct non-linear part of colored graph for symmetry computations

Construct graph:

Each node of the expression trees gets a different node.
Each coefficient of a sum expression gets its own node connected to the node of the corresponding child.
Each constraint (with lhs and (!) rhs) gets its own node connected to the corresponding node of the root expression.

Note: : In contrast to the linear part, lhs and rhs are treated together here, so that each unique combination of lhs and rhs gets its own node. This makes the implementation a lot simpler with the small downside, that different formulations of the same constraints would not be detected as equivalent, e.g. for 0 <= x1 + x2 <= 1 0 <= x3 + x4 x3 + x4 <= 1 there would be no symmetry between (x1,x2) and (x3,x4) detected.

Each different constraint (sides), sum-expression coefficient, constant and operator type gets a different color that is attached to the corresponding entries.

Precondition: This method assumes that the nodes corresponding to permutation variables are already in the graph and that their node number is equal to their index.

Parameters

scip	SCIP instance
G	Graph to be constructed
exprdata	data for nonlinear constraints
nnodes	buffer to store number of nodes in graph
nedges	buffer to store number of edges in graph
nusedcolors	number of used colors ind the graph so far
success	whether the construction was successful

Definition at line 473 of file compute_symmetry_bliss.cpp.

References SYM_Optype::expr, FALSE, SYM_Optype::level, SYM_Rhstype::lhs, nnodes, NULL, SYM_Exprdata::nuniquecoefs, SYM_Exprdata::nuniqueconstants, SYM_Exprdata::nuniqueoperators, SYM_Rhstype::rhs, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_EXPRITER_LEAVEEXPR, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPblkmem(), SCIPcalcMemGrowSize(), SCIPconshdlrGetConss(), SCIPconshdlrGetNConss(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPexprGetNChildren(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterGetParentDFS(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfindConshdlr(), SCIPfreeBlockMemoryArrayNull, SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetExprNonlinear(), SCIPgetLhsNonlinear(), SCIPgetProbvarLinearSum(), SCIPgetRhsNonlinear(), SCIPgetValueExprValue(), SCIPgetVarExprVar(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPisExprSum(), SCIPisExprValue(), SCIPisExprVar(), SCIPreallocBlockMemoryArray, SCIPreallocBufferArray, SCIPvarGetProbindex(), SCIPvarIsActive(), TRUE, and SYM_Consttype::value.

Referenced by SYMcomputeSymmetryGenerators().

◆ SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry ( void )

return whether symmetry can be computed

Definition at line 949 of file compute_symmetry_bliss.cpp.

References TRUE.

◆ SYMsymmetryGetName()

const char* SYMsymmetryGetName ( void )

return name of external program used to compute generators

Definition at line 958 of file compute_symmetry_bliss.cpp.

References blissname.

◆ SYMsymmetryGetDesc()

const char* SYMsymmetryGetDesc ( void )

return description of external program used to compute generators

Definition at line 969 of file compute_symmetry_bliss.cpp.

◆ SYMcomputeSymmetryGenerators()

SCIP_RETCODE SYMcomputeSymmetryGenerators	(	SCIP *	scip,
		int	maxgenerators,
		SYM_MATRIXDATA *	matrixdata,
		SYM_EXPRDATA *	exprdata,
		int *	nperms,
		int *	nmaxperms,
		int ***	perms,
		SCIP_Real *	log10groupsize
	)

compute generators of symmetry group

Parameters

scip	SCIP pointer
maxgenerators	maximal number of generators constructed (= 0 if unlimited)
matrixdata	data for MIP matrix
exprdata	data for nonlinear constraints
nperms	pointer to store number of permutations
nmaxperms	pointer to store maximal number of permutations (needed for freeing storage)
perms	pointer to store permutation generators as (nperms x npermvars) matrix
log10groupsize	pointer to store size of group

Definition at line 975 of file compute_symmetry_bliss.cpp.

References blisshook(), createVariableNodes(), FALSE, fillGraphByLinearConss(), fillGraphByNonlinearConss(), BLISS_Data::maxgenerators, BLISS_Data::nmaxperms, nnodes, BLISS_Data::nperms, BLISS_Data::npermvars, SYM_Matrixdata::npermvars, NULL, SYM_Matrixdata::nuniquevars, BLISS_Data::perms, BLISS_Data::scip, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VERBLEVEL_MINIMAL, SCIPdebugMsg, and SCIPverbMessage().

Variable Documentation

◆ blissname

char blissname[100]

static

static variable for holding the name of bliss

Definition at line 955 of file compute_symmetry_bliss.cpp.

Referenced by SYMsymmetryGetName().

SCIP

Detailed Description

Data Structures

Functions

Variables

Function Documentation

◆ SCIP_DECL_HASHGETKEY() [1/3]

◆ SCIP_DECL_HASHKEYEQ() [1/3]

◆ SCIP_DECL_HASHKEYVAL() [1/3]

◆ SCIP_DECL_HASHGETKEY() [2/3]

◆ SCIP_DECL_HASHKEYEQ() [2/3]

◆ SCIP_DECL_HASHKEYVAL() [2/3]

◆ SCIP_DECL_HASHGETKEY() [3/3]

◆ SCIP_DECL_HASHKEYEQ() [3/3]

◆ SCIP_DECL_HASHKEYVAL() [3/3]

◆ blisshook()

◆ createVariableNodes()

◆ fillGraphByLinearConss()

◆ fillGraphByNonlinearConss()

◆ SYMcanComputeSymmetry()

◆ SYMsymmetryGetName()

◆ SYMsymmetryGetDesc()

◆ SYMcomputeSymmetryGenerators()

Variable Documentation

◆ blissname