presolver for storing symmetry information about current problem
This presolver computes symmetries of the problem and stores this information in adequate form. It does not perform additional actions. The symmetry information can be accessed through external functions. However, the user has to declare the type of symmetry that is needed before execution, see SYMsetSpecRequirement().
Definition in file presol_symmetry.c.
#include <scip/cons_linear.h>
#include <scip/cons_knapsack.h>
#include <scip/cons_varbound.h>
#include <scip/cons_setppc.h>
#include <scip/cons_and.h>
#include <scip/cons_logicor.h>
#include <scip/cons_or.h>
#include <scip/cons_xor.h>
#include <scip/presol_symmetry.h>
#include <symmetry/compute_symmetry.h>
#include <string.h>
Go to the source code of this file.
Macros | |
#define | PRESOL_NAME "symmetry" |
#define | PRESOL_DESC "presolver for computing and storing symmetry information about current problem" |
#define | PRESOL_PRIORITY 0 |
#define | PRESOL_MAXROUNDS -1 |
#define | PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
#define | DEFAULT_MAXGENERATORS 1500 |
#define | DEFAULT_COMPUTEPRESOLVED TRUE |
#define | DEFAULT_CHECKSYMMETRIES FALSE |
#define | MAXGENNUMERATOR 64000000 |
Typedefs | |
typedef struct SYM_Sortrhstype | SYM_SORTRHSTYPE |
Functions | |
static | SCIP_DECL_HASHGETKEY (SYMhashGetKeyVartype) |
static | SCIP_DECL_HASHKEYEQ (SYMhashKeyEQVartype) |
static | SCIP_DECL_HASHKEYVAL (SYMhashKeyValVartype) |
static | SCIP_DECL_SORTINDCOMP (SYMsortRhsTypes) |
static | SCIP_DECL_SORTINDCOMP (SYMsortMatCoef) |
static SCIP_Bool | SymmetryFixVar (SYM_SPEC fixedtype, SCIP_VAR *var) |
static SCIP_RETCODE | getActiveVariables (SCIP *scip, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed) |
static SCIP_RETCODE | collectCoefficients (SCIP *scip, SCIP_VAR **linvars, SCIP_Real *linvals, int nlinvars, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool istransformed, SYM_RHSSENSE rhssense, SYM_MATRIXDATA *matrixdata) |
static SCIP_RETCODE | checkSymmetriesAreSymmetries (SCIP *scip, SYM_SPEC fixedtype, SYM_MATRIXDATA *matrixdata, int nperms, int **perms) |
static int | getNSymhandableConss (SCIP *scip) |
static SCIP_RETCODE | computeSymmetryGroup (SCIP *scip, int maxgenerators, SYM_SPEC fixedtype, SCIP_Bool local, SCIP_Bool checksymmetries, int *npermvars, SCIP_VAR ***permvars, SCIP_Real **permvarsobj, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Bool *success) |
static SCIP_RETCODE | determineSymmetry (SCIP *scip, SCIP_PRESOLDATA *presoldata) |
static | SCIP_DECL_PRESOLINIT (presolInitSymmetry) |
static | SCIP_DECL_PRESOLINITPRE (presolInitpreSymmetry) |
static | SCIP_DECL_PRESOLEXIT (presolExitSymmetry) |
static | SCIP_DECL_PRESOLFREE (presolFreeSymmetry) |
static | SCIP_DECL_PRESOLEXEC (presolExecSymmetry) |
static | SCIP_DECL_PRESOLEXITPRE (presolExitpreSymmetry) |
SCIP_RETCODE | SCIPincludePresolSymmetry (SCIP *scip) |
SCIP_RETCODE | SCIPgetGeneratorsSymmetry (SCIP *scip, int *npermvars, SCIP_VAR ***permvars, int *nperms, int ***perms, SCIP_Real *log10groupsize) |
SCIP_RETCODE | SCIPgetPermvarsObjSymmetry (SCIP *scip, SCIP_Real **permvarsobj) |
SCIP_RETCODE | SCIPregisterSymmetry (SCIP *scip, SYM_HANDLETYPE symtype, SYM_SPEC type, SYM_SPEC fixedtype) |
SCIP_RETCODE | SCIPgetTimingSymmetry (SCIP *scip, SCIP_Bool *afterpresolve) |
#define PRESOL_NAME "symmetry" |
Definition at line 51 of file presol_symmetry.c.
Referenced by SCIP_DECL_PRESOLEXEC(), SCIP_DECL_PRESOLEXIT(), SCIP_DECL_PRESOLEXITPRE(), SCIP_DECL_PRESOLFREE(), SCIP_DECL_PRESOLINIT(), SCIP_DECL_PRESOLINITPRE(), SCIPgetGeneratorsSymmetry(), SCIPgetPermvarsObjSymmetry(), SCIPgetTimingSymmetry(), SCIPincludePresolSymmetry(), and SCIPregisterSymmetry().
#define PRESOL_DESC "presolver for computing and storing symmetry information about current problem" |
Definition at line 52 of file presol_symmetry.c.
Referenced by SCIPincludePresolSymmetry().
#define PRESOL_PRIORITY 0 |
priority of the presolver (>= 0: before, < 0: after constraint handlers)
Definition at line 53 of file presol_symmetry.c.
Referenced by SCIPincludePresolSymmetry().
#define PRESOL_MAXROUNDS -1 |
maximal number of presolving rounds the presolver participates in (-1: no limit)
Definition at line 54 of file presol_symmetry.c.
Referenced by SCIPincludePresolSymmetry().
#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolver (fast, medium, or exhaustive) */ |
Definition at line 55 of file presol_symmetry.c.
Referenced by SCIPincludePresolSymmetry().
#define DEFAULT_MAXGENERATORS 1500 |
limit on the number of generators that should be produced within symmetry detection (0 = no limit)
Definition at line 58 of file presol_symmetry.c.
Referenced by SCIPincludePresolSymmetry().
#define DEFAULT_COMPUTEPRESOLVED TRUE |
Should the symmetry be computed after presolving (otherwise before presol)?
Definition at line 59 of file presol_symmetry.c.
Referenced by SCIPincludePresolSymmetry().
#define DEFAULT_CHECKSYMMETRIES FALSE |
Should all symmetries be checked after computation?
Definition at line 60 of file presol_symmetry.c.
Referenced by SCIPincludePresolSymmetry().
#define MAXGENNUMERATOR 64000000 |
determine maximal number of generators by dividing this number by the number of variables
Definition at line 63 of file presol_symmetry.c.
Referenced by determineSymmetry().
typedef struct SYM_Sortrhstype SYM_SORTRHSTYPE |
Definition at line 160 of file presol_symmetry.c.
|
static |
gets the key of the given element
Definition at line 100 of file presol_symmetry.c.
|
static |
returns TRUE iff both keys are equal
Compare the types of two variables according to objective, lower and upper bound, and variable type.
Definition at line 110 of file presol_symmetry.c.
References FALSE, SYM_Vartype::lb, SYM_Vartype::obj, SCIPisEQ(), TRUE, SYM_Vartype::type, and SYM_Vartype::ub.
|
static |
returns the hash value of the key
Definition at line 141 of file presol_symmetry.c.
References SYM_Vartype::lb, SYM_Vartype::obj, SCIPcombineTwoInt, SCIPhashTwo, SCIPrealHashCode(), and SYM_Vartype::ub.
|
static |
sort rhs types - first by sense, then by value
Due to numerical issues, we first sort by sense, then by value.
result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value
0: ind2 comes after (is worse than) ind2
Definition at line 172 of file presol_symmetry.c.
References SYM_Sortrhstype::nrhscoef, SCIP_Real, SYM_Sortrhstype::senses, and SYM_Sortrhstype::vals.
|
static |
sort matrix coefficients
result: < 0: ind1 comes before (is better than) ind2 = 0: both indices have the same value
0: ind2 comes after (is worse than) ind2
Definition at line 206 of file presol_symmetry.c.
References SCIP_Real, and SYM_Sortrhstype::vals.
determines whether variable should be fixed by permutations
fixedtype | bitset of variable types that should be fixed |
var | variable to be considered |
Definition at line 229 of file presol_symmetry.c.
References FALSE, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPvarGetType(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, and TRUE.
Referenced by checkSymmetriesAreSymmetries(), and computeSymmetryGroup().
|
static |
Transforms given variables, scalars, and constant to the corresponding active variables, scalars, and constant.
constant
needs to be initialized! scip | SCIP data structure |
vars | pointer to vars array to get active variables for |
scalars | pointer to scalars a_1, ..., a_n in linear sum a_1*x_1 + ... + a_n*x_n + c |
nvars | pointer to number of variables and values in vars and vals array |
constant | pointer to constant c in linear sum a_1*x_1 + ... + a_n*x_n + c |
transformed | transformed constraint? |
Definition at line 250 of file presol_symmetry.c.
References SCIP_CALL, SCIP_OKAY, SCIPgetProbvarLinearSum(), SCIPreallocBufferArray, SCIPvarGetOrigvarSum(), and TRUE.
Referenced by collectCoefficients().
|
static |
fill in matrix elements into coefficient arrays
scip | SCIP data structure |
linvars | array of linear variables |
linvals | array of linear coefficients values (or NULL if all linear coefficient values are 1) |
nlinvars | number of linear variables |
lhs | left hand side |
rhs | right hand side |
istransformed | whether the constraint is transformed |
rhssense | identifier of constraint type |
matrixdata | matrix data to be filled in |
Definition at line 296 of file presol_symmetry.c.
References getActiveVariables(), SYM_Matrixdata::matcoef, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::nmaxmatcoef, SYM_Matrixdata::nrhscoef, SYM_Sortrhstype::nrhscoef, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhsidx, SYM_Matrixdata::rhssense, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcalcMemGrowSize(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPgetNVars(), SCIPisEQ(), SCIPisInfinity(), SCIPreallocBlockMemoryArray, SCIPvarGetProbindex(), SYM_SENSE_EQUATION, SYM_SENSE_INEQUALITY, and SYM_Sortrhstype::vals.
Referenced by computeSymmetryGroup().
|
static |
checks whether given permutations form a symmetry of a MIP
We need the matrix and rhs in the original order in order to speed up the comparison process. The matrix is needed in the right order to easily check rows. The rhs is used because of cache effects.
scip | SCIP data structure |
fixedtype | variable types that must be fixed by symmetries |
matrixdata | matrix data |
nperms | number of permutations |
perms | permutations |
Definition at line 465 of file presol_symmetry.c.
References FALSE, SYM_Matrixdata::matcoef, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, SYM_Sortrhstype::nrhscoef, SYM_Matrixdata::permvars, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhssense, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPisEQ(), SCIPisZero(), SymmetryFixVar(), and TRUE.
Referenced by computeSymmetryGroup().
|
static |
returns the number of active constraints that can be handled by symmetry
scip | SCIP instance |
Definition at line 611 of file presol_symmetry.c.
References SCIPconshdlrGetNActiveConss(), and SCIPfindConshdlr().
Referenced by computeSymmetryGroup(), and determineSymmetry().
|
static |
compute symmetry group of MIP
scip | SCIP pointer |
maxgenerators | maximal number of generators constructed (= 0 if unlimited) |
fixedtype | variable types that must be fixed by symmetries |
local | Use local variable bounds? |
checksymmetries | Should all symmetries be checked after computation? |
npermvars | pointer to store number of variables for permutations |
permvars | pointer to store variables on which permutations act |
permvarsobj | objective values of permuted variables |
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 log10 of size of group |
success | pointer to store whether symmetry computation was successful |
Definition at line 645 of file presol_symmetry.c.
References checkSymmetriesAreSymmetries(), collectCoefficients(), SYM_Vartype::color, FALSE, getNSymhandableConss(), SYM_Vartype::lb, SYM_Matrixdata::matcoef, SYM_Matrixdata::matcoefcolors, SYM_Matrixdata::matidx, SYM_Matrixdata::matrhsidx, SYM_Matrixdata::matvaridx, SYM_Matrixdata::nmatcoef, SYM_Matrixdata::nmaxmatcoef, SYM_Matrixdata::npermvars, SYM_Matrixdata::nrhscoef, SYM_Sortrhstype::nrhscoef, SYM_Matrixdata::nuniquemat, SYM_Matrixdata::nuniquerhs, SYM_Matrixdata::nuniquevars, SYM_Vartype::obj, SYM_Matrixdata::permvarcolors, SYM_Matrixdata::permvars, SYM_Matrixdata::rhscoef, SYM_Matrixdata::rhscoefcolors, SYM_Matrixdata::rhsidx, SYM_Matrixdata::rhssense, SCIP_CALL, SCIP_ERROR, SCIP_INVALID, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_SETPPCTYPE_COVERING, SCIP_SETPPCTYPE_PACKING, SCIP_SETPPCTYPE_PARTITIONING, SCIPallocBlockMemoryArray, SCIPblkmem(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsActive(), SCIPconsIsTransformed(), SCIPdebugMsg, SCIPduplicateBlockMemoryArray, SCIPerrorMessage, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPgetCapacityKnapsack(), SCIPgetConss(), SCIPgetIntVarXor(), SCIPgetLhsLinear(), SCIPgetLhsVarbound(), SCIPgetNActiveConss(), SCIPgetNConss(), SCIPgetNFixedVars(), SCIPgetNVars(), SCIPgetNVarsAnd(), SCIPgetNVarsKnapsack(), SCIPgetNVarsLinear(), SCIPgetNVarsLogicor(), SCIPgetNVarsOr(), SCIPgetNVarsSetppc(), SCIPgetNVarsXor(), SCIPgetResultantAnd(), SCIPgetResultantOr(), SCIPgetRhsLinear(), SCIPgetRhsVarbound(), SCIPgetRhsXor(), SCIPgetTypeSetppc(), SCIPgetValsLinear(), SCIPgetVars(), SCIPgetVarsAnd(), SCIPgetVarsKnapsack(), SCIPgetVarsLinear(), SCIPgetVarsLogicor(), SCIPgetVarsOr(), SCIPgetVarsSetppc(), SCIPgetVarsXor(), SCIPgetVarVarbound(), SCIPgetVbdcoefVarbound(), SCIPgetVbdvarVarbound(), SCIPgetWeightsKnapsack(), SCIPhashtableCreate(), SCIPhashtableExists(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPinfinity(), SCIPisEQ(), SCIPisStopped(), SCIPmarkDoNotMultaggrVar(), SCIPsort(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SYM_Sortrhstype::senses, SYM_SENSE_AND, SYM_SENSE_EQUATION, SYM_SENSE_INEQUALITY, SYM_SENSE_OR, SYM_SENSE_UNKOWN, SYM_SENSE_XOR, SYMcanComputeSymmetry(), SYMcomputeSymmetryGenerators(), SymmetryFixVar(), TRUE, SYM_Vartype::type, SYM_Vartype::ub, and SYM_Sortrhstype::vals.
Referenced by determineSymmetry().
|
static |
determine symmetry
scip | SCIP instance |
presoldata | presolver data |
Definition at line 1154 of file presol_symmetry.c.
References computeSymmetryGroup(), FALSE, getNSymhandableConss(), MAXGENNUMERATOR, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPgetIntParam(), SCIPgetNActiveConss(), SCIPgetNActivePricers(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetSolvingTime(), SCIPsetIntParam(), SCIPverbMessage(), SCIPwarningMessage(), SYM_SPEC_BINARY, SYM_SPEC_INTEGER, SYM_SPEC_REAL, SYMcanComputeSymmetry(), and TRUE.
Referenced by SCIP_DECL_PRESOLEXITPRE(), SCIP_DECL_PRESOLINITPRE(), and SCIPgetGeneratorsSymmetry().
|
static |
initialization method of presolver (called after problem was transformed)
Definition at line 1313 of file presol_symmetry.c.
References PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPgetIntParam(), SCIPpresolGetData(), and SCIPpresolGetName().
|
static |
presolving initialization method of presolver (called when presolving is about to begin)
Definition at line 1335 of file presol_symmetry.c.
References determineSymmetry(), PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPpresolGetData(), and SCIPpresolGetName().
|
static |
deinitialization method of presolver (called before transformed problem is freed)
Definition at line 1361 of file presol_symmetry.c.
References FALSE, PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPpresolGetData(), SCIPpresolGetName(), and SCIPsetIntParam().
|
static |
destructor of presolver to free user data (called when SCIP is exiting)
Definition at line 1410 of file presol_symmetry.c.
References PRESOL_NAME, SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPpresolGetData(), and SCIPpresolGetName().
|
static |
execution method of presolver
Definition at line 1431 of file presol_symmetry.c.
References PRESOL_NAME, SCIP_DIDNOTRUN, SCIP_OKAY, and SCIPpresolGetName().
|
static |
presolving deinitialization method of presolver (called after presolving has been finished)
Definition at line 1447 of file presol_symmetry.c.
References determineSymmetry(), PRESOL_NAME, SCIP_CALL, SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPdebugMsg, SCIPgetNRuns(), SCIPgetStatus(), SCIPisStopped(), SCIPpresolGetData(), and SCIPpresolGetName().
SCIP_RETCODE SCIPincludePresolSymmetry | ( | SCIP * | scip | ) |
include symmetry constraint handler
scip | SCIP data structure |
Definition at line 1488 of file presol_symmetry.c.
References DEFAULT_CHECKSYMMETRIES, DEFAULT_COMPUTEPRESOLVED, DEFAULT_MAXGENERATORS, FALSE, PRESOL_DESC, PRESOL_MAXROUNDS, PRESOL_NAME, PRESOL_PRIORITY, PRESOL_TIMING, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPallocBlockMemory, SCIPincludeExternalCodeInformation(), SCIPincludePresolBasic(), SCIPsetPresolExit(), SCIPsetPresolExitpre(), SCIPsetPresolFree(), SCIPsetPresolInit(), SCIPsetPresolInitpre(), SYMcanComputeSymmetry(), SYMsymmetryGetDesc(), SYMsymmetryGetName(), and TRUE.
Referenced by SCIPincludeDefaultPlugins().
SCIP_RETCODE SCIPgetGeneratorsSymmetry | ( | SCIP * | scip, |
int * | npermvars, | ||
SCIP_VAR *** | permvars, | ||
int * | nperms, | ||
int *** | perms, | ||
SCIP_Real * | log10groupsize | ||
) |
return symmetry group generators
scip | SCIP data structure |
npermvars | pointer to store number of variables for permutations |
permvars | pointer to store variables on which permutations act |
nperms | pointer to store number of permutations |
perms | pointer to store permutation generators as (nperms x npermvars) matrix |
log10groupsize | pointer to store log10 of group size (or NULL) |
Definition at line 1549 of file presol_symmetry.c.
References determineSymmetry(), PRESOL_NAME, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_STAGE_INITSOLVE, SCIP_STAGE_PRESOLVED, SCIP_STAGE_PRESOLVING, SCIPerrorMessage, SCIPfindPresol(), SCIPgetStage(), SCIPpresolGetData(), and SCIPpresolGetName().
Referenced by SCIP_DECL_PRESOLEXEC(), and SCIP_DECL_PROPINITSOL().
SCIP_RETCODE SCIPgetPermvarsObjSymmetry | ( | SCIP * | scip, |
SCIP_Real ** | permvarsobj | ||
) |
return objective coefficients of permuted variables at time of symmetry computation
scip | SCIP data structure |
permvarsobj | pointer to store objective coefficients of permuted variables (NULL if not available) |
Definition at line 1605 of file presol_symmetry.c.
References PRESOL_NAME, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPerrorMessage, SCIPfindPresol(), SCIPpresolGetData(), and SCIPpresolGetName().
Referenced by propagateOrbitalFixing().
SCIP_RETCODE SCIPregisterSymmetry | ( | SCIP * | scip, |
SYM_HANDLETYPE | symtype, | ||
SYM_SPEC | type, | ||
SYM_SPEC | fixedtype | ||
) |
register that a specific symmetry is needed
scip | SCIP data structure |
symtype | type of symmetry handling of callee |
type | variable types the callee is interested in |
fixedtype | variable types that callee wants to have fixed |
Definition at line 1636 of file presol_symmetry.c.
References PRESOL_NAME, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPerrorMessage, SCIPfindPresol(), SCIPpresolGetData(), and SCIPpresolGetName().
Referenced by SCIP_DECL_PRESOLINIT(), SCIP_DECL_PRESOLINITPRE(), and SCIP_DECL_PROPINIT().
SCIP_RETCODE SCIPgetTimingSymmetry | ( | SCIP * | scip, |
SCIP_Bool * | afterpresolve | ||
) |
return at what time symmetry is computed (before or after presolving)
scip | SCIP data structure |
afterpresolve | pointer to store whether symmetry is computed in stage initpre or exitpre |
Definition at line 1677 of file presol_symmetry.c.
References PRESOL_NAME, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPerrorMessage, SCIPfindPresol(), SCIPpresolGetData(), and SCIPpresolGetName().
Referenced by SCIP_DECL_PRESOLINITPRE().