Scippy

SCIP

Solving Constraint Integer Programs

prop_orbitalfixing.c File Reference

Detailed Description

propagator for orbital fixing

Author
Marc Pfetsch

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)
 

Macro Definition Documentation

◆ PROP_NAME

#define PROP_NAME   "orbitalfixing"

Definition at line 44 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_DESC

#define PROP_DESC   "propagator for orbital fixing"

Definition at line 45 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_TIMING

#define PROP_TIMING   SCIP_PROPTIMING_BEFORELP

propagation timing mask

Definition at line 46 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_PRIORITY

#define PROP_PRIORITY   -1000000

propagator priority

Definition at line 47 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_FREQ

#define PROP_FREQ   1

propagator frequency

Definition at line 48 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_DELAY

#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().

◆ TABLE_NAME_ORBITALFIXING

#define TABLE_NAME_ORBITALFIXING   "orbitalfixing"

Definition at line 52 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_DESC_ORBITALFIXING

#define TABLE_DESC_ORBITALFIXING   "orbital fixing statistics"

Definition at line 53 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_POSITION_ORBITALFIXING

#define TABLE_POSITION_ORBITALFIXING   7001

the position of the statistics table

Definition at line 54 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_EARLIEST_ORBITALFIXING

#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().

Function Documentation

◆ SCIP_DECL_TABLEOUTPUT()

static SCIP_DECL_TABLEOUTPUT ( tableOutputOrbitalfixing  )
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().

◆ SCIP_DECL_TABLEFREE()

static SCIP_DECL_TABLEFREE ( tableFreeOrbitalfixing  )
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().

◆ performOrbitalFixing()

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

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.

Parameters
scipSCIP pointer
permvarsvariables
npermvarsnumber of variables
orbitsarray of non-trivial orbits
orbitbeginsarray containing begin positions of new orbits in orbits array
norbitsnumber of orbits
infeasiblepointer to store whether problem is infeasible
nfixedzeropointer to store number of variables fixed to 0
nfixedonepointer 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().

◆ computeBranchingVariables()

static SCIP_RETCODE computeBranchingVariables ( SCIP scip,
int  nvars,
SCIP_HASHMAP varmap,
SCIP_Shortbool b1,
SCIP_Bool success 
)
static

Get branching variables on the path to root

Parameters
scipSCIP pointer
nvarsnumber of variables
varmapmap of variables to indices in vars array
b1bitset marking the variables branched to 1
successpointer 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().

◆ propagateOrbitalFixing()

static SCIP_RETCODE propagateOrbitalFixing ( SCIP scip,
SCIP_PROPDATA propdata,
SCIP_Bool infeasible,
int *  nprop 
)
static

propagate orbital fixing

Parameters
scipSCIP pointer
propdatapropagator data
infeasiblepointer to store whether the node is detected to be infeasible
nproppointer 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().

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeOrbitalfixing  )
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().

◆ SCIP_DECL_PROPINIT()

static SCIP_DECL_PROPINIT ( propInitOrbitalfixing  )
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.

◆ SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitOrbitalfixing  )
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().

◆ SCIP_DECL_PROPINITSOL()

static SCIP_DECL_PROPINITSOL ( propInitsolOrbitalfixing  )
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().

◆ SCIP_DECL_PROPEXEC()

◆ SCIP_DECL_PROPRESPROP()

static SCIP_DECL_PROPRESPROP ( propRespropOrbitalfixing  )
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.