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 PROP_PRESOL_PRIORITY   -1000000
 
#define PROP_PRESOLTIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */
 
#define PROP_PRESOL_MAXROUNDS   -1
 
#define DEFAULT_SYMCOMPTIMING   2
 
#define DEFAULT_PERFORMPRESOLVING   FALSE
 
#define DEFAULT_ENABLEDAFTERRESTARTS   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 getSymmetries (SCIP *scip, SCIP_PROPDATA *propdata)
 
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_PROPINITPRE (propInitpreOrbitalfixing)
 
static SCIP_DECL_PROPPRESOL (propPresolOrbitalFixing)
 
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().

◆ PROP_PRESOL_PRIORITY

#define PROP_PRESOL_PRIORITY   -1000000

priority of the presolving method (>= 0: before, < 0: after constraint handlers)

Definition at line 51 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_PRESOLTIMING

#define PROP_PRESOLTIMING   SCIP_PRESOLTIMING_EXHAUSTIVE /* timing of the presolving method (fast, medium, or exhaustive) */

Definition at line 52 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ PROP_PRESOL_MAXROUNDS

#define PROP_PRESOL_MAXROUNDS   -1

maximal number of presolving rounds the presolver participates in (-1: no limit)

Definition at line 53 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ DEFAULT_SYMCOMPTIMING

#define DEFAULT_SYMCOMPTIMING   2

timing of symmetry computation for orbital fixing (0 = before presolving, 1 = during presolving, 2 = at first call)

Definition at line 56 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ DEFAULT_PERFORMPRESOLVING

#define DEFAULT_PERFORMPRESOLVING   FALSE

Run orbital fixing during presolving?

Definition at line 59 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ DEFAULT_ENABLEDAFTERRESTARTS

#define DEFAULT_ENABLEDAFTERRESTARTS   FALSE

Run orbital fixing after a restart has occured?

Definition at line 60 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_NAME_ORBITALFIXING

#define TABLE_NAME_ORBITALFIXING   "orbitalfixing"

Definition at line 64 of file prop_orbitalfixing.c.

Referenced by SCIPincludePropOrbitalfixing().

◆ TABLE_DESC_ORBITALFIXING

#define TABLE_DESC_ORBITALFIXING   "orbital fixing statistics"

Definition at line 65 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 66 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 67 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 108 of file prop_orbitalfixing.c.

References NULL, SCIP_DECL_TABLEFREE(), 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 132 of file prop_orbitalfixing.c.

References getSymmetries(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, and SCIPtableGetData().

Referenced by SCIP_DECL_TABLEOUTPUT().

◆ getSymmetries()

static SCIP_RETCODE getSymmetries ( SCIP scip,
SCIP_PROPDATA propdata 
)
static

◆ 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 213 of file prop_orbitalfixing.c.

References computeBranchingVariables(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPdebugMsg, SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), and TRUE.

Referenced by getSymmetries(), and 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 349 of file prop_orbitalfixing.c.

References FALSE, NULL, propagateOrbitalFixing(), SCIP_BOUNDCHGTYPE_BRANCHING, SCIP_CALL, SCIP_OKAY, SCIP_VARTYPE_BINARY, SCIPboundchgGetBoundchgtype(), SCIPboundchgGetVar(), SCIPdomchgGetBoundchg(), SCIPdomchgGetNBoundchgs(), SCIPgetCurrentNode(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPnodeGetDepth(), SCIPnodeGetDomchg(), SCIPnodeGetParent(), SCIPprintNodeRootPath(), SCIPvarGetLbLocal(), SCIPvarGetType(), and TRUE.

Referenced by performOrbitalFixing(), and propagateOrbitalFixing().

◆ propagateOrbitalFixing()

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

◆ SCIP_DECL_PROPFREE()

static SCIP_DECL_PROPFREE ( propFreeOrbitalfixing  )
static

destructor of propagator to free user data (called when SCIP is exiting)

Definition at line 594 of file prop_orbitalfixing.c.

References NULL, SCIP_DECL_PROPINIT(), SCIP_OKAY, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPpropGetData(), and SCIPpropGetName().

Referenced by propagateOrbitalFixing().

◆ SCIP_DECL_PROPINIT()

static SCIP_DECL_PROPINIT ( propInitOrbitalfixing  )
static

initialization method of propagator (called after problem was transformed)

Definition at line 613 of file prop_orbitalfixing.c.

References FALSE, NULL, SCIP_CALL, SCIP_DECL_PROPEXIT(), SCIP_OKAY, SCIPdebugMsg, SCIPgetIntParam(), SCIPpropGetData(), SCIPpropGetName(), SYM_HANDLETYPE_ORBITALFIXING, and TRUE.

Referenced by SCIP_DECL_PROPFREE().

◆ SCIP_DECL_PROPEXIT()

static SCIP_DECL_PROPEXIT ( propExitOrbitalfixing  )
static

deinitialization method of propagator (called before transformed problem is freed)

Definition at line 640 of file prop_orbitalfixing.c.

References NULL, SCIP_DECL_PROPINITPRE(), SCIP_OKAY, SCIPhashmapFree(), and SCIPpropGetData().

Referenced by SCIP_DECL_PROPINIT().

◆ SCIP_DECL_PROPINITPRE()

static SCIP_DECL_PROPINITPRE ( propInitpreOrbitalfixing  )
static

presolving initialization method of propagator (called when presolving is about to begin)

Definition at line 672 of file prop_orbitalfixing.c.

References getSymmetries(), NULL, SCIP_CALL, SCIP_DECL_PROPPRESOL(), SCIP_OKAY, SCIP_STATUS_UNKNOWN, SCIPgetStatus(), SCIPisTransformed(), and SCIPpropGetData().

Referenced by SCIP_DECL_PROPEXIT().

◆ SCIP_DECL_PROPPRESOL()

static SCIP_DECL_PROPPRESOL ( propPresolOrbitalFixing  )
static

◆ 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 829 of file prop_orbitalfixing.c.

References NULL, SCIP_DIDNOTFIND, SCIP_OKAY, and SCIPincludePropOrbitalfixing().

Referenced by SCIP_DECL_PROPEXEC().