Solving Constraint Integer Programs

compute_symmetry_bliss.cpp File Reference

Detailed Description

interface for symmetry computations to bliss

Marc Pfetsch
Thomas Rehn

Definition in file compute_symmetry_bliss.cpp.

#include "compute_symmetry.h"
#include <bliss/defs.hh>
#include <bliss/graph.hh>
#include <vector>
#include <list>
#include <math.h>

Go to the source code of this file.

Data Structures

struct  BLISS_Data


static void blisshook (void *user_param, unsigned int n, const unsigned int *aut)
static SCIP_RETCODE fillGraphByColoredCoefficients (SCIP *scip, bliss::Graph *G, SYM_MATRIXDATA *matrixdata, int &nnodes, int &nedges, 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, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize)


static char blissname [100]

Function Documentation

◆ blisshook()

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

callback function for bliss

user_paramparameter supplied at call to bliss
nsize of aut vector

Definition at line 48 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().

◆ fillGraphByColoredCoefficients()

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

Construct colored graph for symmetry computations

Construct bipartite graph:

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

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

scipSCIP instance
GGraph to be constructed
matrixdatadata for MIP matrix
nnodesnumber of nodes in graph
nedgesnumber of edges in graph
successwhether the construction was successful

Definition at line 126 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::permvarcolors, SYM_Matrixdata::rhscoefcolors, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisEQ(), and TRUE.

Referenced by SYMcomputeSymmetryGenerators().

◆ SYMcanComputeSymmetry()

SCIP_Bool SYMcanComputeSymmetry ( void  )

return whether symmetry can be computed

Definition at line 284 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 293 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 304 of file compute_symmetry_bliss.cpp.

◆ SYMcomputeSymmetryGenerators()

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

compute generators of symmetry group

scipSCIP pointer
maxgeneratorsmaximal number of generators constructed (= 0 if unlimited)
matrixdatadata for MIP matrix
npermspointer to store number of permutations
nmaxpermspointer to store maximal number of permutations (needed for freeing storage)
permspointer to store permutation generators as (nperms x npermvars) matrix
log10groupsizepointer to store size of group

Definition at line 310 of file compute_symmetry_bliss.cpp.

References blisshook(), FALSE, fillGraphByColoredCoefficients(), BLISS_Data::maxgenerators, BLISS_Data::nmaxperms, nnodes, BLISS_Data::nperms, BLISS_Data::npermvars, SYM_Matrixdata::npermvars, NULL, 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 variable for holding the name of bliss

Definition at line 290 of file compute_symmetry_bliss.cpp.

Referenced by SYMsymmetryGetName().