propagator for orbital fixing
This propagator implements orbital fixing as introduced by
F. Margot: Exploiting orbits in symmetric ILP. Math. Program., 98(1-3):3–21, 2003.
The method obtains symmetries from the symmetry presolver and then computes orbits of variables with respect to the subgroup of the symmetry group that stabilizes the variables branched to 1. Then one can fix all variables in an orbit to 0 or 1 if one of the other variables in the orbit is fixed to 0 or 1, respectively. Different from Margot, the subgroup is obtained by filtering out generators that do not individually stabilize the variables branched to 1.
Definition in file prop_orbitalfixing.c.
#include "prop_orbitalfixing.h"
#include <scip/pub_tree.h>
#include <scip/pub_table.h>
#include "presol_symmetry.h"
#include "presol_symbreak.h"
Go to the source code of this file.
Macros | |
#define | PROP_NAME "orbitalfixing" |
#define | PROP_DESC "propagator for orbital fixing" |
#define | PROP_TIMING SCIP_PROPTIMING_BEFORELP |
#define | PROP_PRIORITY -1000000 |
#define | PROP_FREQ 1 |
#define | PROP_DELAY FALSE |
#define | TABLE_NAME_ORBITALFIXING "orbitalfixing" |
#define | TABLE_DESC_ORBITALFIXING "orbital fixing statistics" |
#define | TABLE_POSITION_ORBITALFIXING 7001 |
#define | TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING |
Functions | |
static | SCIP_DECL_TABLEOUTPUT (tableOutputOrbitalfixing) |
static | SCIP_DECL_TABLEFREE (tableFreeOrbitalfixing) |
static SCIP_RETCODE | performOrbitalFixing (SCIP *scip, SCIP_VAR **permvars, int npermvars, int *orbits, int *orbitbegins, int norbits, SCIP_Bool *infeasible, int *nfixedzero, int *nfixedone) |
static SCIP_RETCODE | computeBranchingVariables (SCIP *scip, int nvars, SCIP_HASHMAP *varmap, SCIP_Shortbool *b1, SCIP_Bool *success) |
static SCIP_RETCODE | propagateOrbitalFixing (SCIP *scip, SCIP_PROPDATA *propdata, SCIP_Bool *infeasible, int *nprop) |
static | SCIP_DECL_PROPFREE (propFreeOrbitalfixing) |
static | SCIP_DECL_PROPINIT (propInitOrbitalfixing) |
static | SCIP_DECL_PROPEXIT (propExitOrbitalfixing) |
static | SCIP_DECL_PROPINITSOL (propInitsolOrbitalfixing) |
static | SCIP_DECL_PROPEXEC (propExecOrbitalfixing) |
static | SCIP_DECL_PROPRESPROP (propRespropOrbitalfixing) |
SCIP_RETCODE | SCIPincludePropOrbitalfixing (SCIP *scip) |
#define PROP_NAME "orbitalfixing" |
Definition at line 44 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
#define PROP_DESC "propagator for orbital fixing" |
Definition at line 45 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
#define PROP_TIMING SCIP_PROPTIMING_BEFORELP |
propagation timing mask
Definition at line 46 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
#define PROP_PRIORITY -1000000 |
propagator priority
Definition at line 47 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
#define PROP_FREQ 1 |
propagator frequency
Definition at line 48 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
#define PROP_DELAY FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 49 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
#define TABLE_NAME_ORBITALFIXING "orbitalfixing" |
Definition at line 52 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
#define TABLE_DESC_ORBITALFIXING "orbital fixing statistics" |
Definition at line 53 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
#define TABLE_POSITION_ORBITALFIXING 7001 |
the position of the statistics table
Definition at line 54 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
#define TABLE_EARLIEST_ORBITALFIXING SCIP_STAGE_SOLVING |
output of the statistics table is only printed from this stage onwards
Definition at line 55 of file prop_orbitalfixing.c.
Referenced by SCIPincludePropOrbitalfixing().
|
static |
output method of orbital fixing propagator statistics table to output file stream 'file'
Definition at line 91 of file prop_orbitalfixing.c.
References SCIP_OKAY, SCIP_VERBLEVEL_MINIMAL, SCIPtableGetData(), and SCIPverbMessage().
|
static |
destructor of statistics table to free user data (called when SCIP is exiting)
Definition at line 115 of file prop_orbitalfixing.c.
References SCIP_OKAY, SCIPfreeBlockMemory, and SCIPtableGetData().
|
static |
perform orbital fixing
Note that we do not have to distinguish between variables that have been fixed or branched to 1, since the stabilizer is with respect to the variables that have been branched to 1. Thus, if an orbit contains a variable that has been branched to 1, the whole orbit only contains variables that have been branched to 1 - and nothing can be fixed.
scip | SCIP pointer |
permvars | variables |
npermvars | number of variables |
orbits | array of non-trivial orbits |
orbitbegins | array containing begin positions of new orbits in orbits array |
norbits | number of orbits |
infeasible | pointer to store whether problem is infeasible |
nfixedzero | pointer to store number of variables fixed to 0 |
nfixedone | pointer to store number of variables fixed to 1 |
Definition at line 139 of file prop_orbitalfixing.c.
References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), and TRUE.
Referenced by propagateOrbitalFixing().
|
static |
Get branching variables on the path to root
scip | SCIP pointer |
nvars | number of variables |
varmap | map of variables to indices in vars array |
b1 | bitset marking the variables branched to 1 |
success | pointer to store whether branching variables were computed successfully |
Definition at line 275 of file prop_orbitalfixing.c.
References FALSE, SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPboundchgGetBoundchgtype(), SCIPboundchgGetVar(), SCIPdomchgGetBoundchg(), SCIPdomchgGetNBoundchgs(), SCIPgetCurrentNode(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPnodeGetDepth(), SCIPnodeGetDomchg(), SCIPnodeGetParent(), SCIPprintNodeRootPath(), SCIPvarGetLbLocal(), SCIPvarGetType(), and TRUE.
Referenced by propagateOrbitalFixing().
|
static |
propagate orbital fixing
scip | SCIP pointer |
propdata | propagator data |
infeasible | pointer to store whether the node is detected to be infeasible |
nprop | pointer to store the number of propagations |
Definition at line 359 of file prop_orbitalfixing.c.
References computeBranchingVariables(), FALSE, performOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_Shortbool, SCIPallocBufferArray, SCIPcomputeGroupOrbitsSymbreak(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetPermvarsObjSymmetry(), SCIPisEQ(), SCIPvarGetType(), and TRUE.
Referenced by SCIP_DECL_PROPEXEC().
|
static |
destructor of propagator to free user data (called when SCIP is exiting)
Definition at line 489 of file prop_orbitalfixing.c.
References SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropGetName().
|
static |
initialization method of propagator (called after problem was transformed)
Definition at line 508 of file prop_orbitalfixing.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetIntParam(), SCIPpropGetData(), SCIPpropGetName(), SCIPregisterSymmetry(), SYM_HANDLETYPE_ORBITALFIXING, SYM_SPEC_BINARY, SYM_SPEC_INTEGER, and TRUE.
|
static |
deinitialization method of propagator (called before transformed problem is freed)
Definition at line 541 of file prop_orbitalfixing.c.
References SCIP_OKAY, SCIPhashmapFree(), and SCIPpropGetData().
|
static |
solving process initialization method of propagator (called when branch and bound process is about to begin)
Definition at line 570 of file prop_orbitalfixing.c.
References FALSE, SCIP_CALL, SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPblkmem(), SCIPgetGeneratorsSymmetry(), SCIPgetStatus(), SCIPhashmapCreate(), SCIPhashmapInsert(), SCIPisStopped(), SCIPisTransformed(), and SCIPpropGetData().
|
static |
execution method of propagator
Definition at line 626 of file prop_orbitalfixing.c.
References FALSE, propagateOrbitalFixing(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_Longint, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_STAGE_SOLVING, SCIPdebugMsg, SCIPgetCurrentNode(), SCIPgetDepth(), SCIPgetNRuns(), SCIPgetStage(), SCIPinProbing(), SCIPnodeGetNumber(), SCIPpropGetData(), and SCIPpropGetName().
|
static |
propagation conflict resolving method of propagator
Note that this is relatively difficult to obtain: One needs to include all bounds of variables to would lead to a different orbit in which the variables that was propagated lies. This includes all variables that are moved by the permutations which are involved in creating the orbit.
Definition at line 692 of file prop_orbitalfixing.c.
References SCIP_DIDNOTFIND, and SCIP_OKAY.